Stochastic Polyak Step-Size
Algorithms AIMech:StochasticPolyakStepSize DRAFT
Aliases: SPS, SPS_max, Bounded Stochastic Polyak Step-Size, Stochastic Polyak Learning Rate
An adaptive learning-rate selection rule for stochastic gradient descent on finite-sum or streaming objectives min_{x in R^d} f(x) = (1 / n) sum_{i=1}^n f_i(x) that sets the per-iteration step size for sampled component i_k to gamma_k = (f_i(x^k) - f_i^*) / (c ||nabla f_i(x^k)||^2) (or its bounded variant SPS_max: gamma_k = min{(f_i(x^k) - f_i^*) / (c ||nabla f_i(x^k)||^2), gamma_b}), where f_i^* = inf_x f_i(x) is the known component-loss infimum (zero for standard unregularized surrogate losses or closed-form via the r-Lambert W_r function for l_2-regularized binary losses), c > 0 is a curvature scaling factor, and gamma_b > 0 is an optional upper bound or adaptive smoothing cap gamma_b^k = tau^{b/n} gamma^{k-1}.
Identity Notes & Concept Scope
Distinct from classical deterministic Polyak step-size (Polyak, 1987, which requires full objective evaluations f(x^k), full subgradients g^k, and the global minimum f^*), from ALI-G (Berrada et al., 2020, which adds a denominator regularizer delta > 0 that prevents exact convergence under interpolation), from L4 (Rolinek & Martius, 2018, which estimates f_i^* online using three hyperparameters without convergence guarantees), and from Stochastic Armijo Line Search (SLS, Vaswani et al., 2019, which requires expensive backtracking function evaluations).
Claims & Grounded Evidence
4 Claims
Mechanism
#c-r626-smooth-strong-convexity-sandwich-and-self-bounding-identity
When component functions f_i are mu_i-strongly convex and L_i-smooth with L_max = max_i L_i, the Stochastic Polyak Step-Size is automatically sandwiched in 1 / (2 c L_max) <= 1 / (2 c L_i) <= gamma_k <= 1 / (2 c mu_i) (Eq. 5), and SPS_max satisfies the fundamental self-bounding inequality gamma_k^2 ||nabla f_i(x^k)||^2 <= (gamma_k / c) [f_i(x^k) - f_i^*] (Eq. 17, with equality for unbounded SPS), bounding the squared update norm without bounded-gradient or strong-growth assumptions.
Mechanism
#c-r626-finite-optimal-objective-difference-and-interpolation-rates
Under finite optimal objective difference sigma^2 := E_i[f_i(x^*) - f_i^*] = f(x^*) - E_i[f_i^*] < infinity (Assumption 2.1, Eq. 4), SGD with SPS_max (c >= 1/2) on L_i-smooth convex f_i and mu-strongly convex f satisfies E||x^k - x^*||^2 <= (1 - mu alpha)^k ||x^0 - x^*||^2 + 2 gamma_b sigma^2 / (mu alpha) where alpha = min{1 / (2 c L_max), gamma_b} (Theorem 3.1); under interpolation (sigma^2 = 0), unbounded SPS with c = 1/2 converges linearly to x^* at rate (1 - mu / L_max)^k (Corollary 3.2), and on consistent linear systems A x = b under sketch-and-project reformulation, SPS with c = 1/2 reduces identically to the optimal Randomized Kaczmarz step size gamma_k = 1 (Section 3.4 & Theorem B.3).
Application
#c-r626-lambert-w-closed-form-regularized-infima-and-applications
For l_2-regularized binary log-loss f_i(x) = log(1 + exp(-<x, z_i>)) + (lambda / 2) ||x||^2 and binary exponential loss f_i(x) = exp(-<x, z_i>) + (lambda / 2) ||x||^2, the component infimum f_i^* = g(alpha^*) is obtained in closed form prior to training via the r-Lambert and classical Lambert functions as alpha^* = (1 / ||z_i||) W_1(||z_i||^2 / lambda) (Eq. 73) and alpha^* = (1 / ||z_i||) W_0(||z_i||^2 / lambda) (Eq. 77), enabling SPS and SPS_max to train regularized classifiers, RBF kernel machines, deep matrix factorizations, and ResNet/DenseNet models on CIFAR-10 and CIFAR-100.
Limitation
#c-r626-misspecified-interpolation-fluctuation-limitation
When the interpolation condition sigma^2 = 0 is not exactly satisfied, unbounded SPS (gamma_b = infinity) is sensitive to misspecification and exhibits large step-size fluctuations, requiring either a tuned upper bound gamma_b in SPS_max or the iteration-dependent smoothing cap gamma_b^k = tau^{b/n} gamma^{k-1} to stabilize convergence.
⚠️ Curated Limitations & Negative Results
- Requires knowing or pre-computing the component loss infimum f_i^* = inf_x f_i(x) (readily known as 0 for unregularized standard losses or via Lambert W functions for l_2-regularized binary losses, but nontrivial for arbitrary structured objectives).
- Unbounded SPS (gamma_b = infinity) fluctuates when interpolation (sigma^2 = 0) does not hold, requiring bounded SPS_max or adaptive step-size smoothing gamma_b^k = tau^{b/n} gamma^{k-1}.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ArtificialNeuralNetwork
Artificial Neural Network
|
related_match | SPS is an adaptive stochastic gradient step-size schedule used to train over-parameterized artificial neural networks and convex/PL machine learning models. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r626-primary-pdf
|
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, Simon Lacoste-Julien
|
primary paper
full_text
|
ID: https://dblp.org/rec/conf/aistats/LoizouVLL21
sha256:5ef8bbd6a6ba…
|
r626-arxiv-abs
|
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (arXiv abstract)
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, Simon Lacoste-Julien
|
primary paper
abstract_only
|
ID: https://arxiv.org/abs/2002.10542
sha256:bc23b1ea72d5…
|
r626-metadata-cr
|
Nicolas Loizou, Sharan Vaswani, Issam Hadj Laradji, Simon Lacoste-Julien
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/conf/aistats/LoizouVLL21
sha256:141d186d70c7…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T11:49:00Z
Updated: 2026-10-19T11:49:00Z
Source File:
data/curated/StochasticPolyakStepSize.yaml
· Schema:
curated_concept.yaml
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories