# Fast Mixing of Multi-Scale Langevin Dynamics under the Manifold Hypothesis

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2020.

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

- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Gotta Go Fast When Generating Data with Score-Based Models](https://mlsanity.com/paper/2105.14080/) (2021)
- [Stochastic Image Denoising by Sampling from the Posterior Distribution](https://mlsanity.com/paper/2101.09552/) (2021)
- [Provable Guarantees for Generative Behavior Cloning: Bridging Low-Level Stability and High-Level Behavior](https://mlsanity.com/paper/2307.14619/) (2023)
- [Diffusion models for Handwriting Generation](https://mlsanity.com/paper/2011.06704/) (2020)
- [Intrinsic Dimension Estimation Using Wasserstein Distances](https://mlsanity.com/paper/2106.04018/) (2021)
- [Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problems](https://mlsanity.com/paper/2206.09104/) (2022)
- [Wavelet Transform-assisted Adaptive Generative Modeling for Colorization](https://mlsanity.com/paper/2107.04261/) (2021)
- [Conditionally Strongly Log-Concave Generative Models](https://mlsanity.com/paper/2306.00181/) (2023)
- [Higher Order Generalization Error for First Order Discretization of Langevin Diffusion](https://mlsanity.com/paper/2102.06229/) (2021)
- [Blessing of Dimensionality for Approximating Sobolev Classes on Manifolds](https://mlsanity.com/paper/2408.06996/) (2024)

## Abstract (arXiv)

Recently, the task of image generation has attracted much attention. In particular, the recent empirical successes of the Markov Chain Monte Carlo (MCMC) technique of Langevin Dynamics have prompted a number of theoretical advances; despite this, several outstanding problems remain. First, the Langevin Dynamics is run in very high dimension on a nonconvex landscape; in the worst case, due to the NP-hardness of nonconvex optimization, it is thought that Langevin Dynamics mixes only in time exponential in the dimension. In this work, we demonstrate how the manifold hypothesis allows for the considerable reduction of mixing time, from exponential in the ambient dimension to depending only on the (much smaller) intrinsic dimension of the data. Second, the high dimension of the sampling space significantly hurts the performance of Langevin Dynamics; we leverage a multi-scale approach to help ameliorate this issue and observe that this multi-resolution algorithm allows for a trade-off between image quality and computational expense in generation.