# Random Reshuffling for Stochastic Gradient Langevin Dynamics

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 56 references that are in the map.
- First posted on arXiv 27 Jan 2025.

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

- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [The promises and pitfalls of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1811.10072/) (2018)
- [Stochastic gradient Markov chain Monte Carlo](https://mlsanity.com/paper/1907.06986/) (2019)
- [Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimization](https://mlsanity.com/paper/1910.02008/) (2019)
- [Non-asymptotic bounds for sampling algorithms without log-concavity](https://mlsanity.com/paper/1808.07105/) (2018)
- [Control Variates for Stochastic Gradient MCMC](https://mlsanity.com/paper/1706.05439/) (2017)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1802.05431/) (2018)
- [Sampling from Bayesian Neural Network Posteriors with Symmetric Minibatch Splitting Langevin Dynamics](https://mlsanity.com/paper/2410.19780/) (2024)
- [The True Cost of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1706.02692/) (2017)
- [Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimension](https://mlsanity.com/paper/2108.00682/) (2021)
- [Unbiased Kinetic Langevin Monte Carlo with Inexact Gradients](https://mlsanity.com/paper/2311.05025/) (2023)
- [Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations](https://mlsanity.com/paper/2104.12384/) (2021)

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

- [Randomised Splitting Methods and Stochastic Gradient Descent](https://mlsanity.com/paper/2504.04274/) (2025)
- [A Langevin sampling algorithm inspired by the Adam optimizer](https://mlsanity.com/paper/2504.18911/) (2025)

## Abstract (arXiv)

We examine the use of different randomisation policies for stochastic gradient algorithms used in sampling, based on first-order (or overdamped) Langevin dynamics, the most popular of which is known as Stochastic Gradient Langevin Dynamics. Conventionally, this algorithm is combined with a specific stochastic gradient strategy, called Robbins-Monro. In this work, we study an alternative strategy, Random Reshuffling, and show convincingly that it leads to improved performance via: a) a proof of reduced bias in the Wasserstein metric for strongly convex, gradient Lipschitz potentials; b) an analytical demonstration of reduced bias for a Gaussian model problem; and c) an empirical demonstration of reduced bias in numerical experiments for some logistic regression problems. This is especially important since Random Reshuffling is typically more efficient due to memory access and cache reasons. Such acceleration for the Random Reshuffling policy is familiar from the optimisation literature on stochastic gradient descent.