On the computational cost of Stochastic Gradient Langevin Dynamics
Abstract
Stochastic Gradient Langevin Dynamics (SGLD) reduces the cost of Langevin-based sampling by replacing full-dataset drift evaluations with mini-batch approximations, but the resulting subsampling error may offset this computational saving. We study this trade-off for stochastic differential equations with finite-sum drifts and compare the computational cost of SGLD with that of the Euler-Maruyama (EM) method. For a prescribed mean-square accuracy ε2, we derive complexity estimates that explicitly track the dependence on the dataset size m, mini-batch size s, and accuracy parameter ε. The resulting comparison reveals distinct parameter regimes in which either method is preferable. In particular, EM can have lower leading-order cost only in a small-data, aggressive-subsampling regime, whereas SGLD is favoured over most of the remaining parameter space. In the practically relevant regime s ≪ m, the transition between the two methods occurs at the scale m asymp ε−1. We complement the theoretical analysis with numerical experiments based on a Gaussian Bayesian inference model, which examine the predicted cost regimes together with the underlying discretisation error and variance estimates.
Related
- Theoretical guarantees for stochastic gradient Langevin dynamics
- Local Algebraic Stability of Wasserstein Gradient Descent-Ascent and Mean Field Langevin Dynamics without Spectral Gap
- Autonomous self-harmonic drift in Langevin dynamics causes a compaction of underlying domain for the density of Stochastic Localization
- A CONSTRAINED WASSERSTEIN GRADIENT FLOW FOR MEAN-FIELD LANGEVIN DYNAMICS
- Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials
BibTeX
@misc{majka2026computational,
title = {{On the computational cost of Stochastic Gradient Langevin Dynamics}},
author = {Mateusz B. Majka and Tigran Nagapetyan and Łukasz Szpruch and Yue Wu and Danqi Zhuang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17750},
eprint = {2609.17750},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17750},
}
RIS
TY - UNPB
TI - On the computational cost of Stochastic Gradient Langevin Dynamics
AU - Mateusz B. Majka
AU - Tigran Nagapetyan
AU - Łukasz Szpruch
AU - Yue Wu
AU - Danqi Zhuang
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17750
UR - https://arxiv.org/abs/2609.17750
AB - Stochastic Gradient Langevin Dynamics (SGLD) reduces the cost of Langevin-based sampling by replacing full-dataset drift evaluations with mini-batch approximations, but the resulting subsampling error may offset this computational saving. We study this trade-off for stochastic differential equations with finite-sum drifts and compare the computational cost of SGLD with that of the Euler-Maruyama (EM) method. For a prescribed mean-square accuracy ε^2, we derive complexity estimates that explicitly track the dependence on the dataset size m, mini-batch size s, and accuracy parameter ε. The resulting comparison reveals distinct parameter regimes in which either method is preferable. In particular, EM can have lower leading-order cost only in a small-data, aggressive-subsampling regime, whereas SGLD is favoured over most of the remaining parameter space. In the practically relevant regime s ≪ m, the transition between the two methods occurs at the scale m asymp ε^−1. We complement the theoretical analysis with numerical experiments based on a Gaussian Bayesian inference model, which examine the predicted cost regimes together with the underlying discretisation error and variance estimates.
ER -