Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems

Kevin Kurian Thomas Vaidyan; Ahmet Alacaoglu; Michael P. Friedlander

math.OCNov 5, 2026

Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems

Authors: Kevin Kurian Thomas Vaidyan, Ahmet Alacaoglu, Michael P. Friedlander

Organizations: Department of Computer Science, University of British Columbia · Department of Computer Science and Mathematics, University of British Columbia

Abstract

Last-iterate convergence guarantees for stochastic gradient methods have attracted significant attention as practical implementations typically return the last iterate instead of an average of the iterates. In this paper, we study two approaches for analyzing the last-iterate convergence of proximal and projected stochastic gradient methods without bounded domain or bounded variance assumptions, where black-box variational inference serves as a running example. Under two related assumptions relaxing the bounded variance, we show near-optimal anytime rate $\widetilde{\mathcal{O}}(1/\sqrt{T})$ for the last iterate. Moreover, when the horizon $T$ is known, we remove the logarithmic factor and obtain the optimal order $\mathcal{O}(1/\sqrt{T})$ , matching the order known under bounded variance or bounded domain assumptions.

Figures & tables

Property	( CW ) Assumption	( B-G ) Assumption
Allows nonconvex $f_{i}$	$\times$	$\checkmark$
Allows nonsmooth $f_{i}$	$\times$	$\checkmark$
Control mechanism	ABC-type inequality ( 1.6 )	Iterates bounded in expectation
Step size regimes	$\tau_{t}\leq\frac{1}{4L\sqrt{t+1}}$	$\sum_{t=1}^{T}\tau_{t}^{2}=\mathcal{O}(1)$

Table 1: Comparison of the assumptions considered in this paper.

Reference	Constrained / Regularized	Assumptions	Anytime rate	Horizon-dependent rate
Shamir and Zhang (2013)	✓	Bdd gradients/domain	$\mathcal{O}\!\left(\frac{\ln T}{\sqrt{T}}\right)$	–
Jain et al. (2019)	✓	Bdd gradients/domain	–	$\mathcal{O}\!\left(\frac{1}{\sqrt{T}}\right)$
Liu and Zhou (2024)	✓	Bdd variance	$\mathcal{O}\!\left(\frac{\ln T}{\sqrt{T}}\right)$	$\mathcal{O}\!\left(\frac{1}{\sqrt{T}}\right)$
Garrigos et al. (2025) ; Attia et al. (2025)	$\times$	( CW )	–	$\mathcal{O}\!\left(\frac{\ln T}{\sqrt{T}}\right)$
Vaidyan et al. (2026)	✓	( CW )	–	$\mathcal{O}\!\left(\frac{\ln T}{\sqrt{T}}\right)$
This work	✓	( B-G )	$\mathcal{O}\!\left(\frac{\ln T}{\sqrt{T}}\right)$	$\mathcal{O}\!\left(\frac{1}{\sqrt{T}}\right)$

Table 2: Comparison with existing last-iterate convergence results for SGD variants.

Last-Iterate Convergence

Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.

See all 45 papers

Jun 23, 2026

New Bounds for the Last Iterate of the Stochastic subGradient Method

We study the last iterate of the stochastic subgradient method for one-dimensional convex Lipschitz objectives. For a fixed horizon

n

, we consider the standard fixed stepsizes

η=Θ(1/\sqrt n)

. We prove that, for such stepsize policies, under additive i.i.d. subgradient noise with uniformly bounded variance, the last iterate features an optimization error of order

1/\sqrt n

, thereby removing the extra

(\log n)

factor present in existing generic bounds. On the other hand, we show that without the i.i.d. assumption, the optimization error can be of order

(\log n)/\sqrt n

. Thus, under the uniformly bounded variance assumption alone, the last iterate of SsGM is suboptimal even in dimension one, resolving negatively an open problem posed in Koren and Segal, COLT, 2020.

Guglielmo Beretta, Tommaso Cesari, Roberto Colomboni +1

Department of Computer Science, Aarhus University, Aarhus, Denmark · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

Stochastic Optimization Last-Iterate Convergence Convergence Analysis Stochastic Optimization Convergence Nonsmooth Convex Optimization

Ask PDF

Apr 15, 2026

Gradient Descent's Last Iterate is Often (slightly) Suboptimal

We consider the well-studied setting of minimizing a convex Lipschitz function using either gradient descent (GD) or its stochastic variant (SGD), and examine the last iterate convergence. We prove that

Θ(\sqrt{\log(T)/T})

is the optimal anytime rate attainable with a fixed stepsize schedule (that does not depend on the total number of steps

T

). The upper bound holds already for SGD, and improves on the

\log(T)/\sqrt{T}

rate of Shamir and Zhang [2013], as well as the

\sqrt{\log(T)/T}

rate of Zamani and Glineur [2023] which was proven only for deterministic GD. The matching lower bound holds already for GD, and confirms the conjecture of Jain et al. [2019], namely that the optimal

1/\sqrt{T}

rate for the last iterate cannot be obtained without prior knowledge of

T

Guy Kornowski, Ohad Shamir

Institute for Advanced Study · Weizmann Institute of Science · University of Toronto and the Vector Institute

Last-Iterate Convergence Gradient Descent Stochastic Gradient Descent

Ask PDF

Sep 26, 2026

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal last-iterate rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield high-probability average-iterate rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight

Ω(\log T/\sqrt T)

lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that

\log T

in existing average-iterate upper bounds is unavoidable. Finally, we show that this

\log T

loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates

{O}(1/\sqrt{T})

Weiming Ou, Xiao Wang

Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics

Convergence Analysis Adaptive Gradient Methods Last-Iterate Convergence

Ask PDF

Abstract

Last-Iterate Convergence

Explore similar work

New Bounds for the Last Iterate of the Stochastic subGradient Method

Gradient Descent's Last Iterate is Often (slightly) Suboptimal

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds