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

Understand

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.