New Sample Complexity Bounds for (Regularized) Sample Average
  Approximation in Several Heavy-Tailed, Non-Lipschitzian, and High-Dimensional
  Cases
Hongcheng Liu Jindong Tong
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.