{"id":"arxiv/2611.05813","url":"https://arxiv.org/abs/2611.05813","tags":["cs.CC","cs.DS","math.ST","stat.ML"],"score":0,"title":"Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities","domain":"cs.CC","source":"arxiv","authors":["Huanjian Zhou","Taiji Suzuki"],"reviews":0,"subject":"cs.CC","summary":"We study the query complexity of sampling from smooth distributions on $\\mathbb R^d$ using first-order oracles. For $d$-dimensional strongly log-concave targets with condition number $κ=2$, we prove that any randomized sampler requires $\\exp({Ω(\\log^{1/3} d)})$ queries even from a constant warm start. This rules out polylogarithmic dimension dependence and strictly separates strongly log-concave sampling from Gaussian sampling. For targets with $L$-smooth potentials satisfying an $α$-log-Sobolev inequality with $κ= L/α$, we prove an $Ω(κ)$ query lower bound for $d\\gtrsim\\log^2κ$. This shows…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}