On the Second-order Convergence Properties of Random Search Methods

Aurélien Lucchi, Antonio Orvieto, Adamos Solomou

Introduction

In the landscape of modern machine learning, derivative-free optimization (DFO) has become a critical tool for scenarios where gradients are unavailable or prohibitively expensive to compute. Applications range from black-box adversarial attacks on neural networks to complex reinforcement learning environments. While reaching a first-order stationary point (where the gradient is zero) is a well-studied problem, non-convex optimization landscapes are frequently plagued by saddle points. To truly optimize these functions, algorithms must reach a Second-Order Stationary Point (SOSP)—a point where the gradient is zero and the Hessian matrix has no negative eigenvalues.

Traditional random search methods can eventually escape these saddle points, but they often do so with agonizing slowness. This paper investigates the theoretical underpinnings of this inefficiency and proposes a novel solution: Random Search Power Iteration (RSPI).

The primary challenge in high-dimensional non-convex optimization is that at a saddle point, the "escape routes" (directions of negative curvature) represent a tiny fraction of the total available search space. As the dimension $d$ of the problem increases, the probability of a randomly sampled direction aligning with these escape routes vanishes.

The probability of finding a descent direction at a saddle point decreases exponentially as the problem dimension grows.

As shown in the figure above, the probability of achieving a significant decrease in function value in a single step drops exponentially with the problem dimension. This "exponential curse" means that vanilla random search methods, which rely on isotropic sampling, become practically useless for escaping saddle points in high-dimensional spaces (e.g., $d > 100$). The complexity of these methods scales as $O(\kappa^d \epsilon^{-2})$, where $\kappa > 1$.

Targeted Escape via RSPI

To overcome this limitation, the authors introduce RSPI, which replaces blind sampling with a Derivative-Free Power Iteration (DFPI) routine. Instead of hoping to stumble upon a descent direction, DFPI actively approximates the eigenvector corresponding to the most negative eigenvalue of the Hessian.

Crucially, this is achieved without ever explicitly computing or storing the $d \times d$ Hessian matrix. By estimating Hessian-vector products through finite differences of function evaluations, the algorithm can "steer" its search toward the most promising escape directions.

A comparison of search directions at a saddle point: random sampling (left) vs. the targeted DFPI approach (right).

The visual comparison above illustrates the power of this approach. While random sampling (left) explores the space uniformly, DFPI (right) quickly concentrates its search along the axis of negative curvature, allowing for a rapid exit from the saddle point region.

Key Results and Complexity Gains

The shift from random to targeted search results in a massive theoretical and empirical performance leap:

  • Linear Complexity: The authors prove that RSPI achieves a complexity of $O(d \log(d) \epsilon^{-8/3})$. This moves the needle from exponential scaling to near-linear scaling with respect to dimension $d$.
  • Empirical Scaling: In high-dimensional tests ($d=350$), RSPI significantly outperformed Hessian-based methods. While a full Hessian approach might take seconds per iteration due to $O(d^2)$ requirements, RSPI's power iteration approach took only fractions of a second.
  • Robustness: Experiments on classic benchmarks like the Rastrigin function and high-dimensional quadratic/quartic saddle functions confirmed that RSPI consistently escapes points where standard DFO methods like Stochastic Three Points (STP) stall indefinitely.

Conclusion

By decoupling the search for descent directions from the search for curvature information, RSPI provides a scalable framework for second-order derivative-free optimization. While the current implementation focuses on the most negative curvature direction, future work may involve adaptive strategies for sampling radii and the use of multiple candidate directions to further enhance efficiency in noisy or non-smooth landscapes.

Summary updated

BibTeX
@inproceedings{lucchi2021second,
  author = {Aurélien Lucchi and Antonio Orvieto and Adamos Solomou},
  title = {{On the Second-order Convergence Properties of Random Search Methods}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=1oR_gQGp3Rm},
}
Figure