# Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms

arXiv: https://arxiv.org/abs/2602.05489 · HTML: https://mlsanity.com/paper/2602.05489/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 5 Feb 2026.

## Builds on (most cited first, 21 of 21)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Variance-Reduced Methods for Machine Learning](https://mlsanity.com/paper/2010.00892/) (2020)
- [Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity](https://mlsanity.com/paper/1810.05633/) (2018)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization](https://mlsanity.com/paper/2006.11573/) (2020)
- [Exact convergence rate of the last iterate in subgradient methods](https://mlsanity.com/paper/2307.11134/) (2023)
- [Towards Weaker Variance Assumptions for Stochastic Optimization](https://mlsanity.com/paper/2504.09951/) (2025)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [The Proximal Robbins-Monro Method](https://mlsanity.com/paper/1510.00967/) (2015)
- [Ergodic convergence of a stochastic proximal point algorithm](https://mlsanity.com/paper/1504.05400/) (2015)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similarity](https://mlsanity.com/paper/2502.03401/) (2025)
- [Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems](https://mlsanity.com/paper/2507.14122/) (2025)
- [Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization](https://mlsanity.com/paper/2505.23056/) (2025)
- [The Stochastic Multi-Proximal Method for Nonsmooth Optimization](https://mlsanity.com/paper/2505.12409/) (2025)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)

## Abstract (arXiv)

We analyze two classical algorithms for solving additively composite convex optimization problems where the objective is the sum of a smooth term and a nonsmooth regularizer: proximal stochastic gradient method for a single regularizer; and the randomized incremental proximal method, which uses the proximal operator of a randomly selected function when the regularizer is given as the sum of many nonsmooth functions. We focus on relaxing the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates. We prove the widetildeO(1/√T) rate of convergence for the last iterate of both algorithms under componentwise convexity and smoothness, which is optimal up to log terms. Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.