Stochastic Optimization Convergence

Overview

The field asks when algorithms that use random samples, approximate gradients, or delayed updates reach a solution or a stationary point, and how their error depends on computation and noise. Researchers analyze stochastic gradient descent and its momentum and adaptive variants alongside variance reduction, clipping, proximal and mirror methods, and second-order updates. Results cover convex and nonconvex learning as well as distributed, federated, bilevel, and reinforcement-learning settings, with guarantees often expressed as convergence rates or sample and communication complexity. A central challenge is to obtain sharp guarantees under realistic heavy-tailed or dependent noise without assumptions that exclude practical optimizers or obscure their failures.

Latest papers

CardsList

229 papers22 papers in the last four weeks, down 27% on the four weeks before. 0.2% of all new papers.

  1. Taming the Tails of Stochastic Gradient Descent in the Interpolation Regime

    Nov 18, 2026Leonardo Galli, Daniela Angela Parletta, Andrea PaudiceStochastic Optimization ConvergenceStochastic Gradient Descent

  2. Near-Optimal Methods for Generalized Lipschitz Convex Optimization

    Nov 15, 2026Dmitry Kovalev, Grigory MalinovskyNonsmooth Convex OptimizationStochastic Optimization Convergence

  3. Muon Attains O(ε−3)\mathcal{O}(\varepsilon^{-3}) Iteration Complexity under Shuffling

    Nov 13, 2026Kun Huang, Shi Pu, Karl Henrik JohanssonMuon OptimizerStochastic Optimization

  4. Improved last-iterate bounds for SGD with and without replacement

    Nov 10, 2026Yimin Zhong, Jiaxin ZhouLast-Iterate ConvergenceStochastic Optimization Convergence

  5. On Federated Averaging with Partial Participation under a General Variance Condition

    Nov 10, 2026Ziming Wang, Kun Huang, Karl Henrik Johansson +1Federated LearningFederated Learning Aggregation

  6. Dual-Space Preconditioning for Variational Inequalities and Root-Finding Problems

    Nov 10, 2026Jan Quan, Konstantinos Oikonomidis, Alexander Bodard +1Stochastic Optimization Convergence

  7. Coordinatewise Epsilon for Adam under Heavy-Tailed Noise

    Nov 6, 2026Jeonseong Kim, Chenglin FanStochastic Optimization ConvergenceAdaptive Gradient Methods

  8. O(1/n)O(1/n) Convergence Rate for RVI QQ-Learning

    Nov 5, 2026Avik Kar, Siddharth Chandak, Rahul Singh +1Reinforcement LearningQ-Learning

  9. Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems

    Nov 5, 2026Kevin Kurian Thomas Vaidyan, Ahmet Alacaoglu, Michael P. FriedlanderLast-Iterate ConvergenceStochastic Optimization Convergence

  10. When Does Design Thinking Work? A Convergence Theorem for the Iterate-Test Core

    Nov 2, 2026Paweł Kuraś, Adrian Michalski, Alicja Gerka +1Last-Iterate ConvergenceStochastic Optimization Convergence

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

    Oct 30, 2026Benjamin Grimmer, Qining ShenSmooth Convex OptimizationStochastic Gradient Descent

  12. Stochastic and Noisy Oracles in Smooth Continuous Optimization

    Oct 29, 2026Albert S. Berahas, Liyuan Cao, Katya ScheinbergStochastic Optimization ConvergenceOracle Complexity

  13. Adaptive Federated Optimization Across Smooth and Nonsmooth Regimes

    Oct 29, 2026Zimeng Wang, Ali Dadras, Alp YurtseverFederated LearningAdaptive Gradient Methods

  14. Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

    Oct 28, 2026Igor Sokolov, Alexander Tyurin, Peter RichtárikStochastic OptimizationStochastic Gradient Descent

  15. Non-Ergodic Markovian Mirror Descent with Unbounded Noise

    Oct 25, 2026Yunus Alp Biyikoglu, R. SrikantStochastic OptimizationStochastic Optimization Convergence

  16. Last-Iterate Stationarity of Muon with Finitely Many Newton-Schulz Iterations

    Oct 25, 2026Ping Li, Vincent Y. F. TanMuon OptimizerLast-Iterate Convergence

  17. On the Limits of Stochastic Push-Pull over Time-Varying Digraphs

    Oct 23, 2026Feiming Wang, Yutong He, Sulaiman Alghunaim +1Decentralized OptimizationStochastic Optimization Convergence

  18. When Momentum Helps Polyak--Ruppert Averaging

    Oct 20, 2026Alexandra Suvorikova, Darina Dvinskikh, Yuriy Dorn +1Stochastic OptimizationStochastic Optimization Convergence

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

    Oct 18, 2026Matan Schliserman, Tomer KorenSmooth Convex OptimizationLast-Iterate Convergence

  20. Global Convergence in Deep Networks via the Second Law of Thermodynamics

    Oct 17, 2026Matan Tsipory, Ofir Gaash, Itamar Harel +2Neural Network Training DynamicsStochastic Optimization Convergence

  21. Stochastic Gradient Descent: A Nonlinear Time Series Perspective

    Oct 14, 2026Jiaqi Li, Zhipeng Lou, Stefan Richter +1Richardson ExtrapolationStochastic Gradient Descent

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

    Oct 14, 2026Zijun Chen, Zihan ZhangStochastic OptimizationLast-Iterate Convergence

  23. Principled Design of Expected Improvement for Continuous Simulation Optimization

    Oct 13, 2026Songhao Wang, Jianglin Xia, Haowei Wang +1Stochastic OptimizationStochastic Optimization Convergence

  24. A Nonlinear Time-Series Theory for Constant-step SGD with Momentum

    Oct 12, 2026Younghun Lee, Jake Zummo, Wei Biao WuSGD with MomentumStochastic Gradient Descent