Query lower bounds for log-concave sampling

Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving $\lt$bold$\gt$lower bounds$\lt$/bold$\gt$ for this task has remained elusive, with lower bounds previously known only in dimension one. In this work, we establish the following query lower bounds: (1) sampling from strongly log-concave and log-smooth distributions in dimension $d \geq 2$ requires $\Omega(\log \kappa)$ queries, which is sharp in any constant dimension, and (2) sampling from Gaussians in dimension d (hence also from general logconcave and log-smooth distributions in dimension d) requires $\widetilde{\Omega}(\min (\sqrt{\kappa} \log d, d))$ queries, which is nearly sharp for the class of Gaussians. Here $\kappa$ denotes the condition number of the target distribution. Our proofs rely upon (1) a multiscale construction inspired by work on the Kakeya conjecture in geometric measure theory, and (2) a novel reduction that demonstrates that block Krylov algorithms are optimal for this problem, as well as connections to lower bound techniques based on Wishart matrices developed in the matrix-vector query literature.

Authors

• Sinho Chewi
• Jaume de Dios Pont
• Jerry Li 0001
• Chen Lu 0002
• Shyam Narayanan

Keywords

• Computer science
• Computational modeling
• Task analysis
• Lower Bound
• Target Distribution
• Advances In Recent Years
• Constant Dimension
• Deterministic
• Upper Bound
• Family Size
• Adaptive Algorithm
• Convex Function
• Lower Dimension
• Convex Set
• Information Bits
• Random Rotation
• Random Direction
• Rotation Invariance
• Chebyshev Polynomials
• Query Point
• Matrix-vector Product
• Total Variation Distance
• Oracle Model
• Theoretical Computer Science
• Mollifier
• Sampling
• log-concave distributions
• matrix-vector model
• sublinear algorithms