Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
math.ST, cs.LG, math.PR, stat.TH
Submitted: 2026-09-11
Updated: 2026-09-26
Comments: 55 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension.
Terminology
Abstract
We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is μ-strongly convex and L-smooth, with an unknown mode in the ball of radius μ-1/2 about the origin. We have access to unbiased stochastic oracles with the variance at most σ squared. For every σ 2 0 and total variation (TV) accuracy 0< epsilon 1/10, we prove that the tight complexity of sampling a distribution within ε-TV distance from the target distribution is [ N TV=Θ! ((1+κ)+ σ squared over με),] where κ:= Lμ is the condition number. Note that this complexity bound is simultaneously tight for the condition number κ and accuracy ε. Besides, our tight complexity bound is adaptive to noiseless setting σ=0, which is N TV=Θ! ((1+κ)).
Sources
- Faster high-accuracy log-concave sampling via algorithmic warm starts
- The pseudo-marginal approach for efficient Monte Carlo computations
- Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms
- High-accuracy sampling for diffusion models and log-concave distributions
- High-accuracy log-concave sampling with stochastic queries
- Smoothed Picard Hamiltonian Monte Carlo
- Exact simulation of diffusions and improved algorithms for log-concave sampling
- Query lower bounds for log-concave sampling
- Theoretical guarantees for approximate sampling from smooth and log-concave densities
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
Related papers
- Conformal Prediction for Dyadic Regression Under Complex Missingness
- Bentkus-type asymptotic e-values
- High-Dimensional Asymptotics of Differentially Private PCA
- KL Convergence Guarantees for Score diffusion models under minimal data assumptions
- Geometric bias in eigenspace perturbation under random heterogeneous noise
- On the Asymptotic Inadmissibility of Double Machine Learning Estimators Under Structure-Agnostic Models