Research map / Optimization / Nonconvex and smooth optimization
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
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 |
|---|---|---|---|
| Add NEON negative-curvature extraction to SGD | SGD · (ε, ε^{1/2})-SSP, high probability | IFO time complexity: Noisy SGD: \widetilde O\left(T_gd^p\epsilon^{-4}\right) -> NEON-SGD: \widetilde O\left(T_g\epsilon^{-4}\right) | Helped |
| Add NEON negative-curvature extraction to stochastic momentum | Stochastic momentum · (ε, ε^{1/2})-SSP, high probability | IFO time complexity: \widetilde O\left(T_g\epsilon^{-4}\right) | Helped |
| Add NEON negative-curvature extraction to SCSG | SCSG · (ε, ε^{1/2})-SSP, high probability | IFO time complexity: \widetilde O\left(T_g\epsilon^{-3.5}\right) | Helped |
| Replace second-order negative-curvature search with NEON | Natasha2 · (ε, ε^{1/2})-SSP, expectation | time complexity: Natasha2: \widetilde O\left( T_g\epsilon^{-3.5}+T_h\epsilon^{-2.5} \right) -> NEON-Natasha: \widetilde O\left(T_g\epsilo | Helped |
| Replace second-order negative-curvature search with NEON | SVRG-Hessian · (ε, ε^{1/2})-SSP, high probability | oracle requirement | Helped |
| Use accelerated gradient rather than gradient descent in noise-originated curvature extraction (ablation) | NEON · Negative-curvature extraction, Hessian minimum eigenvalue ≤ -γ | iteration complexity: O(1/\gamma) -> \widetilde O(1/\sqrt{\gamma}) | Helped |
| Use a stochastic mini-batch version of NEON | NEON · Negative-curvature extraction on gisette simulation | IFO calls to find a good negative-curvature direction | Helped |
Closest papers by meaning
- Escaping Saddles with Stochastic Gradients (ICML 2018 · similarity 0.91)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.89)
- On The Complexity of First-Order Methods in Stochastic Bilevel Optimization (ICML 2024 · similarity 0.89)
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry (NeurIPS 2024 · similarity 0.88)
- Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functions (NeurIPS 2024 · similarity 0.88)
- Second-Order Convergence in Private Stochastic Non-Convex Optimization (NeurIPS 2025 · 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.