Stochastic Gradient Descent with Polyak’s Learning Rate

By Adam M. Oberman, Mariana Prazeres. 2019

42 citations recorded by the source corpus.

Stochastic gradient descent (SGD) for strongly convex functions converges at the rate O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(1/k)$$\end{document}. However, achieving good results in practice requires tuning the parameters (for example the learning rate) of the algorithm. In this paper we propose a generalization of the Polyak step size, used for subgradient methods, to stochastic gradient descent. We prove a non-asymptotic convergence at the rate O(1/k)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {O}(1/k)$$\end{document} with a rate constant which can be better than the corresponding rate constant for optimally scheduled SGD. We demonstrate that the method is effective in practice, and on convex optimization problems and on training deep neural networks, and compare to the theoretical rate.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Artificial Intelligence

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Issam Hadj Laradji
4. Peter Richtárik
5. Sharan Vaswani
6. Antonio Orvieto
7. Robert Mansel Gower
8. Gauthier Gidel

In Computational Mechanics

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Sharan Vaswani
4. Issam Hadj Laradji
5. Peter Richtárik
6. Antonio Orvieto
7. Gauthier Gidel
8. Sebastian U. Stich

In Optimization & Training

1. Nicolas Loizou
2. Simon Lacoste-Julien
3. Issam Hadj Laradji
4. Sharan Vaswani
5. Peter Richtárik
6. Antonio Orvieto
7. Robert Mansel Gower
8. Gauthier Gidel

Citations in the corpus

• Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, background): “First attempts on providing an efficient variant of the stepsize that works well in the stochastic setting were made in [3, 24].”
• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “We now briefly compare against the recently proposed stochastic variants of the Polyak step-size (Rolinek and Martius, 2018; Oberman and Prazeres, 2019; Berrada et al., 2020).”