High-accuracy log-concave sampling with stochastic queries

arXiv:2602.14342v2 Announce Type: replace-cross Abstract: We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as polylog(1/elta), where elta 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/elta) 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/elta). 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.

Source: arXiv cs.LG | 2026-05-18