Revisiting the Polyak step size
By Elad Hazan, Sham M. Kakade. 2019
90 citations recorded by the source corpus.
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.
Subfields: Optimization & Training
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Optimization & Training
- Nicolas Loizou
- Simon Lacoste-Julien
- Issam Hadj Laradji
- Ioannis Mitliagkas
- Peter Richtárik
- Sebastian Pokutta
- Sharan Vaswani
- Alejandro Carderera
Citations in the corpus
- Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “The classical Polyak stepsize [25] has been successfully used in the analysis of deterministic subgradient methods in different settings [5, 7, 18].”
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “Contributions: Inspired by the classical Polyak step-size (Polyak, 1987) commonly used with the deterministic subgradient method (Hazan and Kakade, 2019; Boyd et al., 2003), we propose a novel adaptive learning rate for SGD.”
- Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, methodology): “In the deterministic setting Polyak’s results have been been successfully extended and used for solving weakly convex and smooth problems (Boyd et al., 2003; Davis et al., 2018; Hazan & Kakade, 2019).”
- Second-order Conditional Gradients (2020, methodology): “…of the value of f ( x ∗ ) has been used to obtain optimal step sizes, known as Polyak steps, for first-order methods (Polyak, 1969; Nedic, 2002; Hazan & Kakade, 2019) as well as to obtain local estimates of the strong convexity parameter of a function for accelerated algorithms (Barré &…”
- Training Neural Networks for and by Interpolation (2019, background): “…Polyak step-size, which is itself the same as the optimal rate of non-stochastic gradient descent: O (1 / √ T ) for convex Lipschitz functions, O (1 /T ) for convex and smooth functions, and O (exp( − kT )) (for some constant k ) for smooth and strongly convex functions (Hazan & Kakade, 2019).”