English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the sample complexity of sample average approximation (SAA) and itssimple variations, referred to as the regularized SAA (RSAA), in solving convexand strongly convex stochastic programming (SP) problems underheavy-tailed-ness, non-Lipschitz-ness, and/or high dimensionality. The presenceof such irregularities underscores critical vacua in the literature. Inresponse, this paper presents three sets of results: First, we show that the(R)SAA is effective even if the objective function is not necessarily Lipschitzand the underlying distribution admits some bounded central moments only at(near-)optimal solutions. Second, when the SP's objective function is the sumof a smooth term and a Lipschitz term, we prove that the (R)SAA's samplecomplexity is completely independent from any complexity measures (e.g., thecovering number) of the feasible region. Third, we explicate the (R)SAA'ssample complexities with regard to the dependence on dimensionality $d$: Whensome $p$th ($p\geq 2$) central moment of the underlying distribution isbounded, 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 structuralassumptions: (i) strong convexity w.r.t. the $q$-norm ($q\geq 1$); (ii) thecombination of restricted strong convexity and sparsity; and (iii) adimension-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\geqc\cdot \ln d$ is admissible for some constant $c>0$. These new results deviatefrom the SAA's typical sample complexities that grow polynomially with $d$.Part of our proof is based on the average-replace-one (RO) stability, whichappears to be novel for the (R)SAA's analyses.

New Sample Complexity Bounds for (Regularized) Sample Average Approximation in Several Heavy-Tailed, Non-Lipschitzian, and High-Dimensional Cases