Revisiting the Polyak step size

Elad Hazan, Sham Kakade

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 th…