Oracle lower bounds for stochastic gradient sampling algorithms

DOI10.3150/21-BEJ1377zbMath1489.60125arXiv2002.00291OpenAlexW3003921807MaRDI QIDQ2137007

Philip M. Long, Niladri S. Chatterji, Bartlett, Peter L.

Publication date: 16 May 2022

Published in: Bernoulli (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.00291

zbMATH Keywords

Markov chain Monte Carloinformation theoretic lower boundssampling lower boundsstochastic gradient Monte Carlo

Mathematics Subject Classification ID

Bayesian problems; characterization of Bayes procedures (62C10) Monte Carlo methods (65C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dispersion of mass and the complexity of randomized geometric algorithms
• Exponential convergence of Langevin distributions and their discrete approximations
• Langevin diffusions and Metropolis-Hastings algorithms
• Sampling from a log-concave distribution with projected Langevin Monte Carlo
• Isoperimetric problems for convex bodies and a localization lemma
• Rates of convergence of the Hastings and Metropolis algorithms
• Hit-and-run mixes fast
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Couplings and quantitative contraction rates for Langevin dynamics
• Nonasymptotic convergence analysis for the unadjusted Langevin algorithm
• Langevin diffusions and the Metropolis-adjusted Langevin algorithm
• Proximal Markov chain Monte Carlo algorithms
• Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed over Bounded Regions
• The geometry of logconcave functions and sampling algorithms
• Handbook of Markov Chain Monte Carlo
• Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• High-Dimensional Statistics
• Nonasymptotic mixing of the MALA algorithm
• Estimating normalizing constants for log-concave distributions: algorithms and lower bounds
• Foundations of Modern Probability
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Information-Based Complexity, Feedback and Dynamics in Convex Programming
• Hit-and-Run Algorithms for Generating Multivariate Distributions
• Sufficiency and Approximate Sufficiency
• Hit-and-Run from a Corner
• Theoretical Guarantees for Approximate Sampling from Smooth and Log-Concave Densities
• Equivalent Comparisons of Experiments