Abstract
Log-concave sampling has witnessed remarkable algorithmic advances in recentyears, but the corresponding problem of proving lower bounds for this task hasremained elusive, with lower bounds previously known only in dimension one. Inthis work, we establish the following query lower bounds: (1) sampling fromstrongly log-concave and log-smooth distributions in dimension $d\ge 2$requires $\Omega(\log \kappa)$ queries, which is sharp in any constantdimension, and (2) sampling from Gaussians in dimension $d$ (hence also fromgeneral log-concave and log-smooth distributions in dimension $d$) requires$\widetilde \Omega(\min(\sqrt\kappa \log d, d))$ queries, which is nearly sharpfor the class of Gaussians. Here $\kappa$ denotes the condition number of thetarget distribution. Our proofs rely upon (1) a multiscale constructioninspired by work on the Kakeya conjecture in harmonic analysis, and (2) a novelreduction that demonstrates that block Krylov algorithms are optimal for thisproblem, as well as connections to lower bound techniques based on Wishartmatrices developed in the matrix-vector query literature.