Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions

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 simultaneously tight for the condition number $\kappa$ and accuracy $\epsilon$. Besides, our tight complexity bound is adaptive to noiseless setting $\sigma=0$, which is $ N^\star_{\text{TV}}=\Theta\!\left(\log(1+\kappa)\right)$.

Statistics Theory (math.ST); Machine Learning (cs.LG); Probability (math.PR)

arXiv:2609.12590 [math.ST]

(or arXiv:2609.12590v1 [math.ST] for this version)

https://doi.org/10.48550/arXiv.2609.12590 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.