mlsanityData to 7 Oct 2026

Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients

arXiv 2210.01496 ↗First posted 4 Oct 2022math.OC cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

We consider escaping saddle points of nonconvex problems where only the function evaluations can be accessed. Although a variety of works have been proposed, the majority of them require either second or first-order information, and only a few of them have exploited zeroth-order methods, particularly the technique of negative curvature finding with zeroth-order methods which has been proven to be the most efficient method for escaping saddle points. To fill this gap, in this paper, we propose two zeroth-order negative curvature finding frameworks that can replace Hessian-vector product computations without increasing the iteration complexity. We apply the proposed frameworks to ZO-GD, ZO-SGD, ZO-SCSG, ZO-SPIDER and prove that these ZO algorithms can converge to (ε,δ)-approximate second-order stationary points with less query complexity compared with prior zeroth-order works for finding local minima.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 34 of its 55 references that are in the map. First posted on arXiv 4 Oct 2022.

Builds on

34 of 55 references.

References · 34

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2016Practical Black-Box Attacks against Machine Learningcited by 893
  3. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  4. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  5. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 555
  6. 2017How to Escape Saddle Points Efficientlycited by 284
  7. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  8. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  9. 2016Deep Learning without Poor Local Minimacited by 233
  10. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  11. 2018AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networkscited by 137
  12. 2016Matrix Completion has No Spurious Local Minimumcited by 124
22 more
  1. 2016A Geometric Analysis of Phase Retrievalcited by 92
  2. 2017Learning One-hidden-layer Neural Networks with Landscape Designcited by 79
  3. 2016Gradient Descent Learns Linear Dynamical Systemscited by 78
  4. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  5. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  6. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  7. 2017Natasha 2: Faster Non-Convex Optimization Than SGDcited by 49
  8. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  9. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  10. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  11. 2017Neon2: Finding Local Minima via First-Order Oraclescited by 36
  12. 2017On the Optimization Landscape of Tensor Decompositionscited by 21
  13. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  14. 2015Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squarerootcited by 15
  15. 2018On the Local Minima of the Empirical Riskcited by 12
  16. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  17. 2019Efficiently avoiding saddle points with zero order methods: No gradients requiredcited by 10
  18. 2017NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimizationcited by 9
  19. 2019Every Local Minimum Value is the Global Minimum Value of Induced Model in Non-convex Machine Learningcited by 9
  20. 2021On the Second-order Convergence Properties of Random Search Methodscited by 5
  21. 2021Asynchronous Distributed Reinforcement Learning for LQR Control via Zeroth-Order Block Coordinate Descentcited by 4
  22. 2016Faster Principal Component Regression and Stable Matrix Chebyshev Approximationcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 1.

6 papers.

  1. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  2. 2025Converge Faster, Talk Less: Hessian-Informed Federated Zeroth-Order Optimizationcited by 3
  3. 2024Gradient Testing and Estimation by Comparisonscited by 0
  4. 2024How to Boost Any Loss Functioncited by 0
  5. 2024A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learningcited by 0
  6. 2026To Solve Bilevel Optimization with Nonconvex Lower Levels, We Need Second-Order Stationaritycited by 0