We study the sample complexity of sample average approximation (SAA) and its simple variations, referred to as the regularized SAA (RSAA), in solving convex and strongly convex stochastic programming (SP) problems under heavy-tailed-ness, non-Lipschitz-ness, and/or high dimensionality. The presence of such irregularities underscores critical vacua in the literature. In response, this paper presents three sets of results: First, we show that the (R)SAA is effective even if the objective function is not necessarily Lipschitz and the underlying distribution admits some bounded central moments only at (near-)optimal solutions. Second, when the SP's objective function is the sum of a smooth term and a Lipschitz term, we prove that the (R)SAA's sample complexity is completely independent from any complexity measures (e.g., the covering number) of the feasible region. Third, we explicate the (R)SAA's sample complexities with regard to the dependence on dimensionality $d$: When some $p$th ($p\geq 2$) central moment of the underlying distribution is bounded, we show that the required sample size grows at a rate no worse than $\mathcal O\left(p d^{2/p}\right)$ under any one of the three structural assumptions: (i) strong convexity w.r.t. the $q$-norm ($q\geq 1$); (ii) the combination of restricted strong convexity and sparsity; and (iii) a dimension-insensitive $q$-norm of an optimal solution. In both cases of (i) and (iii), it is further required that $p\leq q/(q-1)$. As a direct implication, the (R)SAA's complexity becomes (poly-)logarithmic in $d$, whenever $p\geq c\cdot \ln d$ is admissible for some constant $c>0$. These new results deviate from the SAA's typical sample complexities that grow polynomially with $d$. Part of our proof is based on the average-replace-one (RO) stability, which appears to be novel for the (R)SAA's analyses.

本文研究了在重尾性、非Lipschitz性和/或高维度下解决凸随机规划问题中样本平均逼近（SAA）及其简单变形，即正则化SAA（RSAA）的样本复杂度。通过三组结果，论文表明(R)SAA在目标函数不一定是Lipschitz的情况下，且底层分布仅在（近）最优解处具有一些有界的中心矩时仍然有效。当SP的目标函数是平滑项和Lipschitz项的和时，(R)SAA的样本复杂度与可行域的任何复杂性度量（如覆盖数）完全独立。此外，本文阐明了(R)SAA在与维度d相关时的样本复杂度，当底层分布的第p(p≥2)个中心矩有界时，在三个结构性假设中，所需样本量的增长速率不会超过O(p d^(2/p))，即使p≤q/(q-1)也成立。这些新结果与SAA典型的随维度d多项式增长的样本复杂度相异。

多种重尾、非Lipschitzian及高维情况下，(正则化的)样本平均逼近的新样本复杂性界