High-Accuracy Log-Concave Sampling with Stochastic Queries

Fan Chen, Sinho Chewi, Constantinos Daskalakis, Alexander Rakhlin
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1341-1372, 2026.

Abstract

We show that high-accuracy guarantees for log-concave sampling—that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/\delta)$, where $\delta$ is the desired target accuracy—are achievable using stochastic gradients with sub-exponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/\delta)$ 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/\delta)$. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-chen26g, title = {High-Accuracy Log-Concave Sampling with Stochastic Queries}, author = {Chen, Fan and Chewi, Sinho and Daskalakis, Constantinos and Rakhlin, Alexander}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {1341--1372}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/chen26g/chen26g.pdf}, url = {https://proceedings.mlr.press/v336/chen26g.html}, abstract = { We show that high-accuracy guarantees for log-concave sampling—that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/\delta)$, where $\delta$ is the desired target accuracy—are achievable using stochastic gradients with sub-exponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/\delta)$ 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/\delta)$. 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. } }
Endnote
%0 Conference Paper %T High-Accuracy Log-Concave Sampling with Stochastic Queries %A Fan Chen %A Sinho Chewi %A Constantinos Daskalakis %A Alexander Rakhlin %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-chen26g %I PMLR %P 1341--1372 %U https://proceedings.mlr.press/v336/chen26g.html %V 336 %X We show that high-accuracy guarantees for log-concave sampling—that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/\delta)$, where $\delta$ is the desired target accuracy—are achievable using stochastic gradients with sub-exponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/\delta)$ 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/\delta)$. 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.
APA
Chen, F., Chewi, S., Daskalakis, C. & Rakhlin, A.. (2026). High-Accuracy Log-Concave Sampling with Stochastic Queries. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:1341-1372 Available from https://proceedings.mlr.press/v336/chen26g.html.

Related Material