Research map / Optimization / Nonconvex and smooth optimization
Only tails matter: Average-Case Universality and Robustness in the Convex Regime
Leonardo Cunha, Gauthier Gidel, Fabian Pedregosa, Damien Scieur, Courtney Paquette
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 GCM with high beta (beta=5/2 or 3/2) instead of gradient descent | Generalized Chebyshev Method · Marchenko-Pastur-type ESD, asymptotic function-value rate | convergence exponent: t^{-3} vs t^{-3/2} at xi=-1/2 | Improved |
| Replace gradient descent with Nesterov's method | first-order methods on random quadratics · Marchenko-Pastur-type ESD, asymptotic function-value rate | convergence exponent: t^{-3}log t vs t^{-3/2} | Improved |
| Overestimate beta / underestimate alpha in GCM (robustness to parameter mis-tuning) | Generalized Chebyshev Method · Beta-distributed ESD, asymptotic rate | function-value rate | No clear effect |
| Use Nesterov's method on problems with concentration near 0 (low xi) | Nesterov method · Beta-distributed ESD, function-value rate | gap to optimal rate | No clear effect |
| Overestimating L in GCM | Generalized Chebyshev Method · Beta-distributed ESD | rate | No clear effect |
| Use beta below optimal beta* (beta<beta*) or low xi in GCM (ablation) | Generalized Chebyshev Method · Synthetic Beta / Marchenko-Pastur, finite dimension | variance of function value across initializations | Hurt |
Closest papers by meaning
- Non-Asymptotic and Non-Lipschitzian Bounds on Optimal Values in Stochastic Optimization Under Heavy Tails (ICML 2025 · similarity 0.88)
- Sifting through the noise: Universal first-order methods for stochastic variational inequalities (NeurIPS 2021 · similarity 0.88)
- New Sample Complexity Bounds for Sample Average Approximation in Heavy-Tailed Stochastic Programming (ICML 2024 · similarity 0.88)
- The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.86)
- High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise (ICML 2024 · 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.
