Fetching the paper…

Reading the bibliography…

2015

On Accelerated Methods in Optimization

Wibisono, Andre, Wilson, Ashia C.

Original
PDF
Post on X

Understand

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.

On Accelerated Methods in Optimization · Around

Built on

A method of solving a convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) {O}(1/k^{2})
Yurii Nesterov · 1983
Earlier work this paper cites.
Natural gradient works efficiently in learning
Shun-Ichi Amari · 1998
Earlier work this paper cites.
Calculus of Variations
Israel M. Gelfand and Sergei V. Fomin · 2000
Earlier work this paper cites.
Introductory Lectures on Convex Optimization: A Basic Course
Yurii Nesterov · 2004
Earlier work this paper cites.
Smooth minimization of non-smooth functions
Yurii Nesterov · 2005
Earlier work this paper cites.

Similar

Cubic regularization of Newton’s method and its global performance
Yurii Nesterov and Boris T. Polyak · 2006
Cited alongside, same era.
Accelerating the cubic regularization of Newton’s method on convex problems
Yurii Nesterov · 2008
Cited alongside, same era.
Estimate sequence methods: Extensions and approximations
Michel Baes · 2009
Cited alongside, same era.
Linear coupling: An ultimate unification of gradient and mirror descent
Original
Zeyuan Allen-Zhu and Lorenzo Orecchia · 2014
Cited alongside, same era.

Then

The proximal distance algorithm
Kenneth Lange and Kevin L. Keys · 2014
Later among the works it cites.
A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights
Weijie Su, Stephen Boyd, and Emmanuel Candès · 2014
Later among the works it cites.
Adaptive restart for accelerated gradient schemes
Brendan O’Donoghue and Emmanuel Candès · 2015
Closest in time.
The information geometry of mirror descent
Garvesh Raskutti and Sayan Mukherjee · 2015
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…