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

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

  1. Enhancing SignSGD: Small-Batch Convergence Analysis and a Hybrid Switching Strategy

    Apr 28, 2026Haoran Chen, Wentao WangSign-Based OptimizationStochastic Optimization Convergence

    ´Ecole polytechnique Palaiseau, France

  2. From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability

    Apr 28, 2026Amir Ali Farzin, Philipp Braun, Iman ShamesZeroth-Order OptimizationStochastic Optimization Convergence

    School of Engineering · Australian National University · Canberra, ACT 2601 +3

  3. Complex Stochastic Gradient Descent and Directional Bias in Reproducing Kernel Hilbert Spaces

    Apr 24, 2026Natanael Alpay, Emeric BattagliaKernel RegressionReproducing Kernel Hilbert Spaces

  4. A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad, Shampoo and Muo

    Apr 19, 2026S. Gratton, Ph. L. TointMomentum MethodsNonconvex Stochastic Optimization

    Université de Toulouse, INP, IRIT, Toulouse, France. · Université de Toulouse, INP, IRIT, Toulouse, France, and NAXYS, University of Namur, Namur, Belgium.

  5. Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance

    Apr 17, 2026Arda Fazla, Ege C. Kaya, Antesh Upadhyay +1Stochastic OptimizationOracle Complexity

    School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

  6. StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models

    Apr 16, 2026Dingzhi Yu, Rui Pan, Yuxing Liu +1Stochastic OptimizationSign-Based Optimization

    University of Illinois Urbana-Champaign

  7. Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

    Apr 11, 2026Konstantinos Emmanouilidis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Rene VidalRandom ReshufflingRichardson Extrapolation

    Department of Computer Science, University of Pennsylvania · University of Wisconsin-Madison, Archimedes Research Unit

  8. Optimal Rates for Pure ε\varepsilon-Differentially Private Stochastic Convex Optimization with Heavy Tails

    Apr 7, 2026Andrew LowyHeavy-Tailed Stochastic OptimizationDifferential Privacy

    CISPA Helmholtz Center for Information Security

  9. Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization

    Mar 31, 2026Lam M. Nguyen, Dzung T. Phan, Jayant KalagnanamStochastic Optimization ConvergenceStochastic Gradient Descent

    IBM Research, Thomas J. Watson Research Center, Yorktown Heights, NY, USA

  10. Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

    Mar 31, 2026Kaustubh Kartikey, Shalabh BhatnagarStochastic OptimizationStochastic Optimization Convergence

  11. Gradient Manipulation in Distributed Stochastic Gradient Descent with Strategic Agents: Truthful Incentives with Convergence Guarantees

    Mar 30, 2026Ziqin Chen, Yongqiang WangDistributed TrainingDecentralized Learning

    Department of Electrical and Computer Engineering, Clemson University, Clemson, SC 29634 USA

  12. Optimization Trade-offs in Asynchronous Federated Learning: A Stochastic Networks Approach

    Mar 27, 2026Abdelkrim Alahyane, Céline Comte, Matthieu JonckheereAsynchronous Federated LearningFederated Learning

    LAAS-SARA · EMINES, Mohammed VI Polytechnic University, Ben Guerir, Morocco · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France +1

  13. RAMPAGE: RAndomized Mid-Point for debiAsed Gradient Extrapolation

    Mar 23, 2026Zhankun Luo, M. Berk Sahin, Antesh Upadhyay +2Extragradient MethodsStochastic Optimization Convergence

    Authors are with the School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA.

  14. On the Role of Batch Size in Stochastic Conditional Gradient Methods

    Mar 22, 2026Rustem Islamov, Roman Machacek, Aurelien Lucchi +3Stochastic OptimizationNeural Network Optimization

    University of Basel, Switzerland · MBZUAI, UAE · University of Bern, Switzerland +2

  15. Heavy-Tailed and Long-Range Dependent Noise in Stochastic Approximation: A Finite-Time Analysis

    Mar 20, 2026Siddharth Chandak, Anuj Yadav, Ayfer Ozgur +1Stochastic ApproximationStochastic Optimization Convergence

    Department of Electrical Engineering, Stanford University, CA, USA. · School of Computer & Communication Sciences, EPFL, Lausanne, Switzerland.

  16. Uniform a priori bounds and error analysis for the Adam stochastic gradient descent optimization method

    Mar 19, 2026Steffen Dereich, Thang Do, Arnulf JentzenStochastic OptimizationStochastic Optimization Convergence

    Institute for Mathematical Stochastics, Faculty of Mathematics and Computer Science, University of Münster, Germany · School of Data Science, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China · Department of Probability and Statistic, Institute of Mathematics, Vietnam Academy of Science and Technology, Vietnam +2

  17. Mirror Descent on Riemannian Manifolds

    Mar 18, 2026Jiaxin Jiang, Lei Shi, Jiyuan TanRiemannian OptimizationStochastic Optimization Convergence

    School of Mathematical Sciences, Fudan University, Shanghai 200433, China · Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China

  18. Shuffling the Stochastic Mirror Descent via Dual Lipschitz Continuity and Kernel Conditioning

    Mar 17, 2026Junwen Qiu, Leilei Mei, Junyu ZhangRandom ReshufflingStochastic Optimization

    Industrial Systems Engineering and Management, National University of Singapore

  19. Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions

    Mar 16, 2026Quoc Tran-Dinh, Nghia Nguyen-TrungStochastic OptimizationStochastic Optimization Convergence

    Department of Statistics and Operations Research The University of North Carolina at Chapel Hill 318 Hanes Hall, UNC-Chapel Hill, NC 27599-3260.

  20. High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

    Mar 15, 2026Avik Kar, Siddharth Chandak, Rahul Singh +3Optimization Convergence AnalysisStochastic Optimization Convergence

    Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. · Department of Electrical Engineering, Stanford University, Stanford, CA, USA. · CMAP, CNRS, École polytechnique, Institut Polytechnique ´de Paris, Palaiseau, France.

  21. Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization

    Mar 13, 2026Noel Smith, Andrzej RuszczynskiStochastic OptimizationStochastic Approximation

    Department of Management Science and Information Systems, Rutgers University

  22. Dual Space Preconditioning for Gradient Descent in the Overparameterized Regime

    Mar 11, 2026Reza Ghane, Danil Akhtiamov, Babak HassibiGradient DescentImplicit Bias

    Electrical Engineering Department, California Institute of Technology, Pasadena, CA 91125 USA · Computing + Mathematical Sciences Department, California Institute of Technology, Pasadena, CA 91125 USA

  23. A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method

    Mar 10, 2026Yuchen Fang, Jihun Kim, Sen Na +2Constrained OptimizationStochastic Optimization

    Department of Mathematics, University of California, Berkeley · Department of IEOR, University of California, Berkeley · School of Industrial and Systems Engineering, Georgia Tech +1

  24. SHANG++: Robust Stochastic Acceleration under Multiplicative Noise

    Mar 10, 2026Yaxin Yu, Long Chen, Minfu FengAccelerated Gradient MethodsStochastic Optimization Convergence

    School of Mathematics, Sichuan University, Chengdu, Sichuan, 610065, China · Department of Mathematics, University of California, Irvine, Irvine, CA, 92697, USA

  25. Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization

    Mar 6, 2026Ganzhao YuanNonconvex Stochastic OptimizationStochastic Optimization

    Shenzhen University of Advanced Technology (SUAT), China

  26. Why Adam Can Beat SGD: Second-Moment Normalization Yields Sharper Tails

    Mar 3, 2026Ruinan Jin, Yingbin Liang, Shaofeng ZouStochastic Optimization ConvergenceAdaptive Gradient Methods

    Department of Electrical and Computer Engineering, The Ohio State University, USA · School of Electrical, Computer and Energy Engineering, Arizona State University, USA

  27. HomeAdam: Adam and AdamW Algorithms Sometimes Go Home to Obtain Better Provable Generalization

    Mar 3, 2026Feihu Huang, Guanyi Zhang, Songcan ChenAdaptive Gradient MethodsNeural Network Generalization

    College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China · MIIT Key Laboratory of Pattern Analysis and Machine Intelligence, Nanjing, China

  28. Convex and Non-convex Federated Learning with Stale Stochastic Gradients: Diminishing Step Size is All You Need

    Mar 3, 2026Xinran Zheng, Tara Javidi, Behrouz TouriStochastic Optimization ConvergenceStochastic Gradient Descent

    University of Illinois Urbana-Champaign · University of California San Diego

  29. Mini-Batch Covariance, Diffusion Limits, and Oracle Complexity in Stochastic Gradient Descent: A Sampling-Design Perspective

    Mar 2, 2026Daniel Zantedeschi, Kumar MuthuramanStochastic Gradient DescentStochastic Optimization Convergence

    Muma College of Business, University of South Florida, Tampa, FL, USA · McCombs School of Business, University of Texas at Austin, Austin, TX, USA

  30. On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation

    Feb 27, 2026Yubo Zhou, Luo Luo, Guang Dai +1Stochastic Bilevel OptimizationImplicit Differentiation

    Xi’an Jiaotong University · Fudan University · SGIT AI Lab