Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

Source abstract

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