Revisiting the Polyak step size
Elad Hazan, Sham M. Kakade · arXiv (Cornell University) · 2019
This paper revisits the Polyak step size schedule for convex optimization problems, proving that a simple variant of it simultaneously attains near optimal convergence rates for the gradient descent algorithm, for all ranges of strong convexity, smoothness, and Lipschitz parameters, without a-priory knowledge of these parameters.