High-accuracy log-concave sampling with stochastic queries

We show that high-accuracy guarantees for log-concave sampling – that is, iteration and query complexities which scale as $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\log (1\mathrm{/}\delta )$, where $\delta$ 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 $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(1\mathrm{/}\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 $\mathrm{\Theta }(1\mathrm{/}\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.