Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence

By Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, Simon Lacoste-Julien. 2020

242 citations recorded by the source corpus.

We propose a stochastic variant of the classical Polyak step-size (Polyak, 1987) commonly used in the subgradient method. Although computing the Polyak step-size requires knowledge of the optimal function values, this information is readily available for typical modern machine learning applications. Consequently, the proposed stochastic Polyak step-size (SPS) is an attractive choice for setting the learning rate for stochastic gradient descent (SGD). We provide theoretical convergence guarantees for SGD equipped with SPS in different settings, including strongly convex, convex and non-convex functions. Furthermore, our analysis results in novel convergence guarantees for SGD with a constant step-size. We show that SPS is particularly effective when training over-parameterized models capable of interpolating the training data. In this setting, we prove that SPS enables SGD to converge to the true solution at a fast rate without requiring the knowledge of any problem-dependent constants or additional computational overhead. We experimentally validate our theoretical results via extensive experiments on synthetic and real datasets. We demonstrate the strong performance of SGD with SPS compared to state-of-the-art optimization methods when training over-parameterized models.

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

In Optimization & Training

Citations in the corpus

Dynamics of SGD with Stochastic Polyak Stepsizes: Truly Adaptive Variants and Convergence to Exact Solution (2022, methodology): “…that any different scaling factor cannot make the algorithm convergent. at batch size B can be quantiﬁed by the following quantity, introduced by [22] and studied also in [31, 9]: ﬁx a batch size B , and let It is easy to realize that as soon as problem (1) is interpolated, then 2 B = 0 for each…”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel and Zhang, 2021, Loizou et al., 2020, 2021].”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “Stochastic gradient descent (SGD) (Robbins & Monro, 1951; Nemirovski & Yudin, 1978; 1983; Nemirovski et al., 2009; Hardt et al., 2016; Gower et al., 2019; 2020; Loizou et al., 2020) is the workhorse for training supervised machine learning problems.”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, methodology): “This includes problems such as deep matrix factorization (Rolinek and Martius, 2018; Rahimi and Recht, 2017), binary classification using kernels (Loizou et al., 2020), consistent linear systems (Gower and Richtárik, 2015; Richtárik and Takác, 2020; Loizou and Richtárik, 2020b,a) and multi-class cla”
Training Neural Networks for and by Interpolation (2019, result): “We also refer the interested reader to the recent analysis of (Loizou et al., 2020), which appeared after this work and provides a set of improved theoretical results.”
Agentic AI: Autonomous Intelligence for Complex Goals—A Comprehensive Survey (2025, unknown): “Quick learning rate and quick convergence are always preferred as they enable the AI to work effectively in dynamic environments requiring continual learning [40], [41].”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “Where f∗ i is known in many machine learning applications, and c is a scaling parameter that depends on the class of functions being optimized (Loizou et al., 2021).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, background): “As a result, there has been a recent surge in trying to avoid these assumptions on the stochastic gradients for several classes of smooth functions: strongly convex [14, 25, 31], convex [14, 25, 40, 42], or even nonconvex functions [20, 24, 25].”