Diffusion Posterior Sampling is Computationally Intractable
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909893565349888 |
|---|---|
| author | Gupta, Shivam Jalal, Ajil Parulekar, Aditya Price, Eric Xun, Zhiyang |
| author_facet | Gupta, Shivam Jalal, Ajil Parulekar, Aditya Price, Eric Xun, Zhiyang |
| contents | 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 computationally intractable: under the most basic assumption in cryptography -- that one-way functions exist -- there are instances for which every algorithm takes superpolynomial time, even though 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12727 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Diffusion Posterior Sampling is Computationally Intractable Gupta, Shivam Jalal, Ajil Parulekar, Aditya Price, Eric Xun, Zhiyang Machine Learning Artificial Intelligence Statistics Theory 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 computationally intractable: under the most basic assumption in cryptography -- that one-way functions exist -- there are instances for which every algorithm takes superpolynomial time, even though 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. |
| title | Diffusion Posterior Sampling is Computationally Intractable |
| topic | Machine Learning Artificial Intelligence Statistics Theory |
| url | https://arxiv.org/abs/2402.12727 |