Zhi-Yang Xun

Query Lower Bounds for Diffusion Sampling

This work establishes the first score query lower bounds for diffusion sampling, and proves that for $d$-dimensional distributions, given access to score estimates with polynomial accuracy $\varepsilon=d^{-O(1)}$ (in any $L^p$ sense), any sampling algorithm requires $\widetilde{\Omega}(\sqrt{d})$ adaptive score queries...