# Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints

arXiv: https://arxiv.org/abs/1705.00822 · HTML: https://mlsanity.com/paper/1705.00822/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2017.

## Built on by (most cited first, 4 of 4)

- [Constrained Learning with Non-Convex Losses](https://mlsanity.com/paper/2103.05134/) (2021)
- [Data-Driven Minimax Optimization with Expectation Constraints](https://mlsanity.com/paper/2202.07868/) (2022)
- [Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming](https://mlsanity.com/paper/2401.00664/) (2024)
- [Subsampled Ensemble Can Improve Generalization Tail Exponentially](https://mlsanity.com/paper/2405.14741/) (2024)

## Abstract (arXiv)

We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are "sub-Gaussian"~even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to have been considered before in the non-asymptotic literature. Our proofs combine different ideas of potential independent interest: an adaptation of Talagrand's "generic chaining"~bound for sub-Gaussian processes; "localization"~ideas from the Statistical Learning literature; and the use of standard conditions in Optimization (metric regularity, Slater-type conditions) to control fluctuations of the feasible set.