On Accelerated Methods in Optimization

By Andre Wibisono, Ashia C. Wilson. 2015

30 citations recorded by the source corpus.

In convex optimization, there is an {\em acceleration} phenomenon in which we can boost the convergence rate of certain gradient-based algorithms. We can observe this phenomenon in Nesterov's accelerated gradient descent, accelerated mirror descent, and accelerated cubic-regularized Newton's method, among others. In this paper, we show that the family of higher-order gradient methods in discrete time (generalizing gradient descent) corresponds to a family of first-order rescaled gradient flows in continuous time. On the other hand, the family of {\em accelerated} higher-order gradient methods (generalizing accelerated mirror descent) corresponds to a family of second-order differential equations in continuous time, each of which is the Euler-Lagrange equation of a family of Lagrangian functionals. We also study the exponential variant of the Nesterov Lagrangian, which corresponds to a generalization of Nesterov's restart scheme and achieves a linear rate of convergence in discrete time. Finally, we show that the family of Lagrangians is closed under time dilation (an orbit under the action of speeding up time), which demonstrates the universality of this Lagrangian view of acceleration in optimization.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

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

1. Jianfei Cai
2. Jiuxiang Gu
3. Richard S. Zemel
4. James Lucas
5. Roger Baker Grosse
6. Amir Shahroudy
7. Ruslan Salakhutdinov
8. Tsuhan Chen

In Computational Theory and Mathematics

1. James Lucas
2. Jianfei Cai
3. Roger Baker Grosse
4. Richard S. Zemel

In Numerical Analysis

1. James Lucas
2. Roger Baker Grosse
3. Richard S. Zemel

Citations in the corpus

• Recent advances in convolutional neural networks (2015, background): “This anticipatory update prevents the optimization from moving too fast and achieves better performance [133, 134].”
• Aggregated Momentum: Stability Through Passive Damping (2018, methodology): “While most momentum methods can be viewed as the discretization of second order ODEs (Wilson et al., 2016) it seems that AggMo does not fall into this class of algorithms.”