Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

원문 초록

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 $\kappa=2$, we prove that any randomized sampler requires $\exp({\Omega(\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 $\alpha$-log-Sobolev inequality with $\kappa= L/\alpha$, we prove an $\Omega(\kappa)$ query lower bound for $d\gtrsim\log^2\kappa$. This shows that log-Sobolev sampling is strictly harder than strongly log-concave sampling. Our proofs construct instance-dependent tests that target samples typically pass but outputs of algorithms making few queries typically fail. For strongly log-concave targets, we embed a sequence of hidden Gaussian into high-degree tensor polynomial with smooth gates, forcing any algorithm to uncover the layers sequentially. The log-Sobolev construction hides a constant fraction of the target mass in angular caps while controlling the log-Sobolev constant via delicate estimates.