# Higher Order Generalization Error for First Order Discretization of Langevin Diffusion

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

## Key facts

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

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

- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [The non-convex Burer-Monteiro approach works on smooth semidefinite programs](https://mlsanity.com/paper/1606.04970/) (2016)
- [Global Non-convex Optimization with Discretized Diffusions](https://mlsanity.com/paper/1810.12361/) (2018)
- [Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond](https://mlsanity.com/paper/1906.07868/) (2019)
- [Riemannian Langevin Algorithm for Solving Semidefinite Programs](https://mlsanity.com/paper/2010.11176/) (2020)
- [Fast Mixing of Multi-Scale Langevin Dynamics under the Manifold Hypothesis](https://mlsanity.com/paper/2006.11166/) (2020)

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

- [Convergence of continuous-time stochastic gradient descent with applications to deep neural networks](https://mlsanity.com/paper/2409.07401/) (2024)

## Abstract (arXiv)

We propose a novel approach to analyze generalization error for discretizations of Langevin diffusion, such as the stochastic gradient Langevin dynamics (SGLD). For an ε tolerance of expected generalization error, it is known that a first order discretization can reach this target if we run Omega(ε-1 log (ε-1) ) iterations with Omega(ε-1) samples. In this article, we show that with additional smoothness assumptions, even first order methods can achieve arbitrarily runtime complexity. More precisely, for each N>0, we provide a sufficient smoothness condition on the loss function such that a first order discretization can reach ε expected generalization error given Omega( ε-1/N log (ε-1) ) iterations with Omega(ε-1) samples.