CS Paper Radar

Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation

Ramanan Tamizholi, Siddharth Chandak, Rahul Singh

cs.LG math.OCeess.SY ·submitted 2026-11-10 10:04 UTC · v1

Abstract

We establish last-iterate mean-square residual bounds for nonexpansive stochastic approximation (SA), or stochastic Krasnoselskii-Mann (KM) iterations. In particular, we consider fixed-point mappings that are nonexpansive with respect to the Euclidean norm, and focus on polynomially decaying stepsizes. We study three conditions on the conditional second moment of the noise, and obtain bounds that are optimal up to logarithmic factors in each case. When it scales linearly with the squared residual, the best rate is $O(1/k^{1-ε})$ for any $ε>0$. In this case, for all considered stepsizes, our bounds match those of the noiseless KM iteration. When it is bounded by a constant, the best rate is $O(\log^2 k/\sqrt{k})$. When it scales affinely with the squared norm of the iterate, the best rate is $O(1/k^{1/2-ε})$, and the mean-square residual can diverge if the stepsizes are not square-summable. Thus, unlike for contractive SA, square-summable stepsizes are necessary for nonexpansive SA. We demonstrate how various algorithms with cocoercive maps, such as stochastic gradient descent, linear SA, and learning in cocoercive games, fit into our framework, and how the different noise conditions arise in each of them.

Comment
23 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity

cs.LG stat.MLmath.OC ·2026-09-22 ·Tong Yang, Tao Jiang, Yuejie Chi, Ashok Cutkosky, Lin Xiao
theory similarity 0.76
Abstract

We analyze a simple stochastic inertial Krasnosel'skii--Mann (iKM) method for finding a fixed point of a nonexpansive operator in a real Hilbert space. Our method is obtained simply by adding two inertial extrapolations to stochastic KM [Bravo and Cominetti, 2024], and it retains one call to a possibly biased stochastic oracle per update and achieves sharp rates in both the stochastic and deterministic regimes. Specifically, with our proposed parameter schedule, we prove the following last-iterate fixed-point residual bound: \[ {O}\!\left(\frac{1}{K} +\frac{σ\log K}{\sqrt K} +\frac{B_K\log K}{K}\right), \] where $K$ is the horizon, $σ$ is the noise level and $B_K$ is the accumulated root-mean-square bias. When $B_K=O(\sqrt K)$, this yields $\widetilde O(ε^{-2})$ sample complexity that matches, up to a logarithmic factor, the stochastic-oracle lower bound given under the unbiased subclass of our model [Foster et al., 2019, Theorem 2]. It also improves the best-known $O(ε^{-4})$ random-iterate guarantee for stochastic KM [Bravo and Cominetti, 2024, Corollary 5.4]. To our knowledge, this is the first single-loop method for general nonexpansive fixed-point problems to attain this near-optimal sample complexity without variance reduction or batching. When the oracle is exact, the same method attains the worst-case-optimal $O(K^{-1})$ last-iterate residual rate [Park and Ryu, 2022, Theorem 4.6], improving the $O(K^{-1/2})$ rate of classical KM [Cominetti et al., 2014; Bravo and Cominetti, 2018].

0.27

Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

cs.LG ·2026-10-18 ·Matan Schliserman, Tomer Koren
theory similarity 0.69
Abstract

We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance $σ_\star^2$ of the stochastic gradients at the optimum is small or zero. We establish that after $T$ steps of SGD on $β$-smooth convex losses with any constant stepsize $0<η<2/β$, the last iterate attains expected excess risk $\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)$, which gives the rate $\smash{\widetilde O(1/T)}$ for every constant stepsize in the interpolation regime ($σ_\star=0$), matching the $Ω(1/T)$ lower bound up to logarithmic factors and improving upon the $O(1/\sqrt T)$ rate of Attia et al. (2026) for $η=1/β$. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an $O(1/T)$ rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an arguably simpler proof.

0.32

$O(1/n)$ Convergence Rate for RVI $Q$-Learning

cs.LG ·2026-11-05 ·Avik Kar, Siddharth Chandak, Rahul Singh, Shalabh Bhatnagar
similarity 0.68
Abstract · 24 pages

We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) $Q$-learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'skiĭ--Mann iterations driven by a non-expansive, linearly regular map on a finite-dimensional normed space, we establish last-iterate mean-squared residual bounds under martingale-difference noise whose conditional second moment grows at most linearly with the squared residual. Suitable polynomial stepsizes of order $n^{-a}$ yield an $O(n^{-a})$ rate for $0<a\leq1$. We verify linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs. Applying the general result gives an $O(n^{-1})$ bound on the mean-squared Bellman span residual of RVI $Q$-learning iterates when a suitable stepsize sequence is used. The positive gap between optimal and suboptimal stationary deterministic policies then yields an $O(n^{-1})$ bound on the expected suboptimality of the greedy policy. Consequently, $O(ε^{-1})$ synchronous iterations suffice for an $ε$-optimal policy in expectation. These guarantees are instance-dependent, with constants that depend on the hitting-time parameters and the suboptimality gap of the second-best policy.

0.17

Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime

cs.LG math.OC ·2026-11-18 ·Leonardo Galli, Daniela Angela Parletta, Andrea Paudice
theory similarity 0.66
Abstract

In this paper, we study stochastic gradient descent in the smooth interpolation regime, where the population objective shares a common minimizer with the sample losses. In contrast to prior work, which has largely focused on in-expectation analysis, we obtain high-probability convergence guarantees under the same assumptions. In the convex case, we prove a fast rate of order $\log(β^{-1}) \cdot n^{-1}$ after $n$ iterations, with failure probability at most $β$. In the strongly convex case, we derive a family of moment-based bounds of order $β^{-p} \cdot \exp(-\mathcal{O}(p \cdot n))$ for $p \in (0,1]$, and complement them with a matching lower bound showing that the corresponding deterioration in the exponential rate is essentially unavoidable. In both settings, our theoretical results are unified across a broad class of step-size schedules. Building on this analysis, we extend our results to a low-noise regime and to nonconvex objectives satisfying the Polyak-Lojasiewicz condition.

0.08

Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

cs.LG math.OCstat.ML ·2026-10-14 ·Zijun Chen, Zihan Zhang
similarity 0.66
Abstract

Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex $L$-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order $1/L$. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components $n$. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying $0<η\lesssim 1/(L(1 + \log(nK)))$, where $K$ is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit $1/n$ factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.

0.38

Exact Theory and Optimal Stepsizes for Stochastic Gradient Descent in Smooth Convex Minimization

cs.LG math.OC ·2026-10-30 ·Benjamin Grimmer, Qining Shen
similarity 0.66
Abstract

This work considers the design of stepsize schedules for stochastic gradient descent in smooth convex optimization. Throughout, we assume that gradient noise is conditionally zero-mean with bounded variance. Among problems with dimension $d\geq N+1$, we provide an exact worst-case analysis of the expected suboptimality of stochastic gradient descent's final iterate. Our analysis applies to any (potentially nonconstant) schedule of $N$ stepsizes in $[0,1.5]^N$. Here, exact means that we provide a matching objective function and noise distributions where our guarantee is attained. Whenever the variance bound is at least $Ω(1/\sqrt{N})$, our theory provides the minimax optimal stepsize schedule for stochastic gradient descent and proves its uniqueness. These optimal stepsizes monotonically decrease, ruling out any accelerations in expected final suboptimality from fixed fractal schedules observed in the deterministic case.

0.28

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

cs.LG math.OC ·2026-09-26 ·Weiming Ou, Xiao Wang
similarity 0.66
Abstract · Under Review

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 \textbf{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 \textbf{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})$.

0.47

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

cs.LG stat.MLmath.OCmath.ST ·2026-10-31 ·Denis Belomestny, Alexey Naumov, Sergey Samsonov
theory similarity 0.65
Abstract

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $γ\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-γ}+n^{γ-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $γ$. The nonlinear bias contributes $n^{1/2-γ}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-γ)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $γ=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $γ$.

0.28