We present exponential finite-sample nonasymptotic deviation inequalities for the SAA estimator's near-optimal solution set over the class of stochastic optimization problems with heavy-tailed random H "older continuous functions in the objective and constraints. Such setting is better suited for problems where a sub-Gaussian data generating distribution is less expected, e.g., in stochastic portfolio optimization. One of our contributions is to exploit of the perturbed objective and the perturbed constraints as a property which entails deviation inequalities for joint feasibility and optimality guarantees. This means that our bounds are significantly tighter in terms of diameter and metric entropy since they depend only on the near-optimal solution set but not on the whole feasible set. As a result, we obtain a much sharper sample complexity estimate when compared to a general nonconvex problem. In our analysis, we derive some localized deterministic perturbation error bounds for convex optimization problems which are of independent interest. To obtain our results, we only assume a metric regular convex feasible set, possibly not satisfying the Slater condition and not having a metric regular solution set. In this general setting, joint near feasibility and near optimality are guaranteed. If in addition the set satisfies the Slater condition, we obtain finite-sample simultaneous exact feasibility and near optimality guarantees. Another contribution of our work is to present, as a proof of concept of our localized techniques, a persistent result for a variant of the LASSO estimator under very weak assumptions on the data generating distribution.
: In @cite_5 , the authors consider items (1)-(2) above for (possibly nonconvex) SO problems. Although it includes a broader class of problems, the price to be paid with such generality is that one must consider the @math in order to state nonasymptotic deviation inequalities for the SAA solution set. More precisely, for the concentration of measure property to hold, the variance-type error induced by sample average approximation depends on the diameter and metric entropy of the whole feasible set (see Section for a precise statement). For example, if the @math are Lipschitz continuous, @math is an (random) upper bound on @math and Assumptions - or Assumptions - hold, the bounds stated in @cite_5 ensure joint feasibility and optimality guarantees with probability at least @math as long as the sample size @math for some constant @math . Here, @math , @math is the diameter of @math , @math and @math is a quantity related to the metric entropy of @math In our setting, this is typically of the order of @math . (see Definition in Section of this paper and Section 4.1 in @cite_5 ).
@cite_5
1984332158
The stochastic multiarmed bandit problem is well understood when the reward distributions are sub-Gaussian. In this paper, we examine the bandit problem under the weaker assumption that the distributions have moments of order 1 + e, for some e ∈ (0,1]. Surprisingly, moments of order 2 (i.e., finite variance) are sufficient to obtain regret bounds of the same order as under sub-Gaussian reward distributions. In order to achieve such regret, we define sampling strategies based on refined estimators of the mean such as the truncated empirical mean, Catoni's M-estimator, and the median-of-means estimator. We also derive matching lower bounds that also show that the best achievable regret deteriorates when e <; 1.