mlsanityData to 14 Oct 2026

On the Second-order Convergence Properties of Random Search Methods

arXiv 2110.13265 ↗First posted 25 Oct 2021math.OC cs.LGcited by 5

Not on the map. Why?

Abstract (arXiv)

We study the theoretical convergence properties of random-search methods when optimizing non-convex objective functions without having access to derivatives. We prove that standard random-search methods that do not rely on second-order information converge to a second-order stationary point. However, they suffer from an exponential complexity in terms of the input dimension of the problem. In order to address this issue, we propose a novel variant of random search that exploits negative curvature by only relying on function evaluations. We prove that this approach converges to a second-order stationary point at a much faster rate than vanilla methods: namely, the complexity in terms of the number of function evaluations is only linear in the problem dimension. We test our algorithm empirically and find good agreements with our theoretical results.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 28 of its 58 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

28 of 58 references.

References · 28

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  2. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  3. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
  4. 2017How to Escape Saddle Points Efficientlycited by 285
  5. 2014The Loss Surfaces of Multilayer Networkscited by 280
  6. 2016Deep Learning without Poor Local Minimacited by 234
  7. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  8. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  9. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  10. 2018Simple random search provides a competitive approach to reinforcement learningcited by 75
  11. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  12. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
16 more
  1. 2018Escaping Saddles with Stochastic Gradientscited by 66
  2. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 64
  3. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  4. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  5. 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 43
  6. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 40
  7. 2016The Power of Normalization: Faster Evasion of Saddle Pointscited by 29
  8. 2017First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Timecited by 29
  9. 2016An Improved Gap-Dependency Analysis of the Noisy Power Methodcited by 24
  10. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  11. 2017Accelerated Stochastic Power Iterationcited by 22
  12. 2014A Stochastic PCA and SVD Algorithm with an Exponential Convergence Ratecited by 18
  13. 2019Efficiently avoiding saddle points with zero order methods: No gradients requiredcited by 10
  14. 2021Direct-Search for a Class of Stochastic Min-Max Problemscited by 7
  15. 2020An Accelerated DFO Algorithm for Finite-sum Convex Functionscited by 4
  16. 2017On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimizationcited by 2

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 0; 2024: 2; 2025: 1.

5 papers.

  1. 2024Stabilizing Sharpness-aware Minimization Through A Simple Renormalization Strategycited by 8
  2. 2022Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradientscited by 6
  3. 2025Zeroth-Order Optimization Finds Flat Minimacited by 6
  4. 2022A Globally Convergent Evolutionary Strategy for Stochastic Constrained Optimization with Applications to Reinforcement Learningcited by 2
  5. 2024Stochastic Two Points Method for Deep Model Zeroth-order Optimizationcited by 1