A Deterministic Approach to Avoid Saddle Points.

Lisa Maria Kreusser, Stanley J. Osher, Bao WangarXiv 2019 · OpenReview

TL;DR

Training deep neural networks is often slowed down by saddle points, which standard gradient descent algorithms can easily get trapped in. This paper introduces Modified Laplacian Smoothing Gradient Descent (mLSGD), a deterministic, first-order optimization method that dynamically rotates the gradient direction to shrink the "attraction region" of saddle points. For canonical quadratic functions, mLSGD slashes the dimension of this trap zone from $n-1$ to $\lfloor (n-1)/2 \rfloor$ without sacrificing the overall convergence speed.

What Problem Does This Paper Address?

Nonconvex optimization landscapes—the mathematical terrains we navigate when training modern machine learning models—are riddled with saddle points. While gradient descent (GD) is highly effective at finding stationary points, it can easily get stuck at strict saddle points if it is initialized within their "attraction region" (the stable manifold of initial guesses that lead directly to the saddle point).

Current workarounds to escape or avoid these traps usually rely on adding stochastic noise (such as in Stochastic Gradient Descent or perturbed GD variants) or calculating expensive high-order geometric information (like Hessian matrices). The authors of this paper tackle a fundamental question: Can we avoid saddle points deterministically using only first-order (gradient) information?

Methods

The authors build upon a recently proposed technique called Laplacian Smoothing Gradient Descent (LSGD). Standard LSGD pre-multiplies the gradient by a smoothing matrix $(I - \sigma L)^{-1}$, where $L$ is the discrete one-dimensional Laplacian matrix and $\sigma$ is a fixed positive constant.

The core innovation of this paper is Modified LSGD (mLSGD). Instead of keeping $\sigma$ constant, mLSGD introduces an iteration-dependent function, $\sigma(k)$ (for example, $\sigma(k) = \frac{k+1}{k+2}$).

By varying $\sigma(k)$ dynamically over time, the algorithm non-uniformly perturbs the gradient structure at each step. This time-dependence forces the eigenvectors of the preconditioned system to continuously rotate, making it mathematically difficult for the optimization path to remain trapped within the stable manifold of a saddle point.

Datasets

Not discussed in the paper. Because this is a theoretical and foundational optimization paper, the authors evaluate their approach using synthetic, canonical quadratic functions ($f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T \mathbf{B}\mathbf{x}$) to rigorously analyze the geometry of the attraction regions rather than benchmarking on standard empirical datasets.

Key Insights and Ideas

  • Gradient Rotation vs. Rescaling: Standard GD and regular LSGD merely rescale the gradient along fixed coordinate axes or eigenvectors. By making $\sigma$ time-dependent, mLSGD actively rotates the underlying eigenvectors of the smoothing operator at each iteration.
Figure 1: The attraction region when LSGD is applied to f(x) = 1
  • Shrinking the Trap Zone: For a canonical class of quadratic functions in $n$ dimensions, the dimension of the attraction region drops dramatically from $n-1$ (under standard GD) to $\lfloor (n-1)/2 \rfloor$ (under mLSGD).
  • The 2D Miracle: In a two-dimensional setting, the attraction region shrinks to the trivial set $\{0\}$. This implies that from virtually any non-zero starting point, the deterministic algorithm will naturally steer away from the saddle point.

Key Results

  • Theoretical Dimension Reduction: The authors rigorously prove that mLSGD significantly reduces the dimensionality of the initial data space that can lead to a saddle point.
  • Preserved Convergence Rate: The authors prove that mLSGD maintains an $O(1/\epsilon^2)$ iteration complexity for $\ell$-smooth nonconvex functions. This matches the standard convergence rate of gradient descent, meaning you gain saddle-point avoidance without paying a speed penalty.
  • Numerical Verification: Two-dimensional grid searches confirm the theory: while standard GD gets trapped along specific lines, mLSGD successfully alters its trajectory step-by-step to bypass the saddle point and head toward the true minimizer.

Limitations and Future Work

  • Degenerate Hessians: The current formulation of mLSGD cannot resolve degenerate saddle points—areas where at least one eigenvalue of the Hessian matrix is exactly zero. In these flat regions, the algorithm can still stall.
  • Sensitivity to Coordinate Alignment: The reduction of the attraction region depends on the structure of the Hessian matrix. For certain specific coordinate-aligned functions (like $f(x_1, x_2) = x_1 x_2$), the current version of mLSGD does not inherently shrink the attraction region without further modification.
  • Future Directions: The authors note that extending mLSGD to more general objective functions and combining Laplacian smoothing with stochastic perturbations are promising avenues for creating even more robust optimization algorithms.

Summary updated

Abstract

Loss functions with a large number of saddle points are one of the major obstacles for training modern machine learning models efficiently. First-order methods such as gradient descent are usually the methods of choice for training machine learning models. However, these methods converge to saddle points for certain choices of initial guesses. In this paper, we propose a modification of the recently proposed Laplacian smoothing gradient descent [Osher et al., arXiv:1806.06317], called modified Laplacian smoothing gradient descent (mLSGD), and demonstrate its potential to avoid saddle points without sacrificing the convergence rate. Our analysis is based on the attraction region, formed by all starting points for which the considered numerical scheme converges to a saddle point. We investigate the attraction region's dimension both analytically and numerically. For a canonical class of quadratic functions, we show that the dimension of the attraction region for mLSGD is floor((n-1)/2), and hence it is significantly smaller than that of the gradient descent whose dimension is n-1.
BibTeX
@misc{kreusser2019deterministic,
  author = {Lisa Maria Kreusser and Stanley J. Osher and Bao Wang},
  title = {{A Deterministic Approach to Avoid Saddle Points.}},
  year = {2019},
  eprint = {1901.06827},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1901.06827},
}
Figure