Complexity Guarantees for Polyak Steps with Momentum
This work addresses optimization efficiency for machine learning practitioners by providing incremental improvements to existing methods.
The paper tackles the problem of smooth strongly convex optimization by substituting knowledge of the strong convexity parameter with knowledge of the optimal value, leading to slightly improved convergence bounds for gradient descent with Polyak steps and an accelerated gradient method with momentum and convergence guarantees.
In smooth strongly convex optimization, knowledge of the strong convexity 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.