# High-accuracy log-concave sampling with stochastic queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 33 references that are in the map.
- First posted on arXiv 15 Feb 2026.

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

- [Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions](https://mlsanity.com/paper/2211.01916/) (2022)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Stochastic gradient Markov chain Monte Carlo](https://mlsanity.com/paper/1907.06986/) (2019)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [High-accuracy sampling for diffusion models and log-concave distributions](https://mlsanity.com/paper/2602.01338/) (2026)
- [Asymptotically Optimal Exact Minibatch Metropolis-Hastings](https://mlsanity.com/paper/2006.11677/) (2020)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [An Efficient Minibatch Acceptance Test for Metropolis-Hastings](https://mlsanity.com/paper/1610.06848/) (2016)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [Oracle Lower Bounds for Stochastic Gradient Sampling Algorithms](https://mlsanity.com/paper/2002.00291/) (2020)
- [Mini-batch Metropolis-Hastings MCMC with Reversible SGLD Proposal](https://mlsanity.com/paper/1908.02910/) (2019)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)

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

- [A proximal gradient algorithm for composite log-concave sampling](https://mlsanity.com/paper/2605.12461/) (2026)
- [Windowed thinning and query complexity for the bouncy particle and Zigzag samplers](https://mlsanity.com/paper/2607.28413/) (2026)

## Abstract (arXiv)

We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as polylog(1/δ), where δ is the desired target accuracy -- are achievable using stochastic gradients with subexponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs poly(1/δ) queries. We also give an information-theoretic argument that light-tailed stochastic gradients are necessary for high accuracy: for example, in the bounded variance case, we show that the minimax-optimal query complexity scales as Theta(1/δ). Our framework also provides similar high accuracy guarantees under stochastic zeroth order (value) queries, and an improved complexity result for sampling from finite-sum potentials.