Stochastic Optimization Convergence

Ask about this topic

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

210 papers28 papers in the last four weeks, up 22% on the four weeks before. 0.2% of all new papers.

  1. Adaptive Federated Optimization Across Smooth and Nonsmooth Regimes

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

    Department of Mathematics and Mathematical Statistics, Ume˚a University, Sweden

  2. Rennala NSGD: Asynchronous Stochastic Optimization Beyond Euclidean Geometry

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

    Center of Excellence for Generative AI, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia. · AXXX, Moscow, Russia. · Applied AI Institute, Moscow, Russia.

  3. Non-Ergodic Markovian Mirror Descent with Unbounded Noise

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

    ECE and CSL UIUC · ECE, CSL, and NCSA UIUC

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

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

    Department of Mathematics, National University of Singapore (NUS) · Department of Electrical and Computer Engineering, NUS

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

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

    School of Statistics and Data Science, Nankai University, Tianjin, China. · Center for Machine Learning Research, Peking University. · Electrical Engineering Department, Kuwait University.

  6. Characterizing Oblivious Common-Reward Multi-Player Bandits: Universal Stationarity, Coordination Traps, and Certified Global Rates

    Oct 21, 2026Mingxiao Li, Wenhai Lai, Hongyu WangMulti-Agent BanditsStochastic Optimization Convergence

  7. Convergence of stochastic gradient descent for learning linear neural networks

    Oct 20, 2026Gabin Maxime Nguegnang, Bubacarr Bah, Holger Rauhut +1Stochastic Optimization ConvergenceStochastic Gradient Descent

  8. When Momentum Helps Polyak--Ruppert Averaging

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

    Independent researcher · HSE University · MSU AI Institute +1

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

    Oct 18, 2026Matan Schliserman, Tomer KorenLast-Iterate ConvergenceStochastic Optimization Convergence

    Blavatnik School of Computer Science and AI, Tel Aviv University · Blavatnik School of Computer Science and AI, Tel Aviv University, and Google Research Tel Aviv

  10. 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

    Technion - Israel Institute of Technology, The Andrew and Erna Viterbi Faculty of Electrical & Computer Engineering, Technion City, Haifa 3200003, Israel. · Technion - Israel Institute of Technology, Faculty of Data and Decision Sciences, Technion City, Haifa 3200003, Israel. · Toyota Technological Institute at Chicago, Chicago, IL, USA.

  11. Stochastic Gradient Descent: A Nonlinear Time Series Perspective

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

    Department of Statistics, Rice University, USA · Department of Mathematics, University of California, San Diego, USA · Institute of Applied Mathematics, Heidelberg University, Germany +1

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

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

    Department of Computer Science and Engineering, Hong Kong University of Science and Technology

  13. A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus

    Oct 13, 2026Neil WaltonControl Lyapunov FunctionsStochastic Optimization Convergence

    Durham University

  14. Principled Design of Expected Improvement for Continuous Simulation Optimization

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

    College of Business, Southern University of Science and Technology, Shenzhen, CHINA · Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore, SINGAPORE

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

    Oct 12, 2026Younghun Lee, Jake Zummo, Wei Biao WuStochastic Gradient DescentStochastic Optimization Convergence

    Department of Statistics, University of Chicago

  16. Randomized Momentum Transport with Cheap Predictors

    Oct 9, 2026El Mahdi Chayti, Martin JaggiMomentum MethodsStochastic Optimization Convergence

    Machine Learning and Optimization Laboratory (MLO), EPFL

  17. Variance-Reduced Policy Gradient is Nearly Minimax-Optimal

    Oct 9, 2026Leonardo Cesani, Matteo Papini, Marcello RestelliPolicy GradientPolicy Gradient Methods

    Politecnico di Milano · Universit`a degli Studi di Milano

  18. Stochastic Gradient Descent Ascent is Suboptimal for Nonconvex-PŁ Min-Max Games

    Oct 6, 2026Junsoo HaOptimization Convergence AnalysisMin-Max Optimization

  19. A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization

    Oct 5, 2026Xingyu Chen, Ming Yang, Quanqi Hu +1Stochastic Bilevel OptimizationBilevel Optimization

    Department of Computer Science and Engineering Texas A&M University, College Station, USA

  20. Gaussian Limits for SGD Without Stationary Moments

    Oct 4, 2026Xiaoli Li, Wei Biao WuStochastic Optimization ConvergenceStochastic Gradient Descent

    University of Chicago

  21. Smoothed Gradient Method for Nonconvex Federated Stochastic Bilevel Optimization

    Oct 4, 2026Xinwen Zhang, Peiran Yu, Zhaosong Lu +1Gradient DescentNonconvex Stochastic Optimization

    Temple University · University of Texas at Arlington · University of Minnesota

  22. Convergence Analysis of STORM Under Different Geometries

    Oct 1, 2026Wei Jiang, Yibo Wang, Wenhao Yang +3Stochastic OptimizationLast-Iterate Convergence

    School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China

  23. Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization

    Oct 1, 2026Wei Jiang, Rui Yan, Sifan Yang +3Stochastic OptimizationMomentum Methods

    School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · School of Software Technology, Zhejiang University, Ningbo, China

  24. Exact information accounting for SGD methods

    Sep 30, 2026Akshay BalsubramaniNeural Network GeneralizationStochastic Optimization Convergence

  25. Convergence of Practical Muon with Finite Newton-Schulz Iterations and Nesterov Momentum

    Sep 30, 2026Hanyng Peng, Hui Wang, Yue YuNewton-Schulz IterationGradient Descent

    Pengcheng Laboratory, Shenzhen, China

  26. Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

    Sep 29, 2026Alexander Sholokhov, Alexander RogozinZeroth-Order OptimizationCovariance Matrix Adaptation Evolution Strategy

    Moscow Institute of Physics and Technology, Russia

  27. Adam under Generalized Smoothness with Second-Moment-Type Stochastic Gradients

    Sep 29, 2026Ruinan Jin, Difei Cheng, Ling Chen +3Convergence AnalysisStochastic Optimization Convergence

    Mohamed bin Zayed University of Artificial Intelligence · Aerospace Information Technology University · The Ohio State University +2

  28. Stochastic Heavy Ball with Polyak Step Size and Armijo Line Search: A General Convergence Analysis

    Sep 29, 2026Jiawei Zhang, Qitan Shi, Yuantao GuStochastic OptimizationStochastic Optimization Convergence

    Tsinghua University

  29. Second-Moment Stochastic Approximation Methods

    Sep 29, 2026Tao Jiang, Lin XiaoStochastic ApproximationMuon Optimizer

    Fundamental AI Research (FAIR), Meta Superintelligence Labs

  30. Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis

    Sep 28, 2026Christopher De Sa, Thomas Dybdahl Ahle, Yaroslav Bulatov +1Random ReshufflingStochastic Optimization Convergence

    Together.AI, Cornell University · Normal Computing · Stanford University