Implicit Bias of Linear Equivariant Networks

Hannah Lawrence, Kristian Georgiev, Andrew Dienes, Bobak Toussi Kiani

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 symmetries, such as rotations and permutations, in their architectures. Although the success of G-CNNs is driven by their explicit symmetry bias, a recent line of work has proposed that the implicit bias of training algorithms on particular architectures is key to understanding generalization for overparameterized neural nets. In this context, we show that $L$-layer full-width linear G-CNNs trained via gradient descent for binary classification converge to solutions with low-rank Fourier matrix coefficients, regularized by the $2/L$-Schatten matrix norm. Our work strictly generalizes previous analysis on the implicit bias of linear CNNs to linear G-CNNs over all finite groups, including the challenging setting of non-commutative groups (such as permutations), as well as band-limited G-CNNs over infinite groups. We validate our theorems via experiments on a variety of groups, and empirically explore more realistic nonlinear networks, which locally capture similar regularization patterns. Finally, we provide intuitive interpretations of our Fourier space implicit regularization results in real space via uncertainty principles.

Introduction

In deep learning, Group Equivariant Convolutional Neural Networks (G-CNNs) are the gold standard for tasks involving symmetry. Whether it's rotating an image or permuting atoms in a molecule, G-CNNs explicitly bake these rules into their architecture. However, modern neural networks are heavily overparameterized, meaning they could theoretically memorize training data in infinitely many ways. The fact that they generalize well suggests the presence of an implicit bias: a tendency of optimization algorithms like gradient descent to favor "simple" solutions.

While previous research has characterized this bias for standard fully-connected and convolutional networks, G-CNNs—especially those involving non-commutative groups like 3D rotations—remained theoretically elusive. This paper uncovers how gradient descent pushes G-CNNs toward sparsity in the Fourier domain.

The Fourier Perspective

To analyze complex symmetries, the study shifts the focus from "real space" (raw input data) to the Fourier domain. For standard CNNs, the Fourier transform turns convolutions into element-wise multiplications. However, for G-CNNs over non-commutative groups, convolutions transform into matrix multiplications over irreducible representations (irreps).

The Fourier transform $\mathcal{F}_M$ maps group convolutions to block-diagonal matrix multiplications.

By analyzing the Karush-Kuhn-Tucker (KKT) optimality conditions of the training objective, the authors prove that $L$-layer linear G-CNNs converge to solutions that minimize the $2/L$-Schatten norm of these Fourier matrix coefficients. This result generalizes prior findings from simple cyclic groups to all finite groups and even band-limited infinite groups like $SO(3)$.

Depth and Sparsity

The "$2/L$" exponent in the Schatten norm is a critical finding. As the network depth ($L$) increases, the exponent decreases, creating stronger pressure toward sparsity and low-rank solutions. In non-commutative groups, this "sparsity" manifests as the Fourier coefficient matrices becoming low-rank. Effectively, the network learns to ignore noisy, high-frequency components of the group structure.

This Fourier-domain sparsity has a real-space counterpart governed by the uncertainty principle: being sparse in Fourier space necessitates being "dense" or globally integrated in real space. This forces the network to learn features that are integrated across the entire symmetry group rather than focusing on isolated local pixels.

Empirical Confirmation

The researchers validated these theoretical predictions using synthetic data and variants of MNIST (including Spherical MNIST). Across various groups, such as the dihedral group $D_8$, G-CNNs consistently achieved significantly lower Fourier Schatten norms than standard CNNs or fully-connected networks, aligning with the theoretical "optimal" bounds.

Fourier and real space norms of network linearizations over training epochs.

Interestingly, the authors found that even nonlinear networks using ReLU activations exhibit this same bias locally. While the formal proofs apply to linear architectures, the empirical evidence suggests that the spirit of this Fourier-domain regularization holds for more complex, realistic models.

Conclusion

By uncovering a hidden preference for Fourier-domain simplicity, this research explains why G-CNNs are not just "correct" by architectural design, but also "efficient" by training. The implicit bias of gradient descent naturally complements the explicit symmetry of the G-CNN, guiding the model toward generalizable, low-rank representations.

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 symmetries, such as rotations and permutations, in their architectures. Although the success of G-CNNs is driven by their \emph{explicit} symmetry bias, a recent line of work has proposed that the \emph{implicit} bias of training algorithms on particular architectures is key to understanding generalization for overparameterized neural nets. In this context, we show that $L$-layer full-width linear G-CNNs trained via gradient descent for binary classification converge to solutions with low-rank Fourier matrix coefficients, regularized by the $2/L$-Schatten matrix norm. Our work strictly generalizes previous analysis on the implicit bias of linear CNNs to linear G-CNNs over all finite groups, including the challenging setting of non-commutative groups (such as permutations), as well as band-limited G-CNNs over infinite groups. We validate our theorems via experiments on a variety of groups, and empirically explore more realistic nonlinear networks, which locally capture similar regularization patterns. Finally, we provide intuitive interpretations of our Fourier space implicit regularization results in real space via uncertainty principles.
BibTeX
@inproceedings{lawrence2022implicit,
  author = {Hannah Lawrence and Kristian Georgiev and Andrew Dienes and Bobak Toussi Kiani},
  title = {{Implicit Bias of Linear Equivariant Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=PabeDOzFUU},
}
Figure