Research map / Optimization / Nonconvex and smooth optimization
Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter
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 Natasha1, with regularization-based retraction and sub-epochs, instead of prior offline methods | σ-bounded nonconvex optimization · Functions with σ ≥ L / √n | gradient complexity | Helped |
| Use Natasha1 rather than repeatSVRG in the regime σ < L / √n | σ-bounded nonconvex optimization · Functions with σ < L / √n | gradient complexity | Mixed |
| Use Natasha1 rather than repeatSVRG | σ-bounded nonconvex optimization · σ = L | gradient complexity | No clear effect |
| Use Natasha2 with the added Katyusha-style averaging update | Optimization with (ℓ1,ℓ2)-smooth component functions · n ≥ ℓ1ℓ2 / σ² or n ≤ [paper's stated alternative condition] | gradient complexity | Mixed |
Closest papers by meaning
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.90)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.90)
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity (NeurIPS 2024 · similarity 0.90)
- Stochastic Newton Proximal Extragradient Method (NeurIPS 2024 · similarity 0.89)
- On the Almost Sure Convergence of the Stochastic Three Points Algorithm (ICLR 2025 · similarity 0.89)
- High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails (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.