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

Abstract

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.