# Fisher information lower bounds for sampling

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 50 references that are in the map.
- First posted on arXiv 5 Oct 2022.

## Builds on (most cited first, 30 of 31)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Convergence of score-based generative modeling for general data distributions](https://mlsanity.com/paper/2209.12381/) (2022)
- [Convergence for score-based generative modeling with polynomial complexity](https://mlsanity.com/paper/2206.06227/) (2022)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Non-asymptotic bounds for sampling algorithms without log-concavity](https://mlsanity.com/paper/1808.07105/) (2018)
- [Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry](https://mlsanity.com/paper/1911.01469/) (2019)
- [Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo](https://mlsanity.com/paper/1710.02736/) (2017)
- [Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond](https://mlsanity.com/paper/1906.07868/) (2019)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds](https://mlsanity.com/paper/1911.03043/) (2019)
- [Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms](https://mlsanity.com/paper/2002.00291/) (2020)
- [On the complexity of finding stationary points of smooth functions in one dimension](https://mlsanity.com/paper/2209.07513/) (2022)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)

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

- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization](https://mlsanity.com/paper/2401.05716/) (2024)
- [Query Lower Bounds for Diffusion Sampling](https://mlsanity.com/paper/2604.10857/) (2026)
- [Complexity of Non-Log-Concave Sampling in Fisher Information](https://mlsanity.com/paper/2605.15859/) (2026)
- [Smoothed Score Queries and the Complexity of Sampling](https://mlsanity.com/paper/2605.27769/) (2026)
- [Provable Quantum-Classical Separation for Continuous Gibbs Sampling](https://mlsanity.com/paper/2608.24527/) (2026)

## Abstract (arXiv)

We prove two lower bounds for the complexity of non-log-concave sampling within the framework of Balasubramanian et al. (2022), who introduced the use of Fisher information (FI) bounds as a notion of approximate first-order stationarity in sampling. Our first lower bound shows that averaged LMC is optimal for the regime of large FI by reducing the problem of finding stationary points in non-convex optimization to sampling. Our second lower bound shows that in the regime of small FI, obtaining a FI of at most varepsilon2 from the target distribution requires poly(1/varepsilon) queries, which is surprising as it rules out the existence of high-accuracy algorithms (e.g., algorithms using Metropolis-Hastings filters) in this context.