Faster Gradient-Free Methods for Escaping Saddle Points

Hualin Zhang, Bin GuICLR 2023 · OpenReview

TL;DR

This paper introduces two new zeroth-order (gradient-free) optimization algorithms that leverage Nesterov’s acceleration to escape saddle points faster than previous methods. By using clever finite-difference estimators for gradients and Hessian-vector products, the authors achieve a state-of-the-art oracle complexity of $\tilde{O}(d/\epsilon^{1.75})$ for finding second-order stationary points in non-convex landscapes.

What Problem Does This Paper Address?

In many modern machine learning scenarios—such as black-box adversarial attacks, reinforcement learning policy searches, and hyperparameter tuning—we don't have access to the explicit gradient of a loss function. We only have "zeroth-order" access: we can plug in an input and get a function value, but we can't see the underlying slope.

Optimizing these "black-box" non-convex functions is notoriously difficult because of saddle points. These are regions where the gradient is zero, but the point is not a local minimum (think of the middle of a literal horse saddle). Simple algorithms often get stuck or crawl extremely slowly through these regions. While first-order methods (which use gradients) have used Nesterov’s Accelerated Gradient Descent (AGD) to "speed jump" over these hurdles, it wasn't clear if or how AGD could be adapted to a gradient-free setting to achieve similar speedups.

Methods

The authors propose two main algorithms that adapt Nesterov’s momentum to the zeroth-order regime:

  1. Zeroth-Order Perturbed AGD: This method combines three components:
  2. Central Finite Difference Estimator: Instead of a true gradient, it estimates the slope by querying function values at small offsets in every dimension.
  3. Random Perturbation: When the algorithm detects it is stuck in a flat region (a potential saddle point), it adds a small amount of random noise to "kick" the iterate into a direction that might have negative curvature.
  4. Negative Curvature Exploitation: A specific step to ensure the "Hamiltonian" (a combination of function value and momentum) decreases monotonically.
  5. Zeroth-Order Perturbed AGD with Accelerated Negative Curvature Finding:
    • This is a more sophisticated version that doesn't just rely on random luck to escape a saddle.
  6. It uses a Zeroth-Order Hessian-Vector Product Estimator. By taking the difference of two gradient estimators, the algorithm can approximate how the curvature changes without ever calculating a second derivative. This allows it to explicitly find the direction of steepest descent away from the saddle point.

Datasets

As a theoretical optimization paper, the authors evaluate their algorithms on synthetic but mathematically challenging non-convex "benchmark" functions:

  • Cubic Regularization Problem: A standard test case designed to have difficult saddle points that become harder to navigate as the dimension ($d$) increases.
  • Quartic Function: A landscape with a strict saddle point at the origin and two global minima, used to test how quickly an algorithm can decide which way to "fall" off the saddle.

Key Insights and Ideas

  • The Power of Central Differences: The authors prove that under the assumption of a Lipschitz continuous Hessian, the central difference estimator has a much lower approximation error than the simpler forward difference estimator used in prior work.
  • Momentum is a Double-Edged Sword: In non-convex settings, momentum can actually make you stay near a saddle point longer if not managed. The "Hamiltonian" function is the key insight used to monitor and guarantee that the algorithm is actually making progress.
  • Bridging the Gap: The most significant insight is that zeroth-order methods can achieve the same $\epsilon^{-1.75}$ convergence rate as first-order accelerated methods. This suggests that the "penalty" for not having gradients is primarily a factor of the dimension ($d$), not a fundamental slowdown in the convergence rate itself.

Key Results

  • Theoretical Speedup: The proposed methods reach an $\epsilon$-approximate second-order stationary point (SOSP) in $\tilde{O}(d/\epsilon^{1.75})$ function queries. This is a massive improvement over earlier zeroth-order methods like ZPSGD, which required $\tilde{O}(d^2/\epsilon^5)$ queries.
  • Dimension Efficiency: By using accelerated negative curvature finding, the more advanced algorithm reduces the dependence on the dimension $d$ compared to purely perturbation-based methods.
  • Empirical Performance: In simulations, the new algorithms escaped saddle points in significantly fewer iterations and with fewer total function queries than existing baselines like PAGD (Perturbed Approximate Gradient Descent).
Convergence comparison showing the proposed zeroth-order accelerated methods escaping saddle points faster than the baseline.

Limitations and Future Work

  • Dimension Scaling: While the rate is improved, the complexity still scales linearly with the dimension $d$. In extremely high-dimensional spaces (millions of parameters), zeroth-order methods remain computationally expensive because each "gradient" estimate requires $2d$ function queries.
  • Smoothness Assumptions: The proofs rely on the function being "Hessian Lipschitz," meaning the curvature doesn't change too abruptly. While common in theory, some real-world deep learning surfaces might be more "jagged."
  • Real-World Application: The paper focuses on theoretical benchmarks. A natural next step would be applying these specific accelerated variants to large-scale black-box reinforcement learning tasks to see if the theoretical gains translate to faster training of agents.

Summary updated

Abstract

Escaping from saddle points has become an important research topic in non-convex optimization. In this paper, we study the case when calculations of explicit gradients are expensive or even infeasible, and only function values are accessible. Currently, there have two types of gradient-free (zeroth-order) methods based on random perturbation and negative curvature finding proposed to escape saddle points efficiently and converge to an $\epsilon$-approximate second-order stationary point. Nesterov's accelerated gradient descent (AGD) method can escape saddle points faster than gradient descent (GD) which have been verified in first-order algorithms. However, whether AGD could accelerate the gradient-free methods is still unstudied. To unfold this mystery, in this paper, we propose two accelerated variants for the two types of gradient-free methods of escaping saddle points. We show that our algorithms can find an $\epsilon$-approximate second-order stationary point with $\tilde{\mathcal{O}}(1/\epsilon^{1.75})$ iteration complexity and $\tilde{\mathcal{O}}(d/\epsilon^{1.75})$ oracle complexity, where $d$ is the problem dimension. Thus, our methods achieve a comparable convergence rate to their first-order counterparts and have fewer oracle complexity compared to prior derivative-free methods for finding second-order stationary points.
BibTeX
@inproceedings{zhang2023faster,
  author = {Hualin Zhang and Bin Gu},
  title = {{Faster Gradient-Free Methods for Escaping Saddle Points}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=KDhFkA6MQsW},
}
Figure