Efficient Approximate Posterior Sampling with Annealed Langevin Monte Carlo
This addresses a fundamental challenge in generative modeling for tasks like image super-resolution and reconstruction, offering theoretical guarantees for efficient sampling.
The paper tackles the problem of posterior sampling in score-based generative models, showing that under minimal assumptions, one can tractably sample from a distribution close to the posterior in KL and Fisher divergences, providing the first formal results for approximate posterior sampling in polynomial time.
We study the problem of posterior sampling in the context of score based generative models. We have a trained score network for a prior $p(x)$, a measurement model $p(y|x)$, and are tasked with sampling from the posterior $p(x|y)$. Prior work has shown this to be intractable in KL (in the worst case) under well-accepted computational hardness assumptions. Despite this, popular algorithms for tasks such as image super-resolution, stylization, and reconstruction enjoy empirical success. Rather than establishing distributional assumptions or restricted settings under which exact posterior sampling is tractable, we view this as a more general "tilting" problem of biasing a distribution towards a measurement. Under minimal assumptions, we show that one can tractably sample from a distribution that is simultaneously close to the posterior of a noised prior in KL divergence and the true posterior in Fisher divergence. Intuitively, this combination ensures that the resulting sample is consistent with both the measurement and the prior. To the best of our knowledge these are the first formal results for (approximate) posterior sampling in polynomial time.