ICML 2024poster1 citations
New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming
Abstract
This paper studies sample average approximation (SAA) and its simple regularized variation in solving convex or strongly convex stochastic programming problems. Under heavy-tailed assumptions and comparable regularity conditions as in the typical SAA literature, we show --- perhaps for the first time --- that the sample complexity can be completely free from any complexity measure (e.g., logarithm of the covering number) of the feasible region. As a result, our new bounds can be more advantageous than the state-of-the-art in terms of the dependence on the problem dimensionality.
BibTeX
@inproceedings{
liu2024new,
title={New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming},
author={Hongcheng Liu and Jindong Tong},
booktitle={Forty-first International Conference on Machine Learning},
year={2024},
url={https://openreview.net/forum?id=2hWd4CVhXz}
}