Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networks

Lechao Xiao

Introduction

In the realm of high-dimensional machine learning, the "curse of dimensionality" poses a significant challenge: the volume of space increases so rapidly that the available data becomes sparse, requiring an exponential number of samples to learn complex functions. While modern deep learning architectures, particularly Convolutional Neural Networks (CNNs), appear to circumvent this curse, the underlying mathematical principles have remained partially obscured.

Previous theoretical work on infinite-width Multi-Layer Perceptrons (MLPs) identified a "frequency bias," where networks prioritize learning low-degree polynomials (low frequency) over high-degree ones. However, this perspective fails to account for the spatial structure inherent in data like images. This paper introduces the Eigenspace Restructuring principle, a unified framework that characterizes the inductive bias of neural architectures by balancing spatial distance and interaction frequency.

The Learning Index Framework

To analyze how different architectures learn, the authors utilize the infinite-width limit of neural networks, specifically the Neural Network Gaussian Process (NNGP) and the Neural Tangent Kernel (NTK). The central innovation is the Learning Index (LI), a metric that determines the order and efficiency with which a network learns specific functions.

The Learning Index is defined as the sum of two distinct components:

  1. Frequency Index (FI): This measures the complexity or degree of the interaction within the function.
  2. Spatial Index (SI): This measures the spatial distance between interacting terms. It is calculated based on the length of the Minimum Spanning Tree (MST) on the network's computational Directed Acyclic Graph (DAG).

By representing neural architectures as DAGs, the authors prove the Eigenspace Restructuring Theorem. This theorem demonstrates that while MLPs are primarily sensitive to frequency, CNNs restructure their internal eigenspaces to exploit spatial locality.

The Space-Frequency Trade-off

A fundamental insight of this work is the trade-off between spatial range and interaction frequency under a fixed data budget. Different architectures occupy different regions of this "Space-Frequency" plane.

The Space-Frequency trade-off across different architectures. MLPs are limited to long-range, low-frequency patterns, while deep CNNs cover a broader spectrum of median-range, median-frequency interactions.

As illustrated in the figure above:

  • MLPs (a): Primarily learn "Long-Range, Low-Frequency" interactions. They treat all input dimensions equally, making them inefficient for high-frequency spatial patterns.
  • Shallow CNNs (b): Are restricted to "Short-Range, High-Frequency" interactions due to their limited receptive fields.
  • Deep CNNs (c): Represent the "sweet spot," capable of modeling a rich spectrum of "Median-Range, Median-Frequency" interactions.
  • High-Resolution CNNs (d): Further refine these eigenspaces, allowing for even finer interpolation of complex features.

This restructuring allows deep CNNs to learn certain high-frequency functions with only a polynomial number of samples, effectively breaking the curse of dimensionality for spatially local data.

Empirical Validation

The theoretical predictions were tested using both synthetic polynomials and real-world datasets. Synthetic functions were designed on hyperspheres to isolate the effects of range and frequency.

MSE Residual vs Training Set Size. CNNs (blue and orange) demonstrate significantly better sample efficiency than MLPs (red) for functions requiring spatial and frequency coordination.

The empirical results confirm that the eigenvalues of neural kernels decay as $d^{-LI}$. Consequently, functions with a lower Learning Index are learned much faster. On ImageNet, the theory correctly predicted that the performance gap between models using Global Average Pooling (GAP) and those using Flattening layers is most pronounced when data is scarce. GAP improves data efficiency by a factor related to the pooling window size, though this advantage diminishes in the infinite-data limit.

Conclusion and Future Work

Eigenspace Restructuring provides a rigorous explanation for the superiority of CNNs in processing structured data. By incorporating spatial locality into the learning process, deep CNNs can navigate the high-dimensional landscape far more efficiently than MLPs.

While the current analysis focuses on the "lazy training" regime and assumes uniform input distributions, it lays the groundwork for understanding more complex architectures. Future research aims to extend this "Space and Frequency" framework to Recurrent Neural Networks (RNNs) and Transformers, potentially uncovering similar principles of restructuring in temporal and attention-based models.

Summary updated

BibTeX
@inproceedings{xiao2022eigenspace,
  author = {Lechao Xiao},
  title = {{Eigenspace Restructuring: a Principle of Space and Frequency in Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=NZQ8aTScT1-},
}
Figure