Research map / Optimization / Nonconvex and smooth optimization
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
Zeyuan Allen-Zhu
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 |
|---|---|---|---|
| apply SGD after SGD instead of using naive SGD for small gradient norm | convex stochastic optimization · online convex, gradient norm eps | gradient complexity exponent: ε−4 -> ε−8/3 | Improved |
| add regularization with sigma proportional to eps before SGD1 | SGD1 · online convex, gradient norm eps | gradient complexity exponent: ε−8/3 -> ε−5/2 | Improved |
| use recursive regularization with doubling sigma and warm starts instead of single regularization | SGD2 · online convex, gradient norm eps | gradient complexity exponent: ε−5/2 -> ε−2 log^3(1/ε) | Improved |
| apply the recursive-regularization idea to nonconvex objectives (SGD5) | nonconvex SGD variants · online nonconvex, approximate local minimum | gradient complexity exponent: ε−4 -> ε−3.5 | Improved |
Closest papers by meaning
- Natasha 2: Faster Non-Convex Optimization Than SGD (NeurIPS 2018 · similarity 0.91)
- Learning Rates for Stochastic Gradient Descent With Nonconvex Objectives (TPAMI 2021 · similarity 0.90)
- The Complexity of Finding Stationary Points with Stochastic Gradient Descent (ICML 2020 · similarity 0.89)
- Benign Underfitting of Stochastic Gradient Descent (NeurIPS 2022 · similarity 0.89)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.89)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.88)
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.
