Research map / Optimization / Nonconvex and smooth optimization
Natasha 2: Faster Non-Convex Optimization Than 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 |
|---|---|---|---|
| Combine Natasha1.5 for stationary-point steps with Oja's algorithm for negative-curvature detection | Natasha2 · Approximate local minima | gradient complexity: eO(ε−4) -> eO(ε−3.25) | Improved |
| Use a negative-curvature direction from Oja's algorithm rather than random perturbation to escape saddle points | Natasha2 · Approximate local minima | gradient complexity: eO(ε−4 · poly(d)) -> eO(ε−3.25) | Improved |
Closest papers by meaning
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (NeurIPS 2018 · similarity 0.91)
- Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimization (JMLR 2022 · similarity 0.91)
- Stochastic Variance Reduction for Nonconvex Optimization (ICML 2016 · similarity 0.90)
- The Complexity of Finding Stationary Points with Stochastic Gradient Descent (ICML 2020 · similarity 0.90)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.88)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 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.
