Diffusion Posterior Sampling is Computationally Intractable
<|reference_start|>Diffusion Posterior Sampling is Computationally Intractable: Diffusion models are a remarkably effective way of learning and sampling from a distribution $p(x)$. In posterior sampling, one is also given a measurement model $p(y \mid x)$ and a measurement $y$, and would like to sample from $p(x \mid y)$. Posterior sampling is useful for tasks such as inpainting, super-resolution, and MRI reconstruction, so a number of recent works have given algorithms to heuristically approximate it; but none are known to converge to the correct distribution in polynomial time.   In this paper we show that posterior sampling is \emph{computationally intractable}: under the most basic assumption in cryptography -- that one-way functions exist -- there are instances for which \emph{every} algorithm takes superpolynomial time, even though \emph{unconditional} sampling is provably fast. We also show that the exponential-time rejection sampling algorithm is essentially optimal under the stronger plausible assumption that there are one-way functions that take exponential time to invert.<|reference_end|>
@article{gupta2024diffusion,
    title={Diffusion Posterior Sampling is Computationally Intractable},
    author={Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, Zhiyang Xun},
    journal={arXiv preprint arXiv:2402.12727},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.12727},
    primaryClass={cs.LG cs.AI math.ST stat.ML stat.TH}
}