Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

We study the almost sure convergence of the last-iterate optimization error of Stochastic (sub)Gradient Descent (SGD) for convex objectives. For smooth objectives, we establish convergence rates of order $k^{-1/3}$ when a stationary minimizer exists, and $k^{-1/4}$ otherwise, up to polylogarithmic factors, where $k$ denotes the iteration counter. We further show that the latter rate extends to nonsmooth convex objectives. All these rates are achieved by deterministic, anytime stepsize policies. Finally, we establish matching lower bounds showing that the exponents $-1/3$ and $-1/4$ are optimal, up to polylogarithmic factors, for the corresponding problem classes.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-18
DOI
https://doi.org/10.48550/arxiv.2611.24151
Primary Topic
Stochastic Gradient Optimization Techniques
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

Andrea Paudice, Weiming Ou, Xiao Wang
arXiv (Cornell University)
Stochastic Gradient Optimization Techniques
preprint

Nearly Tight Almost Sure Convergence Rates for the Last iterate of SGD

Andrea Paudice, Weiming Ou, Xiao Wang
preprint en

Abstract

We study the almost sure convergence of the last-iterate optimization error of Stochastic (sub)Gradient Descent (SGD) for convex objectives. For smooth objectives, we establish convergence rates of order $k^{-1/3}$ when a stationary minimizer exists, and $k^{-1/4}$ otherwise, up to polylogarithmic factors, where $k$ denotes the iteration counter. We further show that the latter rate extends to nonsmooth convex objectives. All these rates are achieved by deterministic, anytime stepsize policies. Finally, we establish matching lower bounds showing that the exponents $-1/3$ and $-1/4$ are optimal, up to polylogarithmic factors, for the corresponding problem classes.

arXiv (Cornell University)
Stochastic Gradient Optimization Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon