Conditional Sampling from Invertible Generative Models with Applications to Inverse Problems.

Erik M. Lindgren, Jay Whang, Alexandros G. Dimakis

TL;DR

This paper demonstrates that exactly sampling from a pre-trained normalizing flow conditioned on partial observations is computationally hard (NP-hard). To overcome this, the authors propose a novel variational inference framework that composes a trainable "pre-generator" flow with the fixed, pre-trained prior. This approach enables stable, non-adversarial approximate conditional inference, delivering high-quality image reconstructions and reliable uncertainty quantification.

What Problem Does This Paper Address?

Inverse problems—such as image inpainting, super-resolution, and compressed sensing—seek to recover an underlying signal $x$ from noisy, incomplete measurements $y^* = A(x) + \text{noise}$. Deep generative models like normalizing flows are highly attractive as priors for these tasks because they offer exact likelihood evaluation and efficient sampling.

However, performing accurate probabilistic inference (i.e., computing the conditional distribution $p(x|y^*)$) using a pre-trained flow model remains a major challenge. The authors formalize this difficulty by proving a core hardness theorem: exact conditional sampling from a flow model with additive coupling layers is fundamentally intractable (equivalent to solving NP-complete problems like 3-SAT). Consequently, researchers must rely on approximate conditioning methods.

Methods

Instead of re-training a massive generative model from scratch or fine-tuning its weights, the authors propose keeping the pre-trained base model $f: z \mapsto x$ fixed. They introduce a separate, trainable flow model called a pre-generator $\hat{f}: \epsilon \mapsto z$, which maps simple Gaussian noise $\epsilon$ into the latent space of the base model.

The full conditional sampler is formed by the composition of these two models: $$x = f(\hat{f}(\epsilon))$$

To train the pre-generator, the authors use Stochastic Variational Inference (SVI). Because deterministic forward operators $A(x)$ can cause the variational loss to explode to infinity, they introduce a Gaussian smoothing mechanism. This relaxes the hard measurement constraint into a soft constraint, effectively acting as observation noise and ensuring a stable training procedure that avoids the pitfalls of adversarial training (GANs). Furthermore, they show that the pre-generator can be amortized over observations (Amortized Variational Inference, or AVI), allowing for zero-shot conditional inference at test time.

Datasets

The method was evaluated using pre-trained RealNVP architectures on three standard image datasets:

  • MNIST
  • CIFAR-10 (processed with 5-bit pixel quantization)
  • CelebA-HQ (resized to $64 \times 64$ resolution with 5-bit pixel quantization)

Key Insights and Ideas

  • The Hardness Justification: The mathematical proof that exact conditioning is NP-hard provides a rigorous theoretical justification for why approximate conditioning and observation smoothing are mandatory when working with normalizing flows.
  • Composition Over Re-training: Learning a flow into the latent space of an existing flow preserves the architectural benefits (invertibility, exact likelihoods) of the base model while repurposing it for entirely new downstream tasks.
  • Distributional Advantage: Most existing methods focus on point estimates (like MAP evaluation). By recovering the entire posterior distribution, this method can compute the conditional mean—the mathematically optimal Minimum Mean Squared Error (MMSE) estimator under $\ell_2$ loss—which significantly improves reconstruction accuracy.
  • True Uncertainty Quantification: Because the model outputs a distribution, it can map out pixel-wise variance and capture semantic ambiguities, such as a pixel that could multi-modally belong to either a person's neck or a dark background.
Figure 1: Uncertainty quantification highlighted at differ- ent pixel locations, obtained from our learned approximate posterior. The top pixel is observed, and thus is sharply concentrated on a single value (the small variance is due to our use of smoothing). The bimodal plot distribution in the bottom left captures the semantic ambiguity of the bottom pixel that can be part of either the neck or the background.

Key Results

  • Superior Sample Quality: In image inpainting tasks, the SVI approach outperformed strong baselines like Langevin Monte Carlo (LMC) and Ambient VI, achieving lower Mean Squared Error (MSE) and better Frechet Inception Distance (FID) scores across all datasets.
  • Compressed Sensing Gains: Utilizing the empirical mean (MMSE estimator) from 32 conditional samples yielded a substantial boost in Peak Signal-to-Noise Ratio (PSNR) compared to traditional point-estimate methods.
  • Massive Speedups via Amortization: While optimization-based inference (SVI) took tens of seconds per image, the amortized version (AVI) generated high-quality conditional samples in a fraction of a second (e.g., 0.046 seconds on CelebA-HQ), making it orders of magnitude faster than MCMC baselines.

Limitations and Future Work

  • Amortization Quality Trade-off: Although the amortized pre-generator (AVI) drastically accelerates inference speed, it suffers from a noticeable drop in sample quality and higher FID scores compared to its non-amortized SVI counterpart.
  • Hyperparameter Sensitivity: The smoothing parameter $\sigma$ requires careful tuning. Setting it too large causes the model to ignore the actual observations, while setting it too small forces the model to try and fit a degenerate posterior, resulting in unnatural artifacts.
  • Smoothing Metrics: The authors note that preliminary attempts to use advanced perceptual metrics (like LPIPS) for the observation smoothing loss showed no benefit over standard $\ell_2$ distance, leaving the exploration of alternative smoothing techniques to future work.

Summary updated

Abstract

Given an inverse problem with a normalizing flow prior, we wish to estimate the distribution of the underlying signal conditioned on the observations. We approach this problem as a task of conditional inference on the pre-trained unconditional flow model. We first establish that this is computationally hard for a large class of flow models. Motivated by this, we propose a framework for approximate inference that estimates the target conditional as a composition of two flow models. This formulation leads to a stable variational inference training procedure that avoids adversarial training. Our method is evaluated on a variety of inverse problems and is shown to produce high-quality samples with uncertainty quantification. We further demonstrate that our approach can be amortized for zero-shot inference.
BibTeX
@inproceedings{lindgren2021conditional,
  author = {Erik M. Lindgren and Jay Whang and Alexandros G. Dimakis},
  title = {{Conditional Sampling from Invertible Generative Models with Applications to Inverse Problems.}},
  booktitle = {TPM @ UAI},
  year = {2021},
  url = {https://openreview.net/forum?id=vZGPHN0Q_f},
}
Figure