{"id":"arxiv/2609.12590","url":"https://arxiv.org/abs/2609.12590","tags":["math.ST","cs.LG","math.PR"],"score":0,"title":"Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions","domain":"math.ST","source":"arxiv","authors":["Weiming Ou","Xiao Wang"],"reviews":0,"subject":"math.ST","summary":"We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\\geq1$. For $μ$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\\star$ in the ball $\\mathbb{B}(0,μ^{-1/2})$, and unbiased gradient oracles with variance at most $σ^2$, the minimax worst-case expected query complexity is $Θ\\left(\\log(1+κ)+\\frac{σ^2}{μ\\varepsilon}\\right)$, jointly optimal for the condition number $κ:=L/μ$, variance $σ^2\\ge 0$, and TV accuracy $0<\\varepsilon\\leq 1/10$. In the noiseless setting $σ=0$, this tight complexity…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-11","reactions":{}}