Complexity Guarantees for Polyak Steps with Momentum.
TITLE: Complexity Guarantees for Polyak Steps with Momentum.
AUTHORS: Mathieu Barré, Adrien Taylor, Alexandre d'Aspremont.
ABSTRACT: In smooth strongly convex optimization, or in the presence of Holderian
error bounds, knowledge of the curvature parameter is critical for obtaining
simple methods with accelerated rates. In this work, we study a class of
methods, based on Polyak steps, where this knowledge is substituted by that of
the optimal value, f_*. We first show slightly improved convergence bounds
than previously known for the classical case of simple gradient descent with
Polyak steps, we then derive an accelerated gradient method with Polyak steps
and momentum, along with convergence guarantees.
STATUS: Preprint.
ArXiv PREPRINT: 2002.00915
|