Parallel Backpropagation for Inverse of a Convolution with Application to Normalizing Flows

Sandeep Nagar, Girish VarmaAISTATS 2025

Presented at AISTATS 2025, this research introduces a significant optimization for a core component of generative modeling: the invertible convolution. By deriving a fast, parallel backpropagation algorithm for the inverse of a convolution, the authors enable a new architecture called Inverse-Flow that makes image generation significantly faster without sacrificing model expressivity.

The Bottleneck in Normalizing Flows

Normalizing Flows (NFs) are a class of generative models that transform a simple probability distribution (like a Gaussian) into a complex one (like an image) through a series of invertible, differentiable mappings.

A major bottleneck in NFs is the use of convolutions. While standard convolutions are fast, their inverses—required for either training or sampling—are notoriously slow. Most popular models like Glow settle for $1 \times 1$ convolutions because they are easy to invert, but they lack the spatial "receptive field" of larger $k \times k$ kernels. Previous attempts to use $k \times k$ invertible convolutions were either autoregressive (inherently sequential) or computationally prohibitive, requiring $O(n^3)$ time for backpropagation.

Parallel Backpropagation and Inverse-Flow

The authors tackle the challenge of making $k \times k$ invertible convolutions practical for deep learning by optimizing the gradient computation of the inverse operation. Their approach introduces two primary innovations:

1. The Parallel Backprop Algorithm

The authors derive recursive formulas for computing gradients with respect to the input and weights of an inverse convolution. They observe that while the operation has sequential dependencies, pixels along the diagonals of an image are independent. By processing these diagonals in sequence but parallelizing the computation within each diagonal on a GPU, they achieve a running time of $O(mk^2)$ for an $m \times m$ image, effectively reducing complexity from $O(n^3)$ to $O(\sqrt{n})$.

The mathematical setup of the convolution operation, showing the relationship between input x, kernel W, and output y.
Algorithm 1: The proposed parallel backpropagation algorithm for the inverse of a convolution.

2. Inverse-Flow Architecture

Traditionally, NFs use a convolution in the forward pass (image $\to$ latent) and an inverse convolution for sampling (latent $\to$ image). The authors propose the opposite: use the inverse convolution in the forward pass. Because the sampling pass is the inverse of the forward pass, sampling now uses a standard convolution, which is highly optimized on modern hardware. This "Inv-Flow" step combines the optimized inverse convolution with Actnorm, $1 \times 1$ convolutions, Spline Activations (SA), and Coupling layers.

Key Results and Insights

The models were evaluated on standard image benchmarks including MNIST ($28 \times 28$) and CIFAR-10 ($32 \times 32$).

  • Sampling Speedup: On the MNIST dataset, Inverse-Flow achieved a sampling time of 12.2 ms, compared to 33.5 ms for SNF and 47.3 ms for FIncFlow. This represents a ~3-4x speedup over state-of-the-art invertible convolution methods.
  • Efficiency: On MNIST, Inverse-Flow achieved better Negative Log-Likelihood (NLL) than FIncFlow while using nearly 10x fewer parameters (0.6M vs 5.16M).
  • Exact Gradients: Unlike some recent methods that use approximate inversion to save time, this method provides exact gradients, leading to more stable training and better density estimation.

Limitations and Future Work

While sampling is fast, the forward pass (and thus training) is still slower than a standard convolution. For a $256 \times 256$ image, the forward pass takes approximately 427 ms. Additionally, to ensure invertibility, the authors assume the bottom-right entry of the kernel is 1, which imposes a specific structure on the learned filters. Future work may explore ways to further tile or approximate these dependencies for ultra-high-resolution tasks where the sequential diagonal bottleneck remains significant.

Summary updated

BibTeX
@inproceedings{nagar2025parallel,
  author = {Sandeep Nagar and Girish Varma},
  title = {{Parallel Backpropagation for Inverse of a Convolution with Application to Normalizing Flows}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
}
Figure