Research map / Optimization / Nonconvex and smooth optimization
New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Reframes the Polyak stepsize and its stochastic variants as (sub)gradient descent on a fixed convex surrogate (half squared gap), derives unified rates, and proves negative results showing neighbourhood-of-convergence and instability when the surrogate minimum is positive.
Problem
Understanding why the Polyak stepsize is adaptive across assumptions and when it fails, including its stochastic variants (SPS, SPS_max, SPS+, ALI-G) whose analyses are fragmented and often yield non-vanishing neighbourhood terms.
Approach
Views the Polyak stepsize as subgradient descent on the surrogate phi = 1/2 (f - f*)^2, whose inverse local star upper curvature equals the Polyak stepsize; generalizes to psi = 1/2 h^2 for any convex h >= 0, yielding a unified analysis and showing that a positive minimum of h causes instability and non-convergence.
Key results
- Shows the Polyak surrogate phi = 1/2 (f - f*)^2 is always locally star upper curved with curvature ||g||^2, giving O(1/T) surrogate rate for Lipschitz f and O(1/T^2) for self-bounded f.
- Generalized Polyak stepsize (Algorithm with min(1/||g||^2, gamma/h)) unifies SPS_max, SPS_max^l and SPS_+ and gives rates under self-bounded, Lipschitz, and quadratic-growth assumptions.
- Proves the fixed point of the Polyak update is unstable for self-bounded convex functions with quadratic growth when h* > 0, and constructs a 1-d example where E[F(x_t)] - min F >= 2/3 for all t.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| view Polyak stepsize as descent on the squared-gap surrogate φ(x)=½(f(x)-f*)² | Polyak stepsize · Convex optimization | surrogate convergence rate: O(1/T) | Helped |
| use Polyak stepsize on an L-self-bounded function | Polyak stepsize · L-self-bounded convex optimization | surrogate convergence rate: O(1/T^2) | Helped |
| underestimate the minimum so that h*=min_x h(x)>0 | Deterministic Polyak update · Strictly positive convex functions | fixed-point stability | Hurt |
| apply the unmodified Polyak update to a strictly positive smooth strongly convex function | Deterministic Polyak update · Strictly positive smooth strongly convex functions | convergence of average iterate: δ>0 | Hurt |
| apply the unmodified Polyak update to h(x)=x²/2+a with a>0 | Deterministic Polyak update · One-dimensional quadratic | probability of convergence to optimum: P{limₜ→∞ xₜ=x*}=0 | Hurt |
| use SPS without interpolation on the stated two-quadratic finite-sum objective | SPS · F(x)=0.5(f₁(x)+f₂(x)) | expected suboptimality gap: 2/3 | Hurt |
| use generalized Polyak stepsize with h(x,ξ) positive at the optimum | Generalized Polyak stepsize · Stochastic optimization | convergence target | Hurt |
| clip the stepsize at a sufficiently small maximum | Generalized Polyak stepsize · Strictly positive deterministic objectives | fixed-point stability | Helped |
| set h(x*,ξ)=0 for every sample | Generalized Polyak stepsize · Stochastic optimization | distance to optimum | Helped |
Surprising findings
- Lack of convergence arises from instability due to underestimating the minimum, not from lack of interpolation as commonly believed.
- For 1-d quadratics with positive offset, the set of initializations that converge to the optimum has measure zero.
Limitations
- Framework requires the surrogate h to be convex, which must be assumed a priori.
- No experiments are included; results are purely theoretical.
- Open question on which surrogates admit fast rates and tight neighbourhoods.
Experimental setup
Baselines: ALI-G SPS_max SPS_+ SPS_max^l StoPS DECSPS
Builds on: Polyak stepsize ALI-G SPS_max SPS_+ Passive-Aggressive
Closest papers by meaning
- Constrained Online Convex Optimization with Polyak Feasibility Steps (ICML 2025 · similarity 0.89)
- Non-convex Stochastic Composite Optimization with Polyak Momentum (ICML 2024 · similarity 0.88)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · similarity 0.86)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.86)
- Parameter-free Clipped Gradient Descent Meets Polyak (NeurIPS 2024 · similarity 0.86)
- Taking the Road Less Scheduled with Adaptive Polyak Steps (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.