Research map / Learning theory and algorithms / Sample complexity
New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that sample average approximation (SAA) and a Tikhonov-regularized variant (RSAA) for convex and strongly convex stochastic programs have sample complexity bounds free of any feasible-region complexity measure, under only bounded gradient-variance (heavy-tailed) assumptions.
Problem
Sample complexity of SAA and regularized SAA for convex/strongly convex stochastic programming under heavy-tailed randomness, where existing bounds grow polynomially with feasible-region complexity measures (covering number, generic chaining) and hence with dimension d.
Approach
Uses an average-replace-one stability argument to derive SAA/RSAA sample complexity bounds that depend only on gradient variance, smoothness and strong convexity constants, with no covering-number or generic-chaining term, requiring only a finite second moment of the gradient deviation.
Key results
- For mu-strongly convex SP, SAA needs N >= O(max(L/mu, (sigma_p^2 + M^2)/(mu*eps*beta))) samples, with no feasible-region complexity term.
- For general convex SP, RSAA needs N >= O(V(x*)/(q'-1) * max(L/eps, (sigma_p^2+M^2)/(eps^2 beta))) samples, free of covering-number or generic-chaining terms.
- Under the heavy-tailed bounded-variance assumption, the dependence on feasible-set complexity is removed, with the sample rates reduced to O(1/(eps*beta)) and O(1/(eps^2 beta)) when L and M are negligible.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SAA under the stated strong-convexity and bounded-gradient-variance assumptions | SAA · Strongly convex stochastic programming | sample complexity (suboptimality ≤ ϵ with probability ≥ 1 − β): O(max{L/µ, (σ²_p + M²)/(µϵβ)}) | Helped |
| Add Tikhonov-like regularization to SAA with the specified hyperparameters | RSAA · General convex stochastic programming | sample complexity (suboptimality ≤ ϵ with probability ≥ 1 − β): O(R∗/(q′ − 1) · max{L/ϵ, (σ²_p + M²)/(βϵ²)}) | Helped |
| Avoid feasible-region complexity measures in the sample complexity bound | SAA and RSAA · Strongly convex and general convex stochastic programming | dependence on feasible-region complexity | Helped |
| Exploit strong convexity in the SAA bound | SAA · Strongly convex stochastic programming | dependence on ϵ | Helped |
Surprising findings
- Sample complexity for SAA can be made independent of feasible-region complexity measures such as covering number or generic chaining, which prior work deemed unavoidable under heavy tails.
Limitations
- Results are purely theoretical with no empirical validation.
- Requires convexity of the cost function and Lipschitz-gradient or Lipschitz conditions on the objective components.
- Dependence on sigma_p may implicitly grow with dimension d unless p is large.
Experimental setup
Metrics: sample complexity (required sample size N for epsilon-subopt
Baselines: Shapiro et al. 2021 covering-number SAA bound Oliveira & Thompson 2023 generic chaining SAA bound uniform stability bounds (Hu et al. 2020)
Builds on: sample average approximation uniform stability generic chaining bounds (Oliveira & Thompson 2023) average-replace-one stability (Shalev-Shwartz et al. 2010)
Closest papers by meaning
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.90)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.90)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.89)
- Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions (NeurIPS 2024 · similarity 0.87)
- Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling (ICML 2025 · similarity 0.87)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.