Implicit Bias of Linear Equivariant Networks

Hannah Lawrence, Bobak Toussi Kiani, Kristian G. Georgiev, Andrew K. Dienes

In the world of deep learning, we often build models that are "overparameterized"—they have far more parameters than data points. Theoretically, these models should be able to memorize noise and fail to generalize, yet they work remarkably well. Why? The answer often lies in implicit bias: the tendency of training algorithms like gradient descent to favor "simple" solutions over complex ones, even when both fit the data perfectly.

A new paper from researchers at MIT, titled "Implicit Bias of Linear Equivariant Networks," extends our understanding of this phenomenon to one of the most popular architectural families in modern AI: Group Equivariant Convolutional Neural Networks (G-CNNs).

TL;DR

This paper proves that $L$-layer linear G-CNNs trained with gradient descent are implicitly biased toward solutions with low-rank Fourier matrix coefficients. Specifically, they minimize the $2/L$-Schatten norm in the Fourier regime, meaning that as these networks get deeper, they become increasingly "sparse" in how they represent symmetries, favoring simpler, lower-complexity functions.

What Problem Does This Paper Address?

Standard Convolutional Neural Networks (CNNs) are great at handling translations, but many real-world problems involve other symmetries like rotations (in medical imaging) or permutations (in particle physics). G-CNNs are designed to be "equivariant" to these groups, meaning if you rotate the input, the output rotates predictably.

While we understand the explicit bias of these architectures (the symmetry is baked into the math), we haven't known much about their implicit bias. Previous research showed that standard linear CNNs (which handle cyclic translations) are biased toward sparsity in the Fourier domain. However, those proofs didn't work for more complex, non-commutative groups (where the order of operations matters, like rotating then flipping vs. flipping then rotating). This paper fills that gap, providing a unified theory for all finite groups and even some infinite ones.

Methods

The authors analyze $L$-layer linear G-CNNs—networks where each layer performs a group convolution but lacks non-linear activations like ReLU. While simplified, these models allow for rigorous mathematical analysis that often mirrors what we see in complex, non-linear systems.

The key technical "heavy lifting" involves:

  1. Non-commutative Fourier Analysis: Translating group convolutions (which are complex matrix operations in real space) into the Fourier domain.
Fourier Transform of Group Convolutions
  1. KKT Conditions: Using optimization theory to characterize the "stationary points" where gradient descent ends up.
  2. Schatten Norms: Defining complexity using the $p$-Schatten norm (the $p$-norm of a matrix's singular values). They show the network acts as if it's minimizing this norm for $p = 2/L$.

Datasets

The researchers validated their mathematical theorems using several experimental setups:

  • Synthetic Gaussian Data: Random vectors used to test the basic convergence properties across different groups like $D_8$ (symmetries of a square) and $Q_8$ (quaternions).
  • MNIST Digits: Specifically binary classification tasks (e.g., distinguishing 1s from 5s).
  • Spherical MNIST: A version of MNIST projected onto a sphere to test G-CNNs designed for the infinite rotation group $SO(3)$.

Key Insights and Ideas

  • Depth Drives Sparsity: The "$2/L$" in the Schatten norm is crucial. As the number of layers ($L$) increases, the exponent $2/L$ gets smaller. In optimization, smaller exponents lead to "spikier," sparser solutions. This suggests that deeper equivariant networks are naturally biased toward even simpler representations of symmetry.
  • The Fourier-Real Trade-off: Using the Meshulam uncertainty principle, the authors show a fascinating "aha" moment: if a function is sparse in the Fourier domain (low rank), it must be "dense" in real space. This means the implicit bias forces the network to spread its influence across the entire group rather than focusing on a few specific transformations.
  • Beyond Commutativity: Unlike standard CNNs where Fourier transforms are scalar multiplications, for non-abelian groups, they are matrix multiplications. The authors proved that the implicit bias still holds in this much more difficult mathematical landscape.

Key Results

  • Theoretical Proof: They formally proved that for any finite group, gradient descent on an $L$-layer linear G-CNN converges to a solution that minimizes the $2/L$-Schatten norm of its Fourier coefficients.
  • Experimental Validation: In tests on the $D_8$ group, the G-CNN consistently achieved a lower Fourier Schatten norm than standard CNNs or fully connected networks, confirming the theory.
Fourier Space Norm Comparison
  • Non-linear Surprise: Even though the theory is for linear networks, experiments with ReLU activations showed the same patterns. The non-linear G-CNNs still "locally" minimized the same Fourier-space norms, suggesting the theory has broad practical relevance.

Limitations and Future Work

While a major step forward, the paper notes a few boundaries:

  • Linearity: The core proof is for linear networks. While empirical results on ReLU networks are promising, a formal proof for the non-linear case remains an open challenge.
  • Full-width Kernels: The theory assumes "full-width" kernels (the filter covers the whole group). In practice, many CNNs use small, local filters (e.g., 3x3). Extending this to "bounded-width" kernels is a known difficult problem in the field.
  • Loss Functions: The study focuses on exponential loss for binary classification. How this bias changes with cross-entropy or mean-squared error in multi-class settings is still to be determined.

By showing that G-CNNs are "minimalists" in the Fourier world, this research provides a vital piece of the puzzle in understanding why equivariant models are so effective at learning the underlying laws of symmetrical data.

Summary updated

Abstract

Group equivariant convolutional neural networks (G-CNNs) are generalizations of convolutional neural networks (CNNs) which excel in a wide range of technical applications by explicitly encoding sym...
BibTeX
@inproceedings{lawrence2022implicit,
  author = {Hannah Lawrence and Bobak Toussi Kiani and Kristian G. Georgiev and Andrew K. Dienes},
  title = {{Implicit Bias of Linear Equivariant Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=PabeDOzFUU},
}
Figure