Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

תקציר מקורי באנגליתarXiv:2609.12590v1 Announce Type: cross Abstract: We investigate the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in any fixed Euclidean dimension. The potential is $\mu$-strongly convex and $L$-smooth, with an unknown mode in the ball of radius $\mu^{-1/2}$ about the origin. We have access to unbiased stochastic oracles with the variance at most $\sigma^2$. For every $\sigma^2\ge0$ and total variation (TV) accuracy $0<\varepsilon\le1/10$, we prove that the tight complexity of sampling a distribution within $\epsilon$-TV distance from the target distribution is \[ N^\star_{\text{TV}}=\Theta\!\left(\log(1+\kappa)+ \frac{\sigma^2}{\mu\epsilon}\right), \] where $\kappa:=\frac L\mu$ is the condition number. Note that this complexity bound is simult