A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
By Weijie Su, Stephen P. Boyd, E.J. Candes. 2014
1,385 citations recorded by the source corpus.
We derive a second-order ordinary differential equation (ODE), which is the limit of Nesterov's accelerated gradient method. This ODE exhibits approximate equivalence to Nesterov's scheme and thus can serve as a tool for analysis. We show that the continuous time ODE allows for a better understanding of Nesterov's scheme. As a byproduct, we obtain a family of schemes with similar convergence rates. The ODE interpretation also suggests restarting Nesterov's scheme leading to an algorithm, which can be rigorously proven to converge at a linear rate whenever the objective is strongly convex.
Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training, Mathematical Optimization
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Michael I. Jordan
- Yoshua Bengio
- Ruslan Salakhutdinov
- Sergey Levine
- Percy Liang
- Quoc V. Le
- Mohit Bansal
- Jianfeng Gao
In Computational Mechanics
- Michael I. Jordan
- Simon Shaolei Du
- Francis R. Bach
- Sanjeev Arora
- Praneeth Netrapalli
- Chi Jin
- Peter L. Bartlett
- Zeyuan Allen-Zhu
In Numerical Analysis
- Michael I. Jordan
- Hédy Attouch
- Ernö Robert Csetnek
- B. Recht
- James Lucas
- Roger Baker Grosse
- Alexandre Cabot
- Richard S. Zemel
In Optimization & Training
- Michael I. Jordan
- Peter L. Bartlett
- Simon Lacoste-Julien
- Simon Shaolei Du
- Roger Baker Grosse
- James Lucas
- Peter Richtárik
- Nicolas Loizou
In Mathematical Optimization
- Michael I. Jordan
- Ashia C. Wilson
- Chi Jin
- Yura Malitsky
- Hédy Attouch
- Roger Baker Grosse
- James Lucas
- Richard S. Zemel
Citations in the corpus
- On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization (2018, background): “This approach has led to numerous interesting findings, including recent results in the context of acceleration methods ( e.g. Su et al. (2014); Wibisono et al. (2016)).”
- Stochastic Modified Equations and Adaptive Stochastic Gradient Algorithms (2015, methodology): “Other deterministic continuous time approximation methods include Su et al. (2014); Krichene et al. (2015); Wibisono et al. (2016).”
- Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity (2018, methodology): “The specific case (1) was studied by Su, Boyd and Candès in [36] in terms of the rate of convergence of the values.”
- Accelerated Mirror Descent in Continuous and Discrete Time (2015, methodology): “Although Nesterov’s method has been notoriously hard to explain intuitively [14], progress has been made recently: in [28], Su et al.”
- Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances (2019, background): “[SBC14] Weijie Su, Stephen Boyd, and Emmanuel Candes.”
- A Lyapunov Analysis of Momentum Methods in Optimization (2016, methodology): “O C ] 3 1 D”
- Stochastic Heavy ball (2016, methodology): “of the NAGD when α “ 1 (see [WSC16] and their “magic” constant 3 “ 2α ` 1 in that case).”
- Aggregated Momentum: Stability Through Passive Damping (2018, methodology): “While most momentum methods can be viewed as the discretization of second order ODEs [33] it seems that AggMo does not fall into this class of algorithms.”
- A variational perspective on accelerated methods in optimization (2016, methodology): “For p = 2, Su et al. [32] and Krichene et al. [17] treat the case when we start at t = 0 with initial condition ( X 0 , W 0 ) = ( x 0 , ∇ h ( x 0 )), so that ˙ X 0 = 0.”
- Fast optimization via inertial dynamics with closed-loop damping (2020, methodology): “It was introduced in the context of convex optimization by Su–Boyd–Candès in [88].”
- Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, background): “This leads to an ODE which is the continuous limit of AGD [Su et al., 2016]: where ¨ x and ˙ x are derivatives with respect to time t .”
- On the Effectiveness of Richardson Extrapolation in Machine Learning (2020, neutral): “…of accelerated gradient descent is exactly of the form depicted in the left plot of Figure 2: that is, the iterates x k oscillate around the optimum (see, e.g., Su et al., 2016; Flammarion and Bach, 2015), and Richardson extrapolation is of no help, but is not degrading performance too much.”
- On Accelerated Methods in Optimization (2015, methodology): “3) is a generalization of the energy functional in [13], who were the first to point out that accelerated gradient descent (p = 2, Euclidean case) in continuous time corresponds to the second order equation Ẍt+ 3 t Ẋt+∇f(Xt) = 0, and proved a matching O(1/t2) convergence rate [13, Theorem 3.”
- Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3 (2017, neutral): “In [5], [7], [17], [36] it is proved that the sequence (E(k)) is nonincreasing, and Θ(xk)−minΘ = O ( 1 k2 )”