Source-linked AI summary
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
Yann Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, Yoshua Bengio
TL;DR
High-dimensional non-convex optimization is hindered by proliferating saddle points and their slow, plateau-like regions, rather than primarily by high-error local minima. The paper develops saddle-free Newton as a curvature-based second-order approach that rapidly escapes saddles, and reports superior optimization performance in deep and recurrent neural-network settings.
Problem
High-dimensional non-convex error surfaces contain many saddle points surrounded by plateaus that can slow gradient-based learning, while high-error local minima are not the central difficulty.
Method
The paper develops generalized trust-region methods and derives saddle-free Newton, which rescales gradients using the absolute values of Hessian eigenvalues.
Results
The saddle-free Newton method provides numerical evidence of superior optimization performance and achieves mean squared error 0.57 versus 0.69 for Hessian-Free on one reported task.
Takeaways & Limitations
Saddle-free Newton offers a second-order optimization approach that can rapidly escape high-dimensional saddle points, including weak negative-curvature directions.
Takeaways & Limitations
Natural-gradient approaches can be limited by negative curvature and rank-deficient Fisher matrices, while methods that ignore negative curvature cannot escape saddle points.
Abstract
from arXiv · showhide
A central challenge to many fields of science and engineering involves minimizing non-convex error functions over continuous, high dimensional spaces. Gradient descent or quasi-Newton methods are almost ubiquitously used to perform such minimizations, and it is often thought that a main source of difficulty for these local methods to find the global minimum is the proliferation of local minima with much higher error than the global minimum. Here we argue, based on results from statistical physics, random matrix theory, neural network theory, and empirical evidence, that a deeper and more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest. Such saddle points are surrounded by high error plateaus that can dramatically slow down learning, and give the illusory impression of the existence of a local minimum. Motivated by these arguments, we propose a new approach to second-order optimization, the saddle-free Newton method, that can rapidly escape high dimensional saddle points, unlike gradient descent and quasi-Newton methods. We apply this algorithm to deep or recurrent neural network training, and provide numerical evidence for its superior optimization performance.
1 Introduction
In high-dimensional non-convex optimization, saddle points proliferate and can impede local methods more profoundly than high-error local minima. Their surrounding low-curvature plateaus slow gradient descent, while Newton dynamics can make saddles attractive.
- High-dimensional random error functions increasingly contain saddle points rather than local minima as dimensionality grows.
- Saddle points and local minima are often surrounded by low-curvature plateaus that slow gradient descent.Gradient descent is repelled from saddles along negative-curvature directions, but plateau curvature can make this escape slow.
- Newton’s method can turn saddle points into attractive points instead of rapidly descending away from them.
- The paper proposes a second-order method designed to escape saddle points and reports that it outperforms quasi-Newton methods in some high-dimensional network problems.
2 The prevalence of saddle points in high dimensions
Statistical physics and random matrix theory predict that high-dimensional error landscapes contain many saddle points, while high-error local minima are exponentially rare. Neural-network theory provides qualitatively consistent examples involving saddle-point structures and slow learning.
- Critical points concentrate along an increasing error–index curve, so higher-error critical points tend to have more negative-curvature directions.Here, index α is the fraction of negative Hessian eigenvalues, and error is denoted ϵ.
- Random-matrix analysis explains the trend because Hessian eigenvalues are centered near zero, making all-positive spectra increasingly unlikely as dimensions grow.
- High-error local minima are exponentially rare in dimensionality, whereas saddle points with many negative and approximate plateau directions are exponentially likely.
- A single-linear-hidden-layer multilayer perceptron has saddle points but no local minima, consistent with the high-dimensional landscape prediction.
- Symmetric weight-space submanifolds and indefinite Hessians provide neural-network examples of saddle-point structures associated with slow learning.
3 Experimental validation of the prevalence of saddle points
Experiments on small neural networks test whether random-Gaussian-field predictions extend to practical error surfaces. The measured critical-point and Hessian patterns qualitatively support those predictions.
- The experiments measured critical-point distributions and Hessian eigenvalues in small MLPs trained on down-sampled MNIST and CIFAR-10.Newton’s method was used to identify critical points.
- Critical points in neural-network error surfaces concentrate along a monotonically increasing curve in the ϵ–α plane.
- The empirical test confirms that Bray and Dean’s qualitative observations for random Gaussian fields hold for neural networks.
- As error increases, Hessian eigenvalue distributions shift left, while a large mode at zero indicates plateaus around critical points.
4 Dynamics of optimization algorithms near saddle points
Near saddle points, gradient descent escapes in the correct directions but can move slowly, while Newton-type methods may move toward saddles or suppress the negative-curvature directions needed for escape.
- Local saddle-point analysis: Morse’s lemma provides a local re-parameterization for analyzing non-degenerate saddle points whose Hessians are not singular.This supplies the local coordinate framework for comparing optimization dynamics near saddles.
- Gradient descent: Gradient descent moves toward a saddle along positive-curvature directions and away along negative-curvature directions, but takes small steps when eigenvalues have small absolute value.Its limitation is step size rather than direction, producing slow escape across low-curvature plateaus.
- Newton method: Newton’s inverse-eigenvalue rescaling removes gradient-step slowness but reverses the direction along negative-curvature eigenvectors, making the saddle an attractor.The Newton step moves toward the saddle along both positive- and negative-curvature directions.
- Damping and trust regions: Trust-region damping must make λ_min + α > 0 to ensure descent in every eigen-direction, which can shrink steps in many directions.A large damping coefficient is required even when only the most negative curvature direction demands correction.
- Negative-curvature handling: Ignoring negative curvature, as in truncated Newton or BFGS-style approaches, prevents algorithms from following the directions required to escape saddle points.This limitation applies regardless of the approximation strategy used for the Newton method.
- Natural gradient methods: Natural gradient methods use the Fisher matrix F rather than the Hessian, but rank deficiency and a large Hessian–Fisher difference can make their directions ineffective near some saddles.TONGA can also take excessively large steps near critical points because gradient covariance vanishes there.
5 Generalized trust region methods
Generalized trust-region methods extend classical trust regions by varying both the Taylor approximation order and the distance constraint, thereby defining a family of algorithms.
- Generalized trust-region design: The generalized trust-region class replaces the fixed second-order model with a first- or second-order Taylor expansion and replaces step-norm constraints with distance constraints.The selected Taylor order and distance function specify the resulting algorithm.
- Special case: The α-damped Newton method is a special case with k = 2 and d(θ, θ + ∆θ) = ||∆θ||2.It uses a second-order Taylor model and the Euclidean norm of the parameter step.
6 Attacking the saddle point problem
The paper develops saddle-free Newton as a curvature-aware trust-region method that preserves gradient signs to escape saddle points, with an approximate implementation for high-dimensional problems.
- Saddle-free Newton: Saddle-free Newton rescales gradients by the inverse absolute Hessian eigenvalues, preserving gradient signs so saddle points become repellers.This differs from Newton’s treatment of signed curvature and targets rapid escape from saddle points.
- Generalized trust region: The method minimizes a first-order Taylor approximation within a curvature-defined trust region rather than using a second-order Taylor expansion.The trust-region boundary is reached because the first-order approximation has its minimum at infinity.
- Generalized trust region: The trust-region distance incorporates Hessian curvature, and its discrepancy constraint is replaced by an upper bound involving |H| to make the problem tractable.Lemma 1 provides the bound used to formulate the generalized trust-region method.
- Optimization step: The resulting SFN step is Δθ = −∇f|H|−1 up to a learning-rate scalar, with the constraint solution obtained using Lagrange multipliers.The algorithm jumps to the trust-region border, and the scalar factor is absorbed into the learning rate.
- Optimization behavior: SFN matches Newton when the Hessian is positive definite, while escaping saddle points rapidly even along directions of weak negative curvature.Unlike gradient descent, it moves farther in low-curvature directions and less in high-curvature directions.
- Approximate implementation: Because exact Hessian computation is intractable in high dimensions, the implementation optimizes in a Lanczos-generated Krylov subspace spanning dominant Hessian eigenvectors with high probability.The reduced-space procedure uses k Krylov vectors and an eigendecomposition of the projected Hessian.
7 Experimental validation of the saddle-free Newton method
Experiments across scaled-down and large neural-network problems show that saddle-free Newton escapes regions where SGD and conventional Newton methods stall, improving optimization as problem size grows.
- Small-network validation: The experiments compare MSGD, damped Newton, and saddle-free Newton on downsampled MNIST and CIFAR-10 networks with exact update directions.Damping was used for numerical stability, and hyperparameters were selected through random search or small candidate sets.
- Small-network validation: As network size increases, saddle-free Newton outperforms the other algorithms by a large margin, whereas the smallest network shows comparable performance.This pattern is consistent with the predicted increase in saddle points with dimensionality.
- Small-network validation: Saddle-free Newton escapes, or avoids becoming trapped near, saddle points where SGD and Newton appear stuck during optimization.In the MNIST experiment, rapid escape is especially visible at the 10-th epoch.
- Deep autoencoder: For the seven-hidden-layer MNIST autoencoder, SGD stalls at MSE 1.0, after which saddle-free Newton rapidly escapes the approximate plateau.The eigenvalue distribution shifts right as error decreases, and saddle-free Newton accelerates that shift.
- Deep autoencoder: The autoencoder reaches MSE 0.57 with SGD followed by saddle-free Newton, compared with MSE 0.69 from the previous Hessian-Free method.The reported result is identified as state-of-the-art in the passage.
- Recurrent neural network: In the Penn Treebank recurrent-network experiment, error drops significantly after saddle-free Newton begins, and its solution has fewer negative eigenvalues than the SGD solution.Continuing with truncated Newton with damping did not substantially improve the stalled SGD training.
8 Conclusion
The paper concludes that high-dimensional non-convex landscapes are dominated by saddle points rather than high-error local minima, motivating saddle-free Newton and further work on scalable curvature methods.
- Conclusion: High-dimensional non-convex error surfaces generically contain many saddle points, while high-error local minima are exponentially rare.The conclusion draws on statistical physics, random matrix theory, and neural-network theory.
- Conclusion: Experiments measuring neural-network critical points support the predicted positive relationship between critical-point index and error level.Index is defined as the fraction of negative Hessian eigenvalues.
- Conclusion: The saddle-free Newton method rescales gradients using the absolute inverse Hessian and is derived through generalized trust-region methods.The approach is intended to combine rapid saddle-point escape with Newton-style plateau descent while avoiding their respective pitfalls.
- Conclusion: The method achieves improved optimization on several neural-network training problems and is argued to remain sensible even far from saddle points.The paper presents this as the practical outcome of the generalized trust-region formulation.
- Future work: Future work includes scaling saddle-free Newton beyond Krylov subspaces when the full Hessian cannot be computed and further analyzing neural-network critical points.The authors also anticipate that understanding high-dimensional error surfaces may guide new non-convex optimization algorithms.
D Proof of Lemma 1
The lemma bounds the magnitude of a quadratic form involving a nonsingular matrix by the corresponding quadratic form formed from the matrix’s absolute eigenvalues.
- Lemma: For nonsingular square A and vector x, the lemma states |x⊤Ax| ≤ x⊤|A|x.Here |A| is obtained by replacing each eigenvalue of A with its absolute value.
- Proof: The proof rewrites the identity in the eigenvector basis of A using its eigenvalues.The subsequent bound follows by applying the triangle inequality.
E Implementation details for approximate saddle-free Newton
The approximate saddle-free Newton implementation constructs a Krylov subspace from gradient and curvature information, reuses Hessian computations, and performs optimization within that subspace.
- Krylov construction: The Krylov subspace is generated by a modified Lanczos process initialized with the model gradient and augmented with the previous search direction.This supplies the low-dimensional basis used for approximate curvature calculations.
- Krylov construction: During Lanczos iterations, Hessian-vector products are used to construct the subspace vectors and coefficients.The displayed procedure normalizes successive residual vectors to obtain the next basis vector.
- Curvature computation: The Hessian in the subspace can be computed more efficiently by memorizing the Lanczos vectors and reusing matrix products.This avoids recomputing quantities already obtained during the Lanczos process.
- Subspace optimization: Multiple optimization steps are performed within the same subspace without recomputing the Hessian, assuming that the Hessian changes little during those steps.This is an implementation assumption that trades refreshed curvature for computational efficiency.
- Algorithm: Algorithm 2 summarizes the Lanczos-vector construction used by the approximate method.The procedure iteratively updates basis vectors through gradient initialization, Hessian operations, orthogonalization coefficients, and normalization.
F Experiments
The experiments tune SGD and second-order optimization settings separately for feedforward and recurrent networks. Recurrent-network Hessian spectra are approximated in a Krylov subspace because exact Hessian computation is costly.
- Feedforward networks: SGD hyperparameters for feedforward networks were selected by random search over learning rate, minibatch size, and momentum coefficient.The search drew 80 samples and retained the best configuration.
- Second-order methods: The damping coefficient for Newton and saddle-free Newton methods was chosen at each update to maximize improvement.
- Deep auto-encoder: The deep auto-encoder was pretrained using the Sutskever et al. protocol and classical momentum.
- Recurrent networks: The RNN used orthogonal recurrent-weight initialization, 120 hidden units, and random-search tuning of learning rate, gradient-clipping threshold, and momentum.The random search drew 64 samples and selected the best one.
- Recurrent-network analysis: The gradient and saddle-free update step were clipped when exceeding a threshold, while RNN Hessian eigenvalue distributions were estimated from a Krylov subspace.The approximation was used for Figure 4(d) because computing the exact RNN Hessian is costly.