Run-Sort-ReRun: Escaping Batch Size Limitations in Sliced Wasserstein Generative Models

José Lezama, Wei Chen, Qiang QiuICML 2021 · OpenReview

The Batch Size Bottleneck

In generative modeling, batch size is a critical factor. To accurately reproduce a target distribution, a model needs to "see" enough samples simultaneously to understand its subtleties and diverse modes. However, standard deep learning frameworks are fundamentally limited by GPU memory: every sample in a batch requires storing intermediate activations and gradients for backpropagation.

When hardware constraints force batch sizes to be too small, objective functions provide a noisy, incomplete picture of the overall data distribution. This often leads to "mode collapse," a failure state where the generator only learns to produce a few types of outputs (e.g., generating only one specific digit in an MNIST-like dataset) and ignores the rest of the distribution. While Sliced Wasserstein (SW) distances—which compare distributions by looking at 1D projections—are popular for being differentiable and stable, they still suffer from these hardware-imposed limits.

Small batch sizes lead to mode collapse, while Run-Sort-ReRun captures all modes by effectively using a large batch size.

The Solution: Run-Sort-ReRun (RSR)

To break free from GPU memory constraints, the authors introduce Run-Sort-ReRun (RSR), a three-step procedure that decouples optimal transport calculations from gradient backpropagation, allowing for "virtually" unlimited batch sizes (e.g., tens of thousands of samples).

  1. Run: The model performs a forward pass on a massive batch of latent vectors ($z$) in small, memory-efficient chunks. It stores the latent vectors and their projected values. Crucially, automatic differentiation is turned off during this step, meaning no memory-heavy gradients are stored.
  2. Sort: Once the large batch is collected, the algorithm sorts the projected samples. In 1D, sorting acts as a "magic trick" that solves the optimal transport problem, perfectly matching each generated sample to a target real sample from the true distribution.
  3. ReRun: The model performs a second forward pass on the exact same latent vectors, again in small chunks. This time, automatic differentiation is turned on. Each generated sample is compared to its pre-calculated "target" from the Sort step, and gradients are backpropagated normally.
Schematic of the RSR algorithm showing how correspondences are established globally before backpropagating in small batches.

Additionally, rather than using random Gaussian noise for projection directions, the authors sample directions based on the vectors connecting pairs of real and generated samples. This more effectively identifies and penalizes gaps between the two distributions.

Key Insights

  • Memory vs. Computation Trade-off: The core innovation is realizing that re-running a forward pass is computationally cheaper and far more flexible than attempting to fit a massive gradient graph into limited VRAM.
  • Direct FID Optimization: Fréchet Inception Distance (FID) is the gold standard for evaluating GANs, but it is typically too memory-intensive to optimize directly. RSR makes it possible to match the distribution of Inception features across thousands of samples, essentially training the model to optimize the metric directly, which translates to improved image quality.
  • Logarithmic Complexity: While RSR adds a second forward pass, the time complexity only increases logarithmically with batch size ($O(b \log b)$ due to sorting), making it highly scalable.

Results and Performance

The RSR method significantly improved the performance of baseline models (like E2GAN and StyleGAN2) across standard datasets:

  • CIFAR-10: Fine-tuning E2GAN with RSR improved the FID from 11.26 to 4.9, outperforming StyleGAN-v2 + ADA.
  • STL-10: The FID dropped dramatically from 25.35 to 8.6.
  • LSUN Church: StyleGAN2 fine-tuned with RSR achieved an FID of 3.14, surpassing the original model's 3.86.

An ablation study further confirmed a clear correlation between batch size and quality: on CIFAR-10, increasing the effective batch size from 256 to 8,192 dropped the FID from 10.02 to 6.99.

Limitations and Future Work

While highly effective, RSR does have limitations. The extra forward pass required in the "Run" step increases the total training time per iteration. Furthermore, while optimizing Inception features works well, matching distributions in a single feature space doesn't guarantee perfect image quality across all metrics, suggesting that exploring concatenated feature layers could yield even better results. Finally, for truly massive batches (in the millions), the CPU/GPU sorting step itself could eventually become a computational bottleneck.

Summary updated

Abstract

When training an implicit generative model, ideally one would like the generator to reproduce all the different modes and subtleties of the target distribution. Naturally, when comparing two empiri...
BibTeX
@inproceedings{lezama2021run,
  author = {José Lezama and Wei Chen and Qiang Qiu},
  title = {{Run-Sort-ReRun: Escaping Batch Size Limitations in Sliced Wasserstein Generative Models}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=36V1PbMOaiC},
}
Figure