Source-linked AI summary
Nesterov's Accelerated Gradient and Momentum as approximations to Regularised Update Descent
Aleksandar Botev, Guy Lever, David Barber
TL;DR
The paper addresses how to interpret and improve gradient-based update rules, especially the limited intuitive understanding of NAG. It develops Regularised Update Descent by optimizing the objective with respect to updates, recovers momentum and NAG as approximations, and reports faster convergence than both on quadratic objectives.
Problem
NAG is theoretically principled but has largely defied intuitive interpretation, while the conditions under which RUD outperforms NAG for convex Lipschitz functions remain incompletely analyzed.
Method
The paper optimizes the objective with respect to the parameter update, defining Regularised Update Descent and relating momentum and NAG to first- and second-order approximations.
Results
For the special quadratic objective case, RUD can converge more quickly than NAG or classical momentum.
Takeaways & Limitations
The update-centered framework gives NAG and momentum a common interpretation and presents RUD as a potentially useful optimization algorithm.
Takeaways & Limitations
RUD requires the learning rate not to be too high for momentum values below 0.5 and therefore can diverge, unlike NAG and momentum.
Abstract
from arXiv · showhide
We present a unifying framework for adapting the update direction in gradient-based iterative optimization methods. As natural special cases we re-derive classical momentum and Nesterov's accelerated gradient method, lending a new intuitive interpretation to the latter algorithm. We show that a new algorithm, which we term Regularised Gradient Descent, can converge more quickly than either Nesterov's algorithm or the classical momentum algorithm.
1 Introduction
The paper frames gradient-based optimization around directly choosing parameter updates, recovering momentum and NAG as related methods. This perspective clarifies NAG’s interpretation and motivates analyzing faster convergence.
- The framework directly sets parameter updates to optimize the objective and recovers NAG and classical momentum as special cases.It provides a common perspective on both algorithms rather than treating them as unrelated update rules.
- Momentum can reduce zig-zagging on ridged objectives by accumulating persistent directions while canceling directions whose gradients change rapidly.The paper also motivates momentum for stochastic gradients and flat objective directions.
- NAG smooths the previous two parameter values before taking a gradient step, while momentum continues along the previous update direction.Both methods retain directional information across iterations, but NAG evaluates the gradient from a smoothed parameter value.
- NAG achieves convergence at rate 1/t^2 for Lipschitz convex functions under suitable schedules, compared with GD’s 1/t rate.The paper states that Nesterov proved the NAG rate is optimal among first-order methods in the worst case.
- The paper interprets NAG and momentum through optimization with respect to the update itself, addressing NAG’s limited intuitive interpretation.This update-centered perspective is presented as a contribution of the framework.
2 Regularised Update Descent
Regularised Update Descent optimises an update variable with a regularised objective, and its approximations recover momentum and NAG. The framework also explains why RUD may outperform NAG by evaluating the gradient further along the prospective update.
- Regularised Update Descent: RUD introduces a regularised objective over the prospective update, whose optimum coincides with the optimum of the original objective when the update vanishes.The regulariser prevents the update from remaining nonzero at a stationary point.
- Regularised Update Descent: RUD updates parameters using the newly improved update, with the momentum schedule chosen so µt = 1 − αtγt tends toward 1.The complete algorithm applies θt+1 = θt + vt+1 rather than using the previous update.
- Deriving MOM from RUD: A first-order approximation of the RUD objective recovers classical momentum as update optimisation with respect to vt.This connects momentum directly to optimising an approximate regularised update objective.
- Deriving NAG from RUD: A more accurate expansion recovers NAG by evaluating the gradient at θt + µtvt and setting 1 − αtγt = µt.The factor µt reduces trust in higher-order terms away from the current point, analogous to a trust-region choice.
- RUD versus NAG: RUD evaluates J′ at θt + vt rather than θt + µtvt, so it looks farther forward in a way more consistent with the eventual parameter update.The paper presents this as a tentative explanation for RUD outperforming NAG.
- Convergence regions: Figure 1 maps parameter regions where RUD converges or outperforms NAG, alongside regions where MOM outperforms NAG or RUD.The figure uses the (µ, α) plane for these convergence comparisons.
3 Comparison on a Quadratic function
The paper analyzes NAG, momentum, and RUD on a simple quadratic objective, deriving convergence conditions and comparing their asymptotic behavior. RUD can converge faster than NAG, while momentum generally performs worse in the practical high-momentum regime.
- Analysis scope: The analysis asks whether RUD can converge faster than NAG for convex Lipschitz functions, but fully examines only a simple quadratic objective.For this quadratic case, the update trajectories of NAG, RUD, and momentum can be computed explicitly, with exponential convergence in iteration count.
- Empirical comparison: In the 1000-dimensional quadratic experiment, momentum overshoots the minimum more than RUD or NAG, while RUD typically outperforms NAG.All methods use the same learning-rate and momentum schedules.
- NAG: NAG converges to the minimum for any learning rate 0 < α < 1 and momentum 0 < µ < 1.The sufficient conditions are |w+| < 1 and |w−| < 1.
- MOM: Momentum always converges for 0 < α < 1 and 0 < µ < 1, but it outperforms NAG and RUD only when momentum is small.The paper characterizes the small-momentum regime as practically uninteresting because momentum is typically close to 1.
- RUD: RUD has more complex convergence behavior than NAG or momentum, with convergence restricted to a parameter region.Its stability requires both |w+| < 1 and |w−| < 1.
- RUD: RUD is asymptotically faster than NAG when momentum is high, typically above 0.8, provided α < 1.The faster-convergence region is described as largely independent of the learning rate under that condition.
4 Experiments
Experiments test RUD on a high-dimensional quadratic function and a non-convex autoencoder. RUD outperforms NAG in the quadratic setting and slightly outperforms it on the autoencoder task.
- A toy high dimensional quadratic function: On a randomly generated 1000-dimensional quadratic function, RUD’s theoretical advantage over NAG and momentum carries over to the more general quadratic setting.The authors report that improved convergence over NAG is typical for quadratic objectives.
- Deep Learning: MNIST: The non-convex experiment trains a 784−1000−500−250−30 autoencoder on 50,000 scaled handwritten-digit images using tanh nonlinearities and binary cross-entropy loss.The model reconstructs 28x28 images through a 30-dimensional representation.
- Deep Learning: MNIST: On the autoencoder problem, RUD slightly outperforms NAG after optimal learning-rate selection for each method.Both methods use the schedule µt = 1 − 3/(5 + t).
5 Conclusion
The paper presents Regularised Update Descent as a first-order optimization approach that optimizes the objective with respect to updates. It also interprets Nesterov’s and momentum methods as approximations to this algorithm.
- Regularised Update Descent optimizes the objective with respect to parameter updates.
- Nesterov’s Accelerated Gradient and momentum can be viewed as approximations to Regularised Update Descent.
- Regularised Update Descent can converge more quickly than Nesterov’s Accelerated Gradient.
A Alternative NAG derivation
The derivation treats optimization as a two-stage update process: regularizer descent followed by lookahead-objective descent. NAG is recovered by setting µ_t = 1−α_tγ_t, while RUD omits the initial regularizer descent.
- The algorithm first descends on the regularizer, then on the lookahead objective J(θ_t + v), before updating θ_t.
- The update equations set v_t+1 = (1 − α_tγ_t)v_t − α_tg_t and θ_t+1 = θ_t + v_t+1.
- Setting µ_t = 1−α_tγ_t recovers Nesterov’s Accelerated Gradient formulation.
- RUD differs from NAG by omitting the initial descent step on the regularizer, leaving ṽ_t+1 = v_t.