High-Accuracy Log-Concave Sampling with Stochastic Queries

Abstract

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 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 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 Θ(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.