Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $$\begin{gathered} d \\ geq1 \end{gathered}$$. For $mu$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^{\star }$ in the ball $$\begin{gathered} mathbbB(0, \\ m{u}^{-1/2}) \end{gathered}$$, and unbiased gradient oracles with variance at most $sigm{a}^2$, the minimax worst-case expected query complexity is $$\begin{gathered} Theta \\ left( \\ log(1+\kappa )+ \\ frac \\ sigm{a}^2 \\ mu \\ varepsilon \\ right) \end{gathered}$$, jointly optimal for the condition number $$\begin{gathered} kappa:=L/ \\ mu \end{gathered}$$, variance $$\begin{gathered} sigm{a}^2 \\ ge0 \end{gathered}$$, and TV accuracy $$\begin{gathered} 0< \\ varepsilon \\ leq1/10 \end{gathered}$$. 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 $$\begin{gathered} mathbbB(0, \\ m{u}^{-1/2}) \end{gathered}$$, 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.