  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.
