演讲人： Eric Price University of Texas, Austin
时间： 2024-06-11 14:00-2024-06-11 15:00
地点：FIT 1-222
内容：

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∣x) and a measurement y, and would like to sample from p(x∣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 talk I will 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. I will also show how existing heuristics exhibit noticeable bias on real data. 

This is based on joint work with Shivam Gupta, Ajil Jalal, Aditya Parulekar, and Zhiyang Xun.

个人简介:

Eric Price is an associate professor in the Department of Computer Science at the University of Texas at Austin. His undergraduate and graduate education was at MIT, where he was fortunate to have Piotr Indyk as his advisor. After graduating in 2013, he was a postdoc at the Simons Institute in Berkeley and at the IBM Almaden Research Center before arriving at UT in Fall 2014. (CV)