# Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization arXiv: https://arxiv.org/abs/2111.06328 · HTML: https://mlsanity.com/paper/2111.06328/ ## Key facts - Cited by 13 papers in the map (data through 14 Oct 2026). - Builds on 17 of its 60 references that are in the map. - First posted on arXiv 11 Nov 2021. ## Builds on (most cited first, 17 of 17) - [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016) - [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018) - [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019) - [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018) - [Stochastic modified equations and adaptive stochastic gradient algorithms](https://mlsanity.com/paper/1511.06251/) (2015) - [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017) - [On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems](https://mlsanity.com/paper/2006.11144/) (2020) - [SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation](https://mlsanity.com/paper/2006.10311/) (2020) - [Convergence rates for the stochastic gradient descent method for non-convex objective functions](https://mlsanity.com/paper/1904.01517/) (2019) - [An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias](https://mlsanity.com/paper/2006.07904/) (2020) - [Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity](https://mlsanity.com/paper/1907.11331/) (2019) - [Linear Convergence of Adaptive Stochastic Gradient Descent](https://mlsanity.com/paper/1908.10525/) (2019) - [Convergence of constant step stochastic gradient descent for non-smooth non-convex functions](https://mlsanity.com/paper/2005.08513/) (2020) - [Analysis of Stochastic Gradient Descent in Continuous Time](https://mlsanity.com/paper/2004.07177/) (2020) - [On Riemannian Stochastic Approximation Schemes with Fixed Step-Size](https://mlsanity.com/paper/2102.07586/) (2021) - [Stochastic Gradient Descent in Continuous Time: A Central Limit Theorem](https://mlsanity.com/paper/1710.04273/) (2017) - [Logarithmic Heavy Traffic Error Bounds in Generalized Switch and Load Balancing Systems](https://mlsanity.com/paper/2003.07821/) (2020) ## Built on by (most cited first, 13 of 13) - [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022) - [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024) - [On Uniform Boundedness Properties of SGD and its Momentum Variants](https://mlsanity.com/paper/2201.10245/) (2022) - [Exponential Concentration in Stochastic Approximation](https://mlsanity.com/paper/2208.07243/) (2022) - [On the Impact of Output Perturbation on Fairness in Binary Linear Classification](https://mlsanity.com/paper/2402.03011/) (2024) - [A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques](https://mlsanity.com/paper/2403.11163/) (2024) - [Effect of Random Learning Rate: Theoretical Analysis of SGD Dynamics in Non-Convex Optimization via Stationary Distribution](https://mlsanity.com/paper/2406.16032/) (2024) - [Central Limit Theorems for Stochastic Gradient Descent Quantile Estimators](https://mlsanity.com/paper/2503.02178/) (2025) - [Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD](https://mlsanity.com/paper/2608.26765/) (2026) - [Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD](https://mlsanity.com/paper/2609.39144/) (2026) - [Gaussian Limits for SGD Without Stationary Moments](https://mlsanity.com/paper/2610.05599/) (2026) - [Limit Theory for Online Expectile Estimation under Short and Long Range Dependence](https://mlsanity.com/paper/2610.16030/) (2026) - [A Nonlinear Time-Series Theory for Constant-step SGD with Momentum](https://mlsanity.com/paper/2610.16034/) (2026) ## Abstract (arXiv) Stochastic approximation (SA) and stochastic gradient descent (SGD) algorithms are work-horses for modern machine learning algorithms. Their constant stepsize variants are preferred in practice due to fast convergence behavior. However, constant step stochastic iterative algorithms do not converge asymptotically to the optimal solution, but instead have a stationary distribution, which in general cannot be analytically characterized. In this work, we study the asymptotic behavior of the appropriately scaled stationary distribution, in the limit when the constant stepsize goes to zero. Specifically, we consider the following three settings: (1) SGD algorithms with smooth and strongly convex objective, (2) linear SA algorithms involving a Hurwitz matrix, and (3) nonlinear SA algorithms involving a contractive operator. When the iterate is scaled by 1/√α, where α is the constant stepsize, we show that the limiting scaled stationary distribution is a solution of an integral equation. Under a uniqueness assumption (which can be removed in certain settings) on this equation, we further characterize the limiting distribution as a Gaussian distribution whose covariance matrix is the unique solution of a suitable Lyapunov equation. For SA algorithms beyond these cases, our numerical experiments suggest that unlike central limit theorem type results: (1) the scaling factor need not be 1/√α, and (2) the limiting distribution need not be Gaussian. Based on the numerical study, we come up with a formula to determine the right scaling factor, and make insightful connection to the Euler-Maruyama discretization scheme for approximating stochastic differential equations.