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^2ge0 and total variation (TV) accuracy 0<arepsilonle1/10, we prove that the tight complexity of sampling a distribution within epsilon-TV distance from the target distribution is [ N^star_{ext{TV}}=Theta!left(log(1+kappa)+ frac{sigma^2}{muepsilon}right), ] where kappa:=frac Lmu 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_{ext{TV}}=Theta!left(log(1+kappa)right).

Related

• Smoothed Score Queries and the Complexity of Sampling
• High-accuracy log-concave sampling with stochastic queries
• A proximal gradient algorithm for composite log-concave sampling

Source: arXiv cs.LG | 2026-09-14