# On the Second-order Convergence Properties of Random Search Methods

arXiv: https://arxiv.org/abs/2110.13265 · HTML: https://mlsanity.com/paper/2110.13265/

## 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 (most cited first, 28 of 28)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Simple random search provides a competitive approach to reinforcement learning](https://mlsanity.com/paper/1803.07055/) (2018)
- [Gradient Descent Can Take Exponential Time to Escape Saddle Points](https://mlsanity.com/paper/1705.10412/) (2017)
- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- [Escaping Saddles with Stochastic Gradients](https://mlsanity.com/paper/1803.05999/) (2018)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [The Power of Normalization: Faster Evasion of Saddle Points](https://mlsanity.com/paper/1611.04831/) (2016)
- [First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time](https://mlsanity.com/paper/1711.01944/) (2017)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [Accelerated Stochastic Power Iteration](https://mlsanity.com/paper/1707.02670/) (2017)
- [A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate](https://mlsanity.com/paper/1409.2848/) (2014)
- [Efficiently avoiding saddle points with zero order methods: No gradients required](https://mlsanity.com/paper/1910.13021/) (2019)
- [Direct-Search for a Class of Stochastic Min-Max Problems](https://mlsanity.com/paper/2102.11386/) (2021)
- [An Accelerated DFO Algorithm for Finite-sum Convex Functions](https://mlsanity.com/paper/2007.03311/) (2020)
- [On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization](https://mlsanity.com/paper/1709.08571/) (2017)

## Built on by (most cited first, 5 of 5)

- [Stabilizing Sharpness-aware Minimization Through A Simple Renormalization Strategy](https://mlsanity.com/paper/2401.07250/) (2024)
- [Zeroth-Order Negative Curvature Finding: Escaping Saddle Points without Gradients](https://mlsanity.com/paper/2210.01496/) (2022)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [A Globally Convergent Evolutionary Strategy for Stochastic Constrained Optimization with Applications to Reinforcement Learning](https://mlsanity.com/paper/2202.10464/) (2022)
- [Stochastic Two Points Method for Deep Model Zeroth-order Optimization](https://mlsanity.com/paper/2402.01621/) (2024)

## 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.