Learning Invariance with Compact Transforms

Anna T. Thomas, Albert Gu, Tri Dao, Atri Rudra, Christopher RéWorkshops @ ICLR 2018 · OpenReview

Overview

State-of-the-art deep neural networks often require billions of parameters, making them difficult to deploy on resource-constrained devices. To solve this, researchers frequently use "structured matrices" (like Toeplitz or circulant matrices) to compress layers. These structures work by encoding an inductive bias—specifically, shift-invariance, similar to how convolutions operate.

However, most existing methods rely on fixed structures. If your data has a specific pattern or invariance that doesn't perfectly match a standard Toeplitz matrix, performance degrades. This paper introduces a method to automatically learn the "structure" of neural network layers using the low displacement-rank (LDR) framework. By learning the displacement operators from data rather than using fixed ones, the authors enable models to discover domain-specific invariances—like the 2D grid structure of an image—while maintaining extreme parameter efficiency.

The Low Displacement-Rank (LDR) Framework

The authors utilize the LDR framework to decouple the "rules" of the data from the fine-tuned details. In this setup, a large, dense weight matrix $A$ is represented by two sparse "displacement operators" ($M$ and $N$) and a low-rank residual matrix ($R$). The relationship is defined by the equation:

$$MA - AN = R$$

The key innovations in this paper include:

  • Learning the Operators: Instead of fixing $M$ and $N$ as simple shift matrices, the authors parameterize them and learn their values via backpropagation.
  • Scaled-cycle Operators: A generalization of circulant matrices where the "wrap-around" and scaling values are learned.
  • Tridiagonal-plus-corner Operators: A broad class encompassing almost all classic structured matrices (Toeplitz, Vandermonde, Cauchy) and standard low-rank matrices.
  • Efficient Reconstruction: Specialized algorithms ensure that even though the operators are learned, the weight matrix can still be multiplied and stored efficiently in near-linear time and space.

Discovering Data Geometry

A powerful aspect of the LDR framework is that the operators ($M, N$) capture the high-level invariances of the data, while the residual ($R$) handles the fine-tuned details.

In a striking result, the authors demonstrated that when training on flattened MNIST images (where 2D structure is technically lost to the network), the learned operators "rediscovered" the 28x28 grid.

Comparison of fixed Toeplitz-like structure versus learned scaled-cycle matrix, alongside the DFT of the learned subdiagonal showing a clear peak at frequency 28 (the image width).

As shown above, the Discrete Fourier Transform (DFT) of the learned operator exhibits a clear peak at 28, corresponding exactly to the image width. This proves that the model can automatically learn the optimal basis for a specific dataset, whereas fixed operators often provide a poor basis.

Key Results and Performance

The authors evaluated their approach on several datasets, including MNIST-noise (MNIST with correlated pixel noise), CIFAR-10, and a synthetic Rectangle dataset.

  • Superior Accuracy with Fewer Parameters: On the MNIST-noise task, the "Tridiagonal-plus-corner" model achieved 78.4% accuracy with only ~15k parameters.
Test accuracy versus total number of parameters on the MNIST-noise dataset. The learned operators significantly outperform fixed structures and unconstrained models.
  • Massive Compression: As seen in the performance chart, the learned structured layers outperformed fixed Toeplitz-like models (71.2%) and standard unconstrained models (67.6%) of similar size. In fact, they achieved better results than a massive unconstrained model with 623,290 parameters while using roughly 40x fewer parameters.
  • General Gains: On standard benchmarks, the broad classes of learned structured matrices improved final accuracy by 5–7% compared to conventional parameter-constraining methods.

Limitations and Future Work

While the theoretical efficiency is sound, LDR layers require specialized kernels to match the raw speed of highly optimized standard GEMM (General Matrix Multiply) operations in libraries like cuBLAS. Additionally, learning the operators adds another layer of optimization, which may require more careful tuning of learning rates and initialization compared to standard layers.

Future work will need to focus on extending these structured transforms from single-hidden-layer networks to very deep architectures, such as ResNets, to fully realize their potential in modern deep learning pipelines.

Summary updated

Abstract

The problem of building machine learning models that admit efficient representations and also capture an appropriate inductive bias for the domain has recently attracted significant interest. Existing work for compressing deep learning pipelines has explored classes of structured matrices that exhibit forms of shift-invariance akin to convolutions. We leverage the displacement rank framework to automatically learn the structured class, allowing for adaptation to the invariances required for a given dataset while preserving asymptotically efficient multiplication and storage. In a setting with a small fixed parameter budget, our broad classes of structured matrices improve final accuracy by 5-7% on standard image classification datasets compared to conventional parameter constraining methods.
BibTeX
@inproceedings{thomas2018learning,
  author = {Anna T. Thomas and Albert Gu and Tri Dao and Atri Rudra and Christopher Ré},
  title = {{Learning Invariance with Compact Transforms}},
  booktitle = {Workshops @ ICLR},
  year = {2018},
  url = {https://openreview.net/forum?id=e9D4WBRhKg},
}
Figure