Stochastic Optimization Convergence

Follow this topic Ask about this topic

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

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

On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passes
Feb 24, 2026Boao Kong, Hengrui Zhang, Kun YuanStochastic Optimization Convergence Stochastic Gradient Descent
Peking University. · Sichuan University.
Generalized Random Direction Newton Algorithms for Stochastic Optimization
Feb 23, 2026Soumen Pachal, Prashanth L. A., Shalabh Bhatnagar +1Stochastic Optimization Stochastic Optimization Convergence
Indian Institute of Technology Madras · Indian Institute of Science, Bangalore · TCS Research, Chennai, India
Implicit Bias and Convergence of Matrix Stochastic Mirror Descent
Feb 22, 2026Danil Akhtiamov, Reza Ghane, Omead Pooladzandi +1Mirror Descent Stochastic Optimization Convergence
Electrical Engineering, Caltech, Pasadena, CA
Exponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression
Feb 21, 2026Sacchit Kale, Piyushi Manupriya, Pierre Marion +2Gradient Descent Stochastic Optimization Convergence
Undergraduate Programme Indian Institute of Science, Bangalore. · Dept. of Computer Science and Automation Indian Institute of Science, Bangalore. · Inria, Ecole Normale Supérieure PSL Research University, Paris, France.
Adam Improves Muon: Adaptive Moment Estimation with Orthogonalized Momentum
Feb 19, 2026Minxin Zhang, Yuxuan Liu, Hayden SchaefferDeep Learning Optimization Adaptive Gradient Methods
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095, USA
AdaGrad-Diff: a Corrected Version of the Adaptive Gradient Algorithm for Composite Optimization
Feb 13, 2026Matia Bojovic, Saverio Salzo, Massimiliano PontilAdaptive Gradient Methods Stochastic Optimization Convergence
Computational Statistics and Machine Learning, Istituto Italiano di Tecnologia, Genoa, Italy · Department of Mathematics, University of Genoa, Genoa, Italy · DIAG, Sapienza University of Rome, Rome, Italy +1
RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization
Feb 6, 2026El Mahdi Chayti, Mohamad FakhouriFrank-Wolfe Algorithms Second-Order Optimization
Machine Learning and Optimization Laboratory (MLO) EPFL, Switzerland
Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods
Feb 3, 2026Grigory Begunov, Alexander TyurinDistributed Optimization Stochastic Gradient Descent
AXXX, Moscow, Russia · Lomonosov Moscow State University, Moscow, Russia
Adaptive Momentum and Nonlinear Damping for Neural Network Training
Jan 30, 2026Aikaterini Karoni, Rajit Rajpal, Benedict Leimkuhler +1Momentum Methods Stochastic Optimization Convergence
School of Mathematics University of Bristol · School of Mathematics University of Edinburgh · CERMICS, CNRS, École des Ponts, Institut Polytechnique de Paris; Inria Paris, France
Breaking the Stochasticity Barrier: An Adaptive Variance-Reduced Method for Variational Inequalities
Jan 30, 2026Yungi Jeong, Takumi OtsukaNonconvex Stochastic Optimization Stochastic Optimization Convergence
Department of Mathematics, National University of Singapore · Department of Computer Science and Communication Engineering, Waseda University
Riemannian Lyapunov Framework: Optimization as Closed Loop Control on Riemannian Manifolds
Jan 29, 2026Yixuan Wang, Omkar Sudhir Patil, Warren E. DixonStochastic Optimization Convergence Gradient Descent Dynamics
Department of Mechanical and Aerospace Engineering University of Florida
Variance Reduction for Stochastic Switching in Functionally Constrained Federated Optimization
Jan 23, 2026Antesh Upadhyay, Sang Bin Moon, Zhankun Luo +1Federated Learning Stochastic Optimization
School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA
Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance
Nov 30, 2025Robin Yadav, Shuo Xie, Tianhao Wang +1Sign-Based Optimization Class-Imbalanced Learning
Toyota Technological Institute at Chicago · University of British Columbia · University of California, San Diego
Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates
Nov 14, 2025Dmitry Kovalev, Ekaterina BorodichNonconvex Stochastic Optimization Stochastic Optimization Convergence
Yandex Research
Adam symmetry theorem: characterization of the convergence of the stochastic Adam optimizer
Nov 10, 2025Steffen Dereich, Thang Do, Arnulf Jentzen +1Stochastic Optimization Stochastic 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 · School of Data Science and School of Artificial Intelligence, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China +1
Stochastic Difference-of-Convex Optimization with Momentum
Oct 20, 2025El Mahdi Chayti, Martin JaggiNonconvex Optimization Nonconvex Stochastic Optimization
Machine Learning and Optimization Laboratory (MLO), EPFL
Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization
Aug 31, 2025Laurent Condat, Peter RichtárikStochastic Optimization Nonconvex Stochastic Optimization
King Abdullah University of Science and Technology (KAUST) Thuwal, Kingdom of Saudi Arabia
Convergence of Stochastic Gradient Methods for Wide Two-Layer Physics-Informed Neural Networks for the Poisson Equation
Aug 29, 2025Bangti Jin, Longjun WuNeural PDE Solvers PDE Solving
Department of Mathematics, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong, P.R. China
Random Walk Learning and the Pac-Man Attack
Aug 1, 2025Xingran Chen, Parimal Parag, Rohit Bhagat +2Cybersecurity Decentralized Learning
Department of Electrical and Computer Engineering, Rutgers University, Piscataway Township, NJ 08854, USA · Department of Electrical Communication Engineering, Indian Institute of Science, Bangalore, Karnataka 560012, India
Better Convergence Guarantees for Sign-Based Momentum Methods
Jul 16, 2025Wei Jiang, Dingzhi Yu, Sifan Yang +3Sign-Based Optimization Momentum Methods
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China
On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm
May 17, 2025Huan Li, Yiming Dong, Zhouchen LinOptimization Convergence Analysis Stochastic Optimization Convergence
Institute of Robotics and Automatic Information Systems, College of Artificial Intelligence, Nankai University, Tianjin, China. · National Key Lab of General AI, School of Intelligence Science and Technology, Peking University, Beijing, China.
Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
May 6, 2025Max Qiushi Lin, Jincheng Mei, Matin Aghaei +6Multi-Armed Bandits Policy Gradient
Simon Fraser University · Google DeepMind · Google Research +1
A Provably Convergent Plug-and-Play Framework for Stochastic Bilevel Optimization
May 2, 2025Tianshu Chu, Dachuan Xu, Wei Yao +2Stochastic Bilevel Optimization Bilevel Optimization
Institute of Operations Research and Information Engineering, Beijing University of Technology · National Center for Applied Mathematics Shenzhen · National Center for Applied Mathematics Shenzhen, and Department of Mathematics, Southern University of Science and Technology +2
Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases
Apr 6, 2025Alkis Kalavasis, Anay Mehrotra, Felix ZhouLinear Regression Stochastic Optimization Convergence
Yale University
Preconditioned Inexact Stochastic ADMM for Deep Model
Feb 15, 2025Shenglong Zhou, Ouya Wang, Ziyan Luo +2Stochastic Optimization Deep Learning Optimization
School of Mathematics and Statistics, Beijing Jiaotong University, China · ITP Lab, Department of EEE, Imperial College London, UK · National Mobile Communications Research Laboratory, Southeast University, China
Convergence Rate Analysis of LION
Nov 12, 2024Yiming Dong, Huan Li, Zhouchen LinSign-Based Optimization Deep Learning Optimization
State Key Lab of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University, Beijing, 100871, China · Institute of Robotics and Automatic Information Systems, College of Artificial Intelligence, Nankai University, Tianjin, 300071, China · Pazhou Laboratory (Huangpu), Guangzhou, 510555, China
Convergence of Sharpness-Aware Minimization Algorithms using Increasing Batch Size and Decaying Learning Rate
Sep 16, 2024Hinata Harada, Hideaki IidukaSharpness-Aware Minimization Nonconvex Optimization
Meiji University, Japan
Learning rate adaptive stochastic gradient descent optimization methods: numerical simulations for deep learning methods for partial differential equations and convergence analyses
Jun 20, 2024Steffen Dereich, Arnulf Jentzen, Adrian RiekertAdaptive Learning Rate Stochastic Optimization Convergence
Institute for Mathematical Stochastics, University of Münster, Germany · School of Data Science and Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong, Shenzhen (CUHK-Shenzhen), China · Applied Mathematics: Institute for Analysis and Numerics, University of Münster, Germany
Convergence Analysis of Sequential Federated Learning on Heterogeneous Data
Nov 6, 2023Yipeng Li, Xinchen LyuNon-IID Federated Learning Stochastic Optimization Convergence
National Engineering Research Center for Mobile Network Technologies Beijing University of Posts and Telecommunications Beijing, 100876, China
Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
Feb 23, 2023El Mahdi Chayti, Martin Jaggi, Nikita DoikovSecond-Order Optimization Stochastic Optimization Convergence
Machine Learning and Optimization Laboratory (MLO), EPFL

Feb 24, 2026J/K move · Enter open · S save

On the Convergence of Stochastic Gradient Descent with Perturbed Forward-Backward Passes

Boao Kong, Hengrui Zhang, Kun Yuan

Peking University. · Sichuan University.

Stochastic Optimization Convergence Stochastic Gradient Descent Gradient Descent Dynamics Nonconvex Stochastic Optimization

Open paper AskPDF arXiv

We study stochastic gradient descent (SGD) for composite optimization problems with

N

sequential operators subject to perturbations in both the forward and backward passes. Unlike classical analyses that treat gradient noise as additive and localized, perturbations to intermediate outputs and gradients cascade through the computational graph, compounding geometrically with the number of operators. We present the first comprehensive theoretical analysis of this setting. Specifically, we characterize how forward and backward perturbations propagate and amplify within a single gradient step, derive convergence guarantees for both general non-convex objectives and functions satisfying the Polyak--Łojasiewicz condition, and identify conditions under which perturbations do not deteriorate the asymptotic convergence order. As a byproduct, our analysis furnishes a theoretical explanation for the gradient spiking phenomenon widely observed in deep learning, precisely characterizing the conditions under which training recovers from spikes or diverges. Experiments on logistic regression with convex and non-convex regularization validate our theories, illustrating the predicted spike behavior and the asymmetric sensitivity to forward versus backward perturbations.