mlsanityData to 7 Oct 2026

Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms

arXiv 2602.05489 ↗First posted 5 Feb 2026math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

Builds on

21 of 38 references.

References · 21

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2023Handbook of Convergence Theorems for (Stochastic) Gradient Methodscited by 158
  3. 2020Better Theory for SGD in the Nonconvex Worldcited by 156
  4. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 132
  5. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  6. 2020Variance-Reduced Methods for Machine Learningcited by 79
  7. 2018Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivitycited by 61
  8. 2015Network Lasso: Clustering and Optimization in Large Graphscited by 42
  9. 2020Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimizationcited by 36
  10. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 35
  11. 2023Exact convergence rate of the last iterate in subgradient methodscited by 24
  12. 2024Dealing with unbounded gradients in stochastic saddle-point optimizationcited by 15
9 more
  1. 2015The Proximal Robbins-Monro Methodcited by 14
  2. 2025Towards Weaker Variance Assumptions for Stochastic Optimizationcited by 13
  3. 2015Ergodic convergence of a stochastic proximal point algorithmcited by 12
  4. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  5. 2025Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similaritycited by 5
  6. 2025Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problemscited by 5
  7. 2025The Stochastic Multi-Proximal Method for Nonsmooth Optimizationcited by 3
  8. 2025Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimizationcited by 3
  9. 2025Decentralized Optimization with Topology-Independent Communicationcited by 1

Built on by

Not cited yet.