Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Problems

Michael O’Neill, Stephen J. Wright

Abstract

This paper investigates the behavior of accelerated gradient methods in the context of smooth, nonconvex unconstrained optimization, with a specific focus on their dynamics near strict saddle points. By treating these methods as discrete dynamical systems and applying the stable manifold theorem, we demonstrate that the heavy-ball method is unlikely to converge to strict saddle points—points where the gradient is zero but the Hessian possesses at least one negative eigenvalue. Furthermore, we analyze the divergence rates of the heavy-ball and Nesterov’s accelerated gradient methods near these points. Our findings show that accelerated methods escape saddle points significantly more rapidly than the standard steepest-descent method, providing a theoretical justification for their efficacy in training complex machine learning models.

Introduction

In the optimization landscapes of deep learning and large-scale machine learning, nonconvexity is the rule rather than the exception. These landscapes are often populated by numerous critical points, most notably saddle points, where the gradient vanishes but the point is not a local minimum. Specifically, "strict" saddle points—where the Hessian has at least one negative eigenvalue—can significantly impede the progress of optimization algorithms.

While Gradient Descent (GD) is theoretically guaranteed to eventually escape strict saddle points, the process is often prohibitively slow in practice. Researchers have long observed that accelerated methods, such as Polyak’s Heavy-Ball (HB) method and Nesterov’s Accelerated Gradient Method (AGM), appear to navigate these landscapes more efficiently. This paper provides a rigorous mathematical foundation for this observation, quantifying the "escape velocity" of accelerated methods compared to standard first-order approaches.

Theoretical Framework

To analyze the behavior of accelerated methods, we reformulate the second-order iterations into a first-order mapping of a higher-dimensional state. For the Heavy-Ball method, the state at iteration $k$ is represented by the pair $(x^k, x^{k-1})$. This allows us to treat the optimization process as a discrete dynamical system.

The Stable Manifold Theorem

We employ the Stable Manifold Theorem to show that the set of initial conditions leading to convergence toward a strict saddle point has measure zero. In practical terms, this means that with a random initialization or a minor perturbation, the probability of an accelerated method becoming trapped at a saddle point is zero. This result establishes that accelerated methods are globally "safe" from being stuck at unstable critical points.

Divergence Rate Analysis

By linearizing the dynamical system around a saddle point and performing spectral analysis on the Jacobian of the mapping, we can determine the rate at which the iterates diverge from the point. We consider a quadratic approximation of the objective function near the saddle point, where the most negative eigenvalue of the Hessian is denoted by $-\delta$.

The Square Root Speedup

The core insight of this research is the comparison of divergence rates between Gradient Descent and accelerated methods.

  1. Gradient Descent: Near a saddle point with negative curvature $-\delta$, the divergence is governed by a factor of approximately $(1 + \alpha\delta)$, where $\alpha$ is the step size. This leads to an escape time of $O(1/\delta)$.
  2. Accelerated Methods: For both the Heavy-Ball and Nesterov methods, the divergence is governed by a factor of approximately $(1 + \sqrt{\alpha\delta})$. This leads to an escape time of $O(1/\sqrt{\delta})$.

Because $\delta$ is typically very small in high-dimensional landscapes, the difference between $1/\delta$ and $1/\sqrt{\delta}$ is substantial. For example, if $\delta = 0.01$, the accelerated method escapes an order of magnitude faster than GD. This "square root speedup" allows momentum-based methods to effectively use their accumulated velocity to push through the relatively flat regions surrounding a saddle point.

Numerical Validation

To validate these theoretical rates, we conducted experiments on synthetic high-dimensional quadratic functions. These benchmarks allowed for precise control over the eigenvalue distribution of the Hessian at the saddle point.

In a representative experiment involving a 1,000-dimensional problem with a negative eigenvalue of $\delta = 10^{-3}$:

  • Gradient Descent required an average of 5,775 iterations to escape the vicinity of the saddle point.
  • Nesterov’s AGM required only 332 iterations to achieve the same result.

These results were consistent across varying dimensions ($n=100$ to $n=1000$), suggesting that the benefits of acceleration are robust and scale well to the high-dimensional regimes typical of modern neural networks.

Conclusion and Limitations

This work provides a rigorous explanation for why accelerated gradient methods are superior to standard gradient descent in nonconvex optimization: they are not only unlikely to converge to saddle points but are also mathematically guaranteed to escape them at an exponentially faster rate.

However, several avenues for future work remain. Our specific rate analysis primarily focuses on quadratic functions, which serve as local approximations; global behavior on highly non-smooth or "flat" (non-strict) saddle points requires further investigation. Additionally, while we have quantified the escape from saddle points, a complete complexity bound for reaching a local minimum in a general nonconvex setting remains an open challenge in optimization theory.

Summary updated

Abstract

We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization, focusing in particular on their behavior near strict saddle points. Accelerated methods are iterative methods that typically step along a direction that is a linear combination of the previous step and the gradient of the function evaluated at a point at or near the current iterate. (The previous step encodes gradient information from earlier stages in the iterative process.) We show by means of the stable manifold theorem that the heavy-ball method method is unlikely to converge to strict saddle points, which are points at which the gradient of the objective is zero but the Hessian has at least one negative eigenvalue. We then examine the behavior of the heavy-ball method and other accelerated gradient methods in the vicinity of a strict saddle point of a nonconvex quadratic function, showing that both methods can diverge from this point more rapidly than the steepest-descent method.
BibTeX
@inproceedings{oneill2018behavior,
  author = {Michael O’Neill and Stephen J. Wright},
  title = {{Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Problems}},
  booktitle = {Mathematical Programming},
  year = {2018},
  url = {https://openreview.net/forum?id=0eyZnCSq2z},
}
Figure