Source-linked AI summary
Online Learning Rate Adaptation with Hypergradient Descent
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, Frank Wood
TL;DR
Gradient-based optimizers depend heavily on learning-rate selection, while adaptive methods still retain a tunable global learning rate. The paper introduces hypergradient descent, which updates the learning rate online using its gradient, and reports improved performance across SGD, Nesterov momentum, and Adam while reducing initial-learning-rate tuning.
Problem
Learning-rate selection remains central to optimization efficiency, and widely used adaptive optimizers still require tuning a fixed global learning-rate hyperparameter.
Method
Hypergradient descent applies gradient descent to the learning rate of an underlying optimizer, updating it online from the objective derivative with respect to that learning rate.
Results
Hypergradient variants of SGD, SGD with Nesterov momentum, and Adam empirically improve their regular versions and reduce the time and resources needed to tune the initial learning rate.
Takeaways & Limitations
For an untuned initial learning rate, hypergradient algorithms consistently bring loss trajectories closer to those achieved with a tuned initial learning rate.
Takeaways & Limitations
The paper's theoretical convergence guarantees are limited, with convergence results and rates for broader hypergradient variants left for future work.
Abstract
from arXiv · showhide
We introduce a general method for improving the convergence rate of gradient-based optimizers that is easy to implement and works well in practice. We demonstrate the effectiveness of the method in a range of optimization problems by applying it to stochastic gradient descent, stochastic gradient descent with Nesterov momentum, and Adam, showing that it significantly reduces the need for the manual tuning of the initial learning rate for these commonly used algorithms. Our method works by dynamically updating the learning rate during optimization using the gradient with respect to the learning rate of the update rule itself. Computing this "hypergradient" needs little additional computation, requires only one extra copy of the original gradient to be stored in memory, and relies upon nothing more than what is provided by reverse-mode automatic differentiation.
1 INTRODUCTION
Learning-rate selection remains a major efficiency bottleneck, even for adaptive optimizers that retain a fixed global learning-rate hyperparameter. Hypergradient descent addresses this by dynamically adapting learning rates and improves several established gradient-based optimizers while reducing tuning demands.
- Learning-rate choice strongly affects how quickly gradient descent reaches a target objective value.Using too large or too small a step can substantially slow descent.
- Adaptive optimizers such as AdaGrad, RMSProp, and Adam still require tuning a fixed global learning-rate hyperparameter.Existing methods that avoid such tuning have not seen widespread adoption, potentially because of complexity, applicability, or performance.
- Hypergradient descent dynamically updates a learning rate using the derivative of the update procedure with respect to that learning rate.The method emerged from an automatic-differentiation perspective and is named for its use of a hypergradient.
- The method adapts SGD, SGD with Nesterov momentum, and Adam, particularly for large-scale neural-network training problems.The paper reports improvements for all three optimizer families.
- For an untuned initial learning rate, hypergradient algorithms consistently move loss trajectories closer to those obtained with a tuned initial learning rate.This reduces reliance on expensive and time-consuming learning-rate hyperparameter search.
2 HYPERGRADIENT DESCENT
Hypergradient descent updates both model parameters and the learning rate online by differentiating the post-update objective with respect to that rate. The method extends to gradient-based optimizers including SGD, Nesterov SGD, and Adam, with low additional memory and computation.
- Core method: HD applies gradient descent to the learning rate of an underlying gradient descent algorithm, updating the parameter and learning-rate sequences online.Unlike reversible learning, it updates the hyperparameter at each iteration rather than differentiating through an entire inner optimization.
- Core method: The hypergradient is the partial derivative of the objective after an update with respect to the learning rate, computed from recent gradient information.For basic HD, the required hypergradient can be computed with a dot product and one extra copy of the original gradient.
- Assumptions: HD assumes that the optimal learning rate changes little between consecutive iterations, using the previous update to approximate the current learning-rate optimum.The stochastic derivation additionally assumes gradient-estimator noise at the current step is independent of noise at previous iterations.
- Learning-rate updates: The multiplicative HD rule is invariant to rescaling and generally adapts faster than the additive rule.The paper presents both additive and multiplicative learning-rate updates, identifying the multiplicative form as usually preferable in practice.
- Algorithmic extensions: Applying the derivation to SGD yields SGD-HD, while corresponding substitutions produce hypergradient variants for Nesterov SGD and Adam.The paper empirically studies these algorithms on logistic regression and multilayer and convolutional neural networks for image classification.
- Empirical scope: For an untuned initial learning rate, hypergradient algorithms consistently move loss trajectories closer to those obtained with a tuned initial rate, reducing the need for learning-rate search.The paper investigates settings for both the hypergradient learning rate β and the initial learning rate α0.
3 RELATED WORK
Related work includes adaptive local learning-rate methods, optimization-based hyperparameter tuning, and online or validation-based hypergradient approaches. The paper distinguishes its method from approaches that backpropagate through many training iterations.
- Learning-rate adaptation: Earlier methods adapted learning rates using derivatives, gradient history, averaging, local sign behavior, or second-order Hessian-vector information.The cited approaches include Almeida et al., Plagianakos et al., Shao and Yip, stochastic meta-descent, RPROP, and Delta-Bar-Delta.
- Adaptive optimizers: AdaGrad, RMSProp, vSGD, and Adam use different heuristics to estimate aspects of the geometry of the traversed objective while adapting learning rates.These methods are presented as recently popular adaptive-learning-rate optimizers.
- Hyperparameter optimization: Several works cast hyperparameter selection as an optimization problem and compute gradients of a validation loss with respect to hyperparameters.Examples include truncated optimization and nested reverse-mode differentiation through training procedures.
- Computational trade-offs: A common limitation of validation-loss hypergradient methods is the need to retain many intermediate variables for reverse-mode differentiation through long training sessions.Maclaurin et al. addressed storage efficiency with reversible learning, whereas the present HD method updates the learning rate online.
4 EXPERIMENTS
Experiments across logistic regression, multilayer networks, and VGG Net compare hypergradient variants with regular optimizers. The variants generally move loss trajectories toward tuned-learning-rate behavior while reducing sensitivity to the initial learning rate.
- Experimental setup: Across several image-classification tasks, SGD-HD, SGDN-HD, and Adam-HD move loss trajectories closer to those obtained with tuned initial learning rates.The experiments compare these variants with SGD, SGDN, and Adam on logistic regression and neural-network objectives.
- Online tuning: Figure 2 compares learning-rate, training-loss, and validation-loss curves for regular SGD and Adam against their HD variants on logistic regression and multilayer MNIST classification.Dashed curves denote regular algorithms, solid curves denote HD variants, and HDM illustrates a multiplicative update rule.
- Hyperparameter sensitivity: Grid-search results indicate that, given a good β, HD performance is somewhat insensitive to α0, so tuning β alone can be sufficient.The search measures iterations to reach a training loss of 0.29 for logistic regression; similar results were observed for multilayer and CNN objectives.
- Logistic regression: In logistic regression, hypergradient variants consistently outperform regular counterparts, including SGD with Nesterov momentum and Adam.The improvement is reported for both training and validation behavior, and is described as particularly striking for Adam.
- Logistic regression: 17% change: Adam-HD increases its learning rate from α0 = 0.001 to 0.001174 before decay, while SGD-HD and SGDN-HD rise to approximately 0.05.The paper conjectures that the initial increase followed by decay adapts to the problem geometry and is associated with the observed performance increase.
- Multilayer neural network: In multilayer MNIST classification, Adam-HD reaches a validation-loss level Adam does not achieve and improves training loss by an order of magnitude over Adam.For this experiment, SGD-HD and SGDN-HD reach learning rates near 0.05, while Adam-HD initially rises only to 0.001083 before decaying.
- Convolutional neural network: On CIFAR-10 with VGG Net, SGD-HD and SGDN-HD perform significantly better than their regular versions in validation loss, while Adam-HD improves training loss but matches Adam's validation loss and speed.The initial learning-rate rise reaches approximately 0.025 for SGD-HD and SGDN-HD and 0.001002 for Adam-HD.
5 CONVERGENCE AND EXTENSIONS
The transitioning extension gradually replaces hypergradient-adapted learning rates with a chosen fixed rate, improving robustness and permitting convergence guarantees under stated convexity and smoothness assumptions.
- Transitioning to the underlying algorithm: The transition uses γ_t = δ(t) α_t + (1 − δ(t)) α_∞, matching α_t early and approaching α_∞ over time.The parameter update uses γ_t instead of α_t, with δ(1) = 1 and δ(t) → 0.
- Transitioning to the underlying algorithm: The extension behaves roughly like hypergradient descent initially and like the underlying algorithm by the end.The suggested α_∞ is a fixed learning rate expected to perform well throughout optimization.
- Transitioning to the underlying algorithm: The extension gives good convergence performance for a larger range of β than the non-transitioning method, improving robustness.This result comes from a preliminary experimental evaluation.
- Convergence: If f is convex and L-Lipschitz smooth with bounded gradient norm, θ_t converges to θ* when α_∞ < 1/L and tδ(t) → 0.The theorem concerns non-stochastic gradient descent under the stated assumptions.
- Convergence: Under these conditions, γ_t approaches α_∞ and eventually lies between 1/(L + 1) and 1/L, enabling standard gradient-descent convergence.The proof uses the limiting behavior of tδ(t) to establish the eventual learning-rate bounds.
- Higher-order hypergradients: The method adapts α_t but still uses a fixed β; adapting β with higher-order hypergradients is left for future work.The authors suggest that recursively adapting hypergradient learning rates might further improve robustness, but leave this hypothesis unexplored.
6 CONCLUSION
The paper applies hypergradient descent to several optimizers and concludes that it can reduce the resources needed to tune initial learning rates. Theoretical convergence guarantees remain limited and incomplete.
- Conclusion: Hypergradient variants of SGD, SGD with Nesterov momentum, and Adam empirically appear to reduce the time and resources needed to tune initial learning rates.The method is described as general, memory- and computation-efficient, and easy to implement.
- Conclusion: With a small β, the method requires significantly less tuning to achieve performance better than—or, in the worst case, the same as—the baseline.This is identified as the main advantage of the presented method.
- Conclusion: The paper's theoretical convergence guarantees are limited, with results still needed for the non-transitioning variant and a more general mixed variant.Establishing convergence rates is identified as future work.