Fetching the paper…

Reading the bibliography…

2016

An optimal first order method based on optimal quadratic averaging

Drusvyatskiy, Dmitriy, Fazel, Maryam, Roy, Scott

Original
PDF
Post on X

Understand

In a recent paper, Bubeck, Lee, and Singh introduced a new first order method for minimizing smooth strongly convex functions.

Their geometric descent algorithm, largely inspired by the ellipsoid method, enjoys the optimal linear rate of convergence.
We show that the same iterate sequence is generated by a scheme that in each iteration computes an optimal average of quadratic lower-models of the function.
Indeed, the minimum of the averaged quadratic approaches the true minimum at an optimal rate.

An optimal first order method based on optimal quadratic averaging · Around

Built on

The cutting-plane method for solving convex programs
J. E. Kelley, Jr · 1960
Earlier work this paper cites.
A method for solving the convex programming problem with convergence rate O ⁡ ( 1 / k 2 ) O(1/k^{2})
Yu. E. Nesterov · 1983
Earlier work this paper cites.
Introductory lectures on convex optimization
Y. Nesterov · 2004
Earlier work this paper cites.
Numerical optimization
J. Nocedal and S.J. Wright · 2006
Earlier work this paper cites.
On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
A. Beck · 2007
Earlier work this paper cites.

Similar

LIBSVM: A library for support vector machines
C.-C. Chang and C.-J. Lin · 2011
Cited alongside, same era.
A differential equation for modeling nesterov’s accelerated gradient method: Theory and insights
W. Su, S. Boyd, and E. Candes · 2014
Cited alongside, same era.
A geometric alternative to Nesterov’s accelerated gradient descent
Original
S. Bubeck, Y.T. Lee, and M. Singh · 2015
Cited alongside, same era.
Linear coupling: An ultimate unification of gradient and mirror descent
Original
Z. Allen-Zhu and L. Orecchia · 2016
Cited alongside, same era.

Then

Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
H. Attouch, J. Peypouquet, and P. Redont · 2016
Closest in time.
Black-box optimization with a politician
Original
S. Bubeck and Y.T. Lee · 2016
Closest in time.
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints
L. Lessard, B. Recht, and A. Packard · 2016
Closest in time.
Geometric descent method for convex composite minimization
Original
S. Chen and S. Ma · 2017
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…