Research map / Optimization / Nonconvex and smooth optimization
Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ERM on Lipschitz-bounded convex functions (non-smooth construction) instead of uniform-convergence-based bounds; sample size needed scales linearly with dimension d (lower bound: ERM fails with n ≤ d/6 samples) | ERM for l2/l2 Lipschitz-bounded SCO · Lipschitz-bounded SCO, unit l2 ball, eps=1/4 | excess population risk of ERM solution (lower bound) | Hurt |
| Smooth (1-smooth) variant of the construction using quadratically smoothed max and non-interacting components | ERM for smooth convex functions · l2 ball, 1-smooth functions | excess population risk of ERM solution (lower bound) | No clear effect |
| Add l1 regularization lambda*||x||_1 (lambda ≤ 1/sqrt(d)) to ERM objective (ablation) | ERM with l1 regularization · l2 ball radius 2, Lipschitz construction | excess population risk of regularized ERM (lower bound) | No clear effect |
| Bounded-range (non-Lipschitz, range [0,1]) functions in dimension 2; ERM requires infinite samples | ERM for bounded-range convex functions · B_2^2, range [0,1] | excess population risk of ERM (lower bound) | Hurt |
| Low-complexity construction with functions from asymptotically good efficient binary codes (each function described by log d bits, computable in O(d) time) | ERM for efficiently computable Lipschitz functions · l2 ball, [d,d/2,rho d,O(d)] code | excess population risk of ERM (lower bound) | Hurt |
Closest papers by meaning
- All ERMs Can Fail in Stochastic Convex Optimization Lower Bounds in Linear Dimension (ICML 2026 · similarity 0.93)
- Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions (NeurIPS 2018 · similarity 0.90)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.89)
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.88)
- New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.87)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.86)
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.