# On Riemannian Stochastic Approximation Schemes with Fixed Step-Size

arXiv: https://arxiv.org/abs/2102.07586 · HTML: https://mlsanity.com/paper/2102.07586/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 51 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Builds on (most cited first, 17 of 17)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [First-order Methods for Geodesically Convex Optimization](https://mlsanity.com/paper/1602.06053/) (2016)
- [Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains](https://mlsanity.com/paper/1707.06386/) (2017)
- [Gradient Descent Learns Linear Dynamical Systems](https://mlsanity.com/paper/1609.05191/) (2016)
- [Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds](https://mlsanity.com/paper/1605.07147/) (2016)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Averaging Stochastic Gradient Descent on Riemannian Manifolds](https://mlsanity.com/paper/1802.09128/) (2018)
- [A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization](https://mlsanity.com/paper/1910.10782/) (2019)
- [Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method](https://mlsanity.com/paper/1511.04777/) (2015)
- [An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization](https://mlsanity.com/paper/1706.03267/) (2017)
- [Convergence Analysis of Riemannian Stochastic Approximation Schemes](https://mlsanity.com/paper/2005.13284/) (2020)
- [Stochastic Primal-Dual Method on Riemannian Manifolds with Bounded Sectional Curvature](https://mlsanity.com/paper/1703.08167/) (2017)
- [On the Effectiveness of Richardson Extrapolation in Machine Learning](https://mlsanity.com/paper/2002.02835/) (2020)
- [Variance reduction for Riemannian non-convex optimization with batch size adaptation](https://mlsanity.com/paper/2007.01494/) (2020)

## Built on by (most cited first, 12 of 12)

- [Metropolis Sampling for Constrained Diffusion Models](https://mlsanity.com/paper/2307.05439/) (2023)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization](https://mlsanity.com/paper/2111.06328/) (2021)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [Backward error analysis and the qualitative behaviour of stochastic optimization algorithms: Application to stochastic coordinate descent](https://mlsanity.com/paper/2309.02082/) (2023)
- [Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA](https://mlsanity.com/paper/2404.06023/) (2024)
- [Riemannian stochastic approximation algorithms](https://mlsanity.com/paper/2206.06795/) (2022)
- [Stochastic Modified Flows for Riemannian Stochastic Gradient Descent](https://mlsanity.com/paper/2402.03467/) (2024)
- [Faster Convergence of Riemannian Stochastic Gradient Descent with Increasing Batch Size](https://mlsanity.com/paper/2501.18164/) (2025)
- [The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium](https://mlsanity.com/paper/2206.04993/) (2022)
- [Tame Riemannian Stochastic Approximation](https://mlsanity.com/paper/2302.00709/) (2023)
- [Stochastic gradient descent with discontinuity across a manifold](https://mlsanity.com/paper/2608.07618/) (2026)

## Abstract (arXiv)

This paper studies fixed step-size stochastic approximation (SA) schemes, including stochastic gradient schemes, in a Riemannian framework. It is motivated by several applications, where geodesics can be computed explicitly, and their use accelerates crude Euclidean methods. A fixed step-size scheme defines a family of time-homogeneous Markov chains, parametrized by the step-size. Here, using this formulation, non-asymptotic performance bounds are derived, under Lyapunov conditions. Then, for any step-size, the corresponding Markov chain is proved to admit a unique stationary distribution, and to be geometrically ergodic. This result gives rise to a family of stationary distributions indexed by the step-size, which is further shown to converge to a Dirac measure, concentrated at the solution of the problem at hand, as the step-size goes to 0. Finally, the asymptotic rate of this convergence is established, through an asymptotic expansion of the bias, and a central limit theorem.