Whitening Convergence Rate of Coupling-based Normalizing Flows

Felix Draxler, Christoph Schnoerr, Ullrich Koethe

Introduction

While coupling-based normalizing flows (such as RealNVP and Glow) are staples of generative modeling, our theoretical understanding of why they converge so well has remained limited. This paper proves that these flows achieve a "linear convergence rate" in whitening data. Essentially, it demonstrates that each additional layer predictably and efficiently strips away correlations, establishing a handy rule of thumb: each block reduces "non-standardness" by roughly 50%.

The Problem: Beyond Weak Convergence

Normalizing flows operate by transforming a complex data distribution into a simple one—usually a standard normal distribution—through a series of invertible mappings. While researchers have previously shown that these flows can represent any distribution (universal approximation), there has been no quantitative way to measure how fast they actually converge when trained using the standard maximum likelihood loss.

The authors identify a critical gap: existing proofs often rely on "weak convergence," which does not guarantee that the Kullback-Leibler (KL) divergence loss used in practice will actually reach zero. To address this, they provide the first quantitative convergence rate for coupling-based flows, focusing specifically on the "whitening" process—the phase where the model learns to remove the mean and diagonalize the covariance matrix of the data.

Methods: Decomposing the Loss

The researchers' key theoretical move is decomposing the total training loss ($\mathcal{L}$) into two distinct components:

  1. Non-Gaussianity ($\mathcal{G}$): How much the data deviates from a bell curve shape (negentropy).
  2. Non-Standardness ($\mathcal{S}$): How much the best Gaussian fit of the data deviates from the "standard" normal distribution (mean of 0, variance of 1).
Loss Decomposition and Convergence

The paper focuses heavily on $\mathcal{S}$. The authors model a standard "coupling block" as a sequence of a random rotation, a coupling layer, and an activation normalization (ActNorm) layer. By applying tools from information geometry and random matrix theory—specifically analyzing how eigenvalues of submatrices behave in a random basis—they derive explicit bounds on how much the non-standardness drops after a single block and across a deep network of $L$ blocks.

Key Insights and Results

The authors validated their theoretical bounds using the EMNIST dataset (to show how a single layer whitens real-world image covariance) and a synthetic toy dataset (to verify the linear convergence rate across diverse covariance matrices). Several key insights emerged:

  • Linear Convergence: The paper proves that the expected loss decreases exponentially relative to the number of blocks ($L$). In optimization terms, this is known as a "linear convergence rate." Specifically, after $L$ blocks, the expected non-standardness is bounded by $\gamma^L \mathcal{S}_{initial}$, where $\gamma$ is a rate constant less than 1.
  • The "50% Rule": One of the most practical takeaways is the heuristic that a single additional coupling block typically reduces the non-standardness of the data by about 50%. As the non-standardness approaches zero, the theoretical convergence rate $\gamma$ settles into a range between $1/2$ and $5/9$.
Relative Non-Standardness Reduction
  • Whitening is a Prerequisite: The authors argue that whitening is a necessary condition for the entire flow to converge. If the model cannot correctly capture the covariance (the "easy" part), it will fail to capture complex non-linear features.
  • Dimension Independence: Surprisingly, the convergence rate is largely independent of the dimensionality ($D$) of the data. Whether working with 10 dimensions or 1,000, the "per-block" efficiency of whitening remains remarkably stable.

Limitations and Future Work

The primary limitation of this work is its almost exclusive focus on the Gaussian/whitening aspect of the flow ($\mathcal{S}$). While whitening is necessary, it is not sufficient for a perfect generative model. The "non-Gaussianity" ($\mathcal{G}$) represents the complex, non-linear structural deviations of the data distribution (such as the specific shapes of digits in EMNIST).

The authors acknowledge that their current theory does not yet explain how the non-linear parts of the coupling layers reduce this non-Gaussianity. Future work aims to lift the restriction to affine-linear layers and explore how deep flows tackle the more complex, non-linear transformations required to fully map real-world data to a standard normal distribution.

Summary updated

Abstract

Coupling-based normalizing flows (e.g. RealNVP) are a popular family of normalizing flow architectures that work surprisingly well in practice. This calls for theoretical understanding. Existing work shows that such flows weakly converge to arbitrary data distributions. However, they make no statement about the stricter convergence criterion used in practice, the maximum likelihood loss. For the first time, we make a quantitative statement about this kind of convergence: We prove that all coupling-based normalizing flows perform whitening of the data distribution (i.e. diagonalize the covariance matrix) and derive corresponding convergence bounds that show a linear convergence rate in the depth of the flow. Numerical experiments demonstrate the implications of our theory and point at open questions.
BibTeX
@inproceedings{draxler2022whitening,
  author = {Felix Draxler and Christoph Schnoerr and Ullrich Koethe},
  title = {{Whitening Convergence Rate of Coupling-based Normalizing Flows}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=TN4UpY_Qzo},
}
Figure