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\ge 1$. 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 \epsilon }\right)$, jointly optimal for the condition number $\kappa :=L/\mu$, variance ${\sigma }^2\ge 0$, and TV accuracy $0<\epsilon \le 1/10$. In the noiseless setting $\sigma =0$, this tight complexity $\Theta \left(\log (1+\kappa )\right)$ is independent of $\epsilon$. 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 }\Vert x_0-x_f^{\star }\Vert )\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.

arXiv commentUnder Review