mlsanityData to 7 Oct 2026

Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

arXiv 2006.13476 ↗First posted 24 Jun 2020cs.LG math.OC stat.MLcited by 39

Not on the map. Why?

Abstract (arXiv)

We design an algorithm which finds an ε-approximate stationary point (with |nabla F(x)|≤ ε) using O(ε-3) stochastic gradient and Hessian-vector products, matching guarantees that were previously available only under a stronger assumption of access to multiple queries with the same random seed. We prove a lower bound which establishes that this rate is optimal and---surprisingly---that it cannot be improved using stochastic pth order methods for any p≥ 2, even when the first p derivatives of the objective are Lipschitz. Together, these results characterize the complexity of non-convex stochastic optimization with second-order methods and beyond. Expanding our scope to the oracle complexity of finding (ε,γ)-approximate second-order stationary points, we establish nearly matching upper and lower bounds for stochastic second-order methods. Our lower bounds here are novel even in the noiseless case.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 7; 2023: 8; 2024: 8; 2025: 8; 2026: 2.

39 papers.

Sort:

By area:

  1. 2022Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Modelscited by 172
  2. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  3. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 53
  4. 2023Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversioncited by 42
  5. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  6. 2023Deterministic Nonsmooth Nonconvex Optimizationcited by 25
  7. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 22
  8. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 19
  9. 2024Random Scaling and Momentum for Non-smooth Non-convex Optimizationcited by 18
  10. 2022Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusionscited by 17
  11. 2023Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oraclescited by 16
  12. 2021Better SGD using Second-order Momentumcited by 14
27 more
  1. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 14
  2. 2022Momentum-Based Policy Gradient with Second-Order Informationcited by 11
  3. 2022Momentum Aggregation for Private Non-convex ERMcited by 10
  4. 2024Learning Optimal Deterministic Policies with Stochastic Policy Gradientscited by 10
  5. 2024Private Zeroth-Order Nonsmooth Nonconvex Optimizationcited by 8
  6. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  7. 2023Debiasing Conditional Stochastic Optimizationcited by 6
  8. 2021On the Second-order Convergence Properties of Random Search Methodscited by 5
  9. 2025Diffusion-DFL: Decision-focused Diffusion Models for Stochastic Optimizationcited by 5
  10. 2024Reevaluating Theoretical Analysis Methods for Optimization in Deep Learningcited by 3
  11. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  12. 2025Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limitscited by 3
  13. 2022Variance-Reduced Conservative Policy Iterationcited by 2
  14. 2025On the Condition Number Dependency in Bilevel Optimizationcited by 2
  15. 2021On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimizationcited by 1
  16. 2021Faster Perturbed Stochastic Gradient Methods for Finding Local Minimacited by 1
  17. 2023A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guaranteescited by 1
  18. 2024On the Stochastic (Variance-Reduced) Proximal Gradient Method for Regularized Expected Reward Optimizationcited by 1
  19. 2025Faster Gradient Methods for Highly-Smooth Stochastic Bilevel Optimizationcited by 1
  20. 2025Asynchronous Policy Gradient Aggregation for Efficient Distributed Reinforcement Learningcited by 1
  21. 2023Stochastic Dimension-reduced Second-order Methods for Policy Optimizationcited by 0
  22. 2023A Homogenization Approach for Gradient-Dominated Stochastic Optimizationcited by 0
  23. 2024A stochastic first-order method with multi-extrapolated momentum for highly smooth unconstrained optimizationcited by 0
  24. 2025FUSE: First-Order and Second-Order Unified SynthEsis in Stochastic Optimizationcited by 0
  25. 2025Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Constructioncited by 0
  26. 2026Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methodscited by 0
  27. 2026Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimizationcited by 0