Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

Abstract

We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is $\mu$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius ${\mu }^{-1/2}$ about the origin. We have access to unbiased stochastic oracles with the variance at most ${\sigma }^2$. For every ${\sigma }^2\ge 0$ and total variation (TV) accuracy $0<\epsilon \le 1/10$, we prove that the tight complexity of sampling a distribution within $\epsilon$-TV distance from the target distribution is \[ N^\star_{\text{TV}}=Θ\!\left(\log(1+κ)+ \frac{σ^2}{με}\right), \] where $\kappa :=\frac{L}{\mu }$ is the condition number. Note that this complexity bound is simultaneously tight for the condition number $\kappa$ and accuracy $\epsilon$. Besides, our tight complexity bound is adaptive to noiseless setting $\sigma =0$, which is $N_{\text{TV}}^{\star }=\Theta \left(\log (1+\kappa )\right)$.

55 pages