Source-linked AI summary
Equilibrated adaptive learning rates for non-convex optimization
Yann N. Dauphin, Harm de Vries, Yoshua Bengio
TL;DR
Large neural networks require scalable adaptive learning rates, yet their non-convex objectives often involve saddle points and indefinite Hessians. The paper analyzes diagonal preconditioners, proposes ESGD from equilibration, and reports performance as good as or better than RMSProp while improving over SGD.
Problem
Scalable adaptive learning rates must address ill-conditioning in large neural networks whose non-convex objectives commonly encounter saddle points and indefinite Hessians.
Method
The paper analyzes diagonal preconditioners, argues that equilibration is better suited than Jacobi to mixed curvature, and builds the ESGD adaptive learning-rate schedule.
Results
ESGD empirically performed as well or better than RMSProp and clearly improved over plain SGD; on MNIST it reached 0.86 training MSE and was approximately three times faster than baseline SGD.
Takeaways & Limitations
Equilibration provides a computationally practical adaptive-learning-rate approach for non-convex optimization and may help explain RMSProp’s successful update directions.
Takeaways & Limitations
The jointly row-and-column equilibration procedure did not work well in an online optimization setting, and the authors state that more research is required to confirm their results.
Abstract
from arXiv · showhide
Parameter-specific adaptive learning rate methods are computationally efficient ways to reduce the ill-conditioning problems encountered when training large deep networks. Following recent work that strongly suggests that most of the critical points encountered when training such networks are saddle points, we find how considering the presence of negative eigenvalues of the Hessian could help us design better suited adaptive learning rate schemes. We show that the popular Jacobi preconditioner has undesirable behavior in the presence of both positive and negative curvature, and present theoretical and empirical evidence that the so-called equilibration preconditioner is comparatively better suited to non-convex problems. We introduce a novel adaptive learning rate scheme, called ESGD, based on the equilibration preconditioner. Our experiments show that ESGD performs as well or better than RMSProp in terms of convergence speed, always clearly improving over plain stochastic gradient descent.
1 Introduction
Deep-network optimization is difficult because objectives are large, non-convex, and often ill-conditioned near saddle points. The paper studies adaptive diagonal preconditioners and proposes ESGD using equilibration.
- Training neural networks involves optimizing non-convex objectives over millions of parameters, making full Hessian-based methods impractical.Parameter-specific diagonal preconditioners are therefore considered viable adaptive-learning-rate alternatives.
- Saddle points are suggested to dominate optimization paths, where flat directions and ill-conditioning can substantially slow training.This motivates exploiting saddle structure when designing computationally efficient preconditioners.
- The paper finds Jacobi unsuitable for mixed positive and negative curvature and proposes equilibration as a better-suited preconditioner for non-convex optimization.It introduces ESGD, an adaptive SGD schedule based on equilibration, and evaluates it on deep autoencoder benchmarks.
2 Preconditioning
Preconditioning transforms the optimization geometry to reduce curvature disparities, but non-convex Hessians can be indefinite, limiting standard positive-semidefinite constructions. The inverse absolute Hessian gives ideal conditioning, while diagonal approximations are needed for scalability.
- Ill-conditioned curvature forces gradient descent to use steps small enough for high-curvature directions, slowing progress in low-curvature directions.This mechanism explains the slow convergence of first-order methods.
- Preconditioning changes variables so the transformed Hessian has more equal curvature across directions, reducing oscillations and accelerating saddle-point escape.The transformed curvature is represented by D^(-1/2)⊤ H D^(-1/2).
- Non-convex loss surfaces may have indefinite Hessians, so H^(-1) is not a valid preconditioner and an unmodified Newton step can move toward a saddle point.Preconditioning remains useful because reducing ill-conditioning around saddles can speed gradient descent.
- The inverse absolute Hessian perfectly conditions the transformed Hessian and is obtained by eigendecomposition followed by taking absolute eigenvalue values.It is the only symmetric positive definite preconditioner that reduces the condition number to 1.
- Full Hessian storage, eigendecomposition, and inversion are computationally infeasible for million-parameter networks, motivating diagonal preconditioners with linear-time operations.The cited costs are O(N^2) for storage and O(N^3) for eigendecomposition and inversion.
3 Related work
Related work includes Jacobi, AdaGrad, RMSProp, and AdaDelta as efficient adaptive methods, but their theoretical suitability to non-convex neural-network optimization remains limited or unclear.
- The Jacobi preconditioner uses the element-wise absolute diagonal of the Hessian and can be approximated efficiently with the Gauss–Newton matrix.The passage notes that the approximation may lose information and that Jacobi has not been competitive for indefinite problems.
- AdaGrad adapts diagonal learning rates from accumulated gradients, but its justification relies strongly on convexity.This creates a theoretical difficulty for applying it to neural networks.
- RMSProp and AdaDelta were introduced as practical adaptive methods for training large neural networks, with RMSProp reported to work very well.The supplied passage does not establish their full theoretical behavior in non-convex settings.
4 Equilibration
Equilibration scales matrix rows to reduce disparities in magnitude and offers theoretical and empirical support for improving conditioning, especially for indefinite matrices. The method is approximated matrix-free for neural-network use.
- Equilibration: Row equilibration scales each matrix row to unit 2-norm by left-multiplying with a diagonal matrix whose entries are inverse row norms.This technique originated in numerical mathematics to reduce round-off errors in linear-system solution.
- Equilibration: The transformed Hessian used in optimization has the same spectrum as row- and column-equilibrated Hessians, linking its conditioning to equilibration.Therefore, successful row equilibration reduces the transformed Hessian’s condition number by the same amount.
- Implementation: An iterative procedure for jointly row-and-column equilibrating the transformed Hessian did not work well online, so the authors retained the original equilibration matrix.This is an implementation boundary for the proposed approach.
- Theory: Row equilibration has a theoretical upper-bound justification, whereas the authors cannot prove that Jacobi improves the corresponding bound.The bound is reduced more when row norms are more varied.
- Experiments: In random neural-network and logistic-regression experiments, equilibration outperforms other methods in non-convex condition-number reduction.Figure 2 reports histograms comparing the ratio before and after preconditioning across sampled models.
- Implementation: A matrix-free unbiased estimator uses Hessian–vector products and can be implemented with gradient-like computations costing about two backpropagations.This avoids storing the Hessian and makes equilibration practical for large neural networks.
5 Equilibrated learning rates are well suited to non-convex problems
The paper argues that equilibration is better suited than Jacobi preconditioning to indefinite, non-convex curvature because it avoids curvature cancellation and overly large steps. Experiments show a clear advantage for equilibration in non-convex settings.
- The equilibration preconditioner can be viewed as the Jacobi preconditioner applied to the absolute Hessian.
- The inverse absolute Hessian is the unique symmetric positive definite preconditioner that reduces the condition number to 1.
- Jacobi preconditioning can underestimate curvature when positive and negative eigendirections cancel, producing steps that are too large.
- Equilibration avoids this divergence mechanism because its curvature estimate uses positive squared-Hessian contributions that cannot cancel.
- In random neural-network experiments, equilibration and Jacobi are closely matched for convex problems, but equilibration significantly outperforms other methods for non-convex problems.
6 Implementation
The proposed ESGD algorithm estimates squared-Hessian diagonal curvature with stochastic updates and amortizes the added computation to approach SGD cost. A Jacobi-preconditioned SGD variant provides the comparison baseline.
- ESGD uses equilibration to build a scalable preconditioner for neural networks.
- The method estimates diag(H^2) with an unbiased estimator and updates a running average similarly to RMSProp.
- Updating every 20 iterations brings equilibration's computational cost close to regular SGD, with damping λ = 10^-4 reported as robust across tasks.
- The comparison method estimates the Hessian diagonal with random ±1 vectors and applies it to precondition SGD like ESGD.
- The Jacobi-based method has the same computational complexity as ESGD, while the optimal method depends on the situation.
7 Experimental setup
The experiments target high-dimensional non-convex optimization by training very deep auto-encoders with a low-dimensional bottleneck. Hyperparameters are selected through random search across method-specific ranges.
- The study aims to test whether equilibration differs significantly from Jacobi preconditioning on high-dimensional non-convex problems.
- The benchmark trains very deep auto-encoders to reconstruct inputs while forcing one layer to be very low-dimensional.
- The low-dimensional bottleneck makes reconstruction difficult because the optimizer must finely tune the parameters.
- Hyperparameters are tuned by random search, with separate learning-rate ranges for SGD, ESGD, RMSProp, and Jacobi preconditioning.
8 Results
Experiments compare adaptive preconditioners on deep autoencoders using learning curves and cosine distances between estimated matrices. ESGD performs best overall, while RMSProp’s similarity to equilibration varies across datasets and training.
- ESGD significantly outperforms RMSProp and Jacobi SGD on MNIST, with the performance gap becoming especially notable after 250 epochs.
- 0.86 training MSE is reached by equilibration on MNIST, improving on the 2.1 training MSE reported for SGD without momentum.
- Approximately three times faster convergence is observed than with baseline SGD on MNIST.
- ESGD performs best on CURVES, although its advantage over RMSProp and Jacobi SGD is less significant than on MNIST.
- RMSProp remains around 0.05 from equilibration but differs from Jacobi by about 0.2 on CURVES.
- On MNIST, RMSProp initially estimates equilibration well, then diverges; after 1000 epochs, it no longer matches equilibration and performance drops relative to ESGD.
9 Conclusion
The paper argues that equilibration is better suited than Jacobi preconditioning for saddle-point problems and uses it to construct ESGD. ESGD empirically outperforms RMSProp on two deep autoencoder benchmarks, while further research is needed to confirm the findings.
- Equilibration is theoretically and empirically comparatively better suited than Jacobi preconditioning for indefinite saddle-point problems.
- ESGD is a novel adaptive learning-rate schedule for non-convex optimization based on the equilibration preconditioner.
- ESGD empirically outperforms RMSProp on two competitive deep autoencoder benchmarks.
- RMSProp’s update direction is practically very similar to the equilibrated update direction, offering a possible explanation for its success in training deep neural networks.
- More research is required to confirm these results.