Query limits exposed for advanced sampling from complex distributions
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
Computational ComplexityData Structures and Algorithms
Summary
Sampling means picking values from complicated probability shapes, which helps in statistics and machine learning. The authors show that for certain smooth and nicely curved high-dimensional shapes, any sampling method needs a lot more steps than previously thought, especially as dimensions grow. They prove this by designing tricky versions of shapes where sampling becomes surprisingly hard. This means some common assumptions about easy sampling from these shapes are incorrect, and more effort is needed for certain cases.
What this means in practice
- •For machine learning engineers: Understand limits on how fast sampling algorithms can run for complicated models with strong mathematical constraints.
- •For statistical modelers: Know which sampling tasks inherently require more computational effort due to the shape and smoothness of the target distribution.
A theory result. No direct application yet.
Authors
Huanjian Zhou, Taiji Suzuki
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 $κ=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 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.