Optimal Last-Iterate Bounds for Nonexpansive Stochastic Approximation
Tamizholi et al.
Last-iterate mean-square residual bounds for stochastic Krasnoselskii-Mann iterations, optimal up to logarithms under three noise conditions, show that square-summable stepsizes are necessary.
Source published · In the Daily Brief of 13 November 2026
Filed under Optimization, Probability
The paper studies stochastic approximation with fixed-point maps that are nonexpansive in the Euclidean norm, the stochastic Krasnoselskii-Mann iteration, with polynomially decaying stepsizes. It bounds the mean-square residual of the last iterate under three conditions on the conditional second moment of the noise.
When the noise scales linearly with the squared residual, the best rate is \(O(1/k^{1-\epsilon})\) for any \(\epsilon > 0\), matching the noiseless iteration. When the noise is bounded, it is \(O(\log^2 k/\sqrt{k})\). When the noise grows affinely with the squared norm of the iterate, it is \(O(1/k^{1/2-\epsilon})\), and the residual can diverge unless the stepsizes are square-summable, unlike the contractive case.
Stochastic gradient descent with cocoercive maps, linear stochastic approximation and learning in cocoercive games fit the framework.