Research map / Optimization / Nonconvex and smooth optimization
Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods
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.
Revisits last-iterate convergence of stochastic mirror descent (CSMD) with a unified analysis giving in-expectation and high-probability rates for composite objectives, general domains and non-Euclidean norms, extended to heavy-tailed and sub-Weibull noise.
Problem
Last-iterate convergence of SGD-type methods for convex (Lipschitz and smooth) composite optimization: prior high-probability last-iterate bounds required compact domains or almost surely bounded noise, and smooth/composite/non-Euclidean cases were largely unexplored.
Approach
A single analysis of Composite Stochastic Mirror Descent that bounds F(x^{t+1})-F(z^t) for a carefully chosen convex combination z^t of past iterates, plus a weight-sequence trick and a sub-Gaussian concentration lemma, yielding last-iterate rates without compactness or bounded-noise assumptions.
Key results
- Last iterate of CSMD achieves near-optimal O(log T/sqrt T) in expectation and O(sqrt(log(1/delta))/sqrt T)-type high-probability rates for Lipschitz/smooth convex problems on general (unbounded) domains under sub-Gaussian noise.
- For smooth strongly convex problems, last-iterate rates O(1/T) in expectation and high probability are obtained without compactness, with step-size schedules that do not need M or sigma.
- Optimal O(1/sqrt T) rates for the last iterate under heavy-tailed noise (finite p-th moment) and sub-Weibull noise are obtained for known T with linearly decaying step sizes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a linearly decaying step size instead of the known-T schedule with a logarithmic factor | CSMD · General convex, finite variance, expectation | last-iterate function value gap: O\left(\frac{LD_{\psi}(x^{*},x^{1})}{T}+\frac{(M+\sigma)\sqrt{D_{\psi}(x^{*},x^{1})\log T}}{\sqrt{T}}\right) -> O\left(\ | Helped |
| Use a linearly decaying step size instead of the known-T schedule with a logarithmic factor | CSMD · General convex, finite variance, high probability | last-iterate function value gap: O\left(\frac{LD_{\psi}(x^{*},x^{1})}{T}+\frac{(M+\sigma\sqrt{\log\frac{1}{\delta}})\sqrt{D_{\psi}(x^{*},x^{1})\log T}}{\ | Helped |
| Use the new step size combining classical and linearly decaying schedules | CSMD · Strongly convex, finite variance, expectation | last-iterate function value gap: O\left(\frac{LD_{\psi}(x^{*},x^{1})}{\exp\left(\frac{T}{2+4\kappa_{f}}\right)}+\frac{(M^{2}+\sigma^{2})\log T}{\mu_{f}(T | Helped |
| Use the new step size combining classical and linearly decaying schedules | CSMD · Strongly convex, finite variance, high probability | last-iterate function value gap: O\left(\frac{\mu_{f}(1+\kappa_{f})D_{\psi}(x^{*},x^{1})}{\exp\left(\frac{T}{3+4\kappa_{f}}\right)}+\frac{(M^{2}+\sigma^{ | Helped |
| Use a linearly decaying step size instead of the known-T heavy-tailed schedule with logarithmic factors | CSMD · General convex, heavy-tailed noise, expectation | last-iterate function value gap: O\left(\frac{L\left[D_{\psi}(x^{*},x^{1})\right]^{2-\frac{2}{p}}(\log T)^{\frac{2}{p}-1}}{T^{2-\frac{2}{p}}}+\frac{(M+\s | Helped |
| Use a linearly decaying step size instead of the known-T sub-Weibull schedule with a logarithmic factor | CSMD · General convex, sub-Weibull noise, high probability | last-iterate function value gap: O\left(\frac{LD_{\psi}(x^{*},x^{1})}{T}+\frac{(M+\sigma\sqrt{C(\delta,p)})\sqrt{D_{\psi}(x^{*},x^{1})\log T}}{\sqrt{T}}\ | Helped |
| Use a fixed schedule with T known rather than a schedule for unknown T | CSMD · General convex, finite variance, expectation | last-iterate function value gap: O\left(\frac{LD_{\psi}(x^{*},x^{1})}{T}+\frac{(M+\sigma)\sqrt{D_{\psi}(x^{*},x^{1})}\log T}{\sqrt{T}}\right) -> O\left(\ | Helped |
| Use a fixed schedule with T known rather than a schedule for unknown T | CSMD · General convex, finite variance, high probability | last-iterate function value gap: O\left(\frac{LD_{\psi}(x^{*},x^{1})}{T}+\frac{(M+\sigma\sqrt{\log\frac{1}{\delta}})\sqrt{D_{\psi}(x^{*},x^{1})}\log T}{\ | Helped |
Surprising findings
- The high-probability last-iterate bound for convex problems holds without clipping, unlike prior averaged-iterate high-probability results which required clipping.
Limitations
- High-probability heavy-tailed bounds are not provided without clipping; only in-expectation results are given under heavy-tailed noise.
- Strongly convex analysis is restricted to mu_f>0 with mu_h=0 in the main text; results for log T factors remain in some step size schedules.
Experimental setup
Metrics: function value gap F(x^{T+1})-F(x^*) convergence rate in T and log(1/delta)
Baselines: Shamir and Zhang 2013 last-iterate rates Harvey et al. 2019 high-probability last-iterate bounds Jain et al. 2019 (smooth last-iterate) Zamani and Glineur 2023
Builds on: stochastic mirror descent composite stochastic mirror descent last-iterate analysis of Orabona/Shamir-Zhang style averaging
Closest papers by meaning
- Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime (NeurIPS 2025 · similarity 0.93)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.93)
- High Probability Convergence of Stochastic Gradient Methods (ICML 2023 · similarity 0.92)
- Derivatives of Stochastic Gradient Descent in parametric optimization (NeurIPS 2024 · similarity 0.90)
- Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization (ICML 2025 · similarity 0.90)
- High-probability complexity bounds for stochastic non-convex minimax optimization (NeurIPS 2024 · similarity 0.89)
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.