Research map / Optimization / Nonconvex and smooth optimization
Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
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.
Proves last-iterate convergence of SGD for smooth convex losses in the low-noise and interpolation regimes, including the greedy stepsize 1/beta, achieving O(1/sqrt T) in the interpolation case and near-optimal O(1/T + sigma_star/sqrt T) with tuned stepsize.
Problem
Last-iterate convergence of SGD with constant stepsizes (especially the greedy stepsize 1/beta) for smooth convex objectives in interpolation and low-noise regimes, where prior analyses only covered average iterates or least squares.
Approach
Extends the Zamani & Glineur last-iterate technique from deterministic nonsmooth subgradient descent to stochastic smooth convex SGD, using a tighter smooth-convex gradient inequality and step-dependent Young's inequality to handle cross terms, with weights v_t=(T-t+2)^{-alpha} tuned to alpha=(2-beta*eta)/4.
Key results
- In the interpolation regime with stepsize eta=1/beta, the last iterate achieves E[F(x_T)-F(x*)] <= 3 beta ||x_1-x*||^2 / sqrt(T), improving the O(T^{-1/4}) rate of prior OLS analysis.
- With stepsize eta=1/(beta log_2 T), the last-iterate rate is O(log T / T) in the interpolation regime.
- In the low-noise regime with tuned stepsize, the last iterate achieves O(1/T + sigma_star/sqrt T) up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed last-iterate SGD analysis with an optimally tuned stepsize | SGD on smooth convex low-noise objectives · Smooth convex low-noise objectives | expected excess risk: \ifrac{1}{T} + \ifrac{\sigma}{\sqrt{T}} -> \ifrac{1}{T} + \ifrac{\sigma_\star}{\sqrt{T}} | Helped |
| Use the proposed last-iterate guarantee beyond ordinary least squares | SGD on smooth convex realizable objectives · Realizable objectives, optimally tuned stepsize | expected excess risk: \ifrac{1}{T} -> \ifrac{1}{T} | No clear effect |
| Set the stepsize to η = 1/β | Last-iterate SGD on smooth convex realizable objectives · Realizable objectives | expected excess risk: O(1/T^{1/4}) -> O(1/\sqrt{T}) | Helped |
| Use without-replacement sampling | Last-iterate SGD on smooth convex realizable objectives · Realizable objectives, T ≤ n | expected excess risk: O(1/\sqrt{T}) | Helped |
| Set the stepsize to η = 1/(β log₂(T)) (ablation) | Last-iterate SGD on smooth convex realizable objectives · Realizable objectives | expected excess risk: \frac{3\beta\norm{x_1-x^\star}^2}{\eta(2-\beta\eta)T^{1-\beta\eta/2}} -> \frac{6\beta\norm{x_1-x^\star}^2 \log_2(T)}{T} | Helped |
| Set the stepsize to the tuned minimum of 1/(β log₂(T)) and ‖x₁−x⋆‖/(σ⋆√(T log₂(T+2))) (ablation) | Last-iterate SGD on smooth convex low-noise objectives · Low-noise objectives | expected excess risk: \frac{24 \beta \norm{x_1-x^\star}^2 \log_2(T)}{T} + \frac{120\sigma_\star \norm{x_1-x^\star} \sqrt{\log_2(T+2)}}{\sqrt{T | Helped |
| Use the standard Kaczmarz method (c = 1) | Block Kaczmarz · Realizable linear systems | expected loss: O(1/T^{1/4}) -> O(1/\sqrt{T}) | Helped |
| Apply the last-iterate SGD guarantee to continual linear regression | Continual linear regression · Random ordering, with or without replacement | forgetting and population loss: \dfrac{1}{\sqrt[4]{T}} -> \dfrac{1}{\sqrt{T}} | Helped |
| Apply the last-iterate SGD guarantee to weakly-regularized continual linear classification | Continual linear classification · Random ordering, with or without replacement | forgetting: \frac{1}{\sqrt[4]{T}} -> \frac{1}{\sqrt{T}} | Helped |
Surprising findings
- The last-iterate guarantee at the greedy stepsize 1/beta is provably weaker than average-iterate rates, leaving an open gap to the Omega(1/T) lower bound.
- A simpler analysis for small stepsizes is non-convergent as eta*beta approaches 1, showing the advanced technique is needed for large stepsizes.
Limitations
- Greedy stepsize rate O(1/sqrt T) is likely not tight versus the known Omega(1/T) lower bound.
- Without-replacement guarantee holds only in the interpolation regime.
- Near-optimal rates for tuned stepsize hold only up to logarithmic factors.
Experimental setup
Metrics: expected excess risk convergence rate in T
Baselines: Varre et al. 2021 last-iterate SGD (O(1/T^{1/4}) for OLS) average-iterate SGD bounds (Gower et al.) Zamani & Glineur-based last-iterate bounds Attia & Koren last-iterate bounds
Builds on: Zamani & Glineur last-iterate analysis Varre et al. last-iterate SGD for least squares
Closest papers by meaning
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · similarity 0.93)
- Last iterate convergence of SGD for Least-Squares in the Interpolation regime. (NeurIPS 2021 · similarity 0.92)
- Rapid Overfitting of Multi-Pass SGD in Stochastic Convex Optimization (ICML 2025 · similarity 0.91)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.90)
- Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson–Romberg Extrapolation (ICLR 2025 · similarity 0.90)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.90)
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.