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 d≥1. For μ-strongly convex, L-smooth potentials with unknown minimizers xf^star in the ball mathbbB(0,μ-1/2), and unbiased gradient oracles with variance at most σ2, the minimax worst-case expected query complexity is Thetaleft(log(1+kappa)+fracσ2μvarepsilonright), jointly optimal for the condition number kappa:=L/μ, variance σ2≥ 0, and TV accuracy 0<varepsilon≤ 1/10. In the noiseless setting σ=0, this tight complexity Thetaleft(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 mathbbB(0,μ-1/2), exact sampling from any initial point x0 can be implemented with expected cost Oleft(log(1+kappa)+log(1+√μ|x0-xf^star|)right), without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.