Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

Abstract

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\geq1$. For $\mu$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\star$ in the ball $\mathbb{B}(0,\mu^{-1/2})$, and unbiased gradient oracles with variance at most $\sigma^2$, the minimax worst-case expected query complexity is $\Theta\left(\log(1+\kappa)+\frac{\sigma^2}{\mu\varepsilon}\right)$, jointly optimal for the condition number $\kappa:=L/\mu$, variance $\sigma^2\ge 0$, and TV accuracy $0<\varepsilon\leq 1/10$. In the noiseless setting $\sigma=0$, this tight complexity $\Theta\left(\log(1+\kappa)\right)$ is independent of $\varepsilon$. Moreover, a gradient-only sampler generates an exact sample with ${O}(\log(1+\kappa))$ worst-case expected queries. Without previous ball $\mathbb{B}(0,\mu^{-1/2})$, exact sampling from any initial point $x_0$ can be implemented with expected cost ${O}\left(\log(1+\kappa)+\log(1+\sqrt{\mu}\|x_0-x_f^\star\|)\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.