Efficient Computation of Deep Nonlinear Infinite-Width Neural Networks that Learn Features

Greg Yang, Michael Santacroce, Edward J HuICLR 2022 · OpenReview

Introduction

The $\pi$-limit is a new theoretical framework that allows researchers to compute the behavior of infinitely wide neural networks that actually learn features. While previous infinite-width theories like the Neural Tangent Kernel (NTK) were easy to compute but failed to learn features, and the "optimal" $\mu$-limit was capable of feature-learning but computationally impossible, the $\pi$-limit offers a powerful middle ground. It provides an infinite-width limit that is both mathematically tractable and capable of matching the performance of real-world finite networks.

The Computability Gap in Infinite-Width Networks

In deep learning theory, researchers often study "infinite-width" networks because their behavior becomes mathematically cleaner as they scale. The most famous version of this is the Neural Tangent Kernel (NTK). However, NTK has a major flaw: in the infinite limit, the network's "features" stay frozen at their random initialization. It behaves like a simple linear model, which fails to reflect how real neural networks dynamically adapt to data.

A more recent theory, the $\mu$-limit (maximal update limit), fixed this by allowing feature learning. Unfortunately, computing the $\mu$-limit for deep nonlinear networks is a computational nightmare. Calculating it involves solving nested Gaussian integrals that grow exponentially more complex with every training step. This paper addresses this "computability gap"—finding a way to get the theoretical benefits of infinite width without losing feature learning or making the math impossible to solve.

Methods: $\pi$-SGD and the Appending Trick

To solve this, the authors introduce $\pi$-SGD (Projected Gradient Descent) and its infinite-width counterpart, the $\pi$-limit.

  1. Projected Gradients: Instead of updating weights in every possible direction, $\pi$-SGD projects the gradients onto the subspace spanned by the network's initial random weights.
  2. Gradient Concatenation: In the infinite-width $\pi$-limit, the training process changes fundamentally. Instead of "adding" updates to weights, the network "appends" them. The authors show that an infinite-width MLP trained this way is mathematically equivalent to another MLP where the activation function is replaced by its "V-transform" (a dual version of the original activation).
In the infinite-width \pi-limit, training updates are appended to the representation space rather than added to the weights.
  1. Tensor Programs: The authors use the "Tensor Programs" framework—a mathematical toolkit for studying limits of neural networks—to prove that this projected training converges to a deterministic, computable limit as width goes to infinity.

This approach bypasses the "nested nonlinearity" problem of the $\mu$-limit, reducing the computational complexity from exponential to quadratic ($\Theta(T^2)$) relative to the number of training steps.

Key Insights and Results

The authors evaluated their $\pi$-limit against standard finite-width networks and NTK baselines on standard datasets like CIFAR-10, Omniglot, and ImageNet32.

  • Closing the Performance Gap: On CIFAR-10, the $\pi$-limit achieved 61.50% accuracy, outperforming both NTK (59.63%) and standard finite-width networks.
  • Omniglot Success: The $\pi$-limit crushed the NTK on Omniglot (91.46% vs 51.72%), proving that feature learning is non-negotiable for complex, few-shot datasets.
Comparison of feature learning representations: NTK fails to cluster, while the \pi-limit successfully clusters data similarly to a finite-width network.
  • Transfer Learning in Infinite Width: Because the $\pi$-limit learns features, it can do something NTK cannot: transfer learning. Pre-training the $\pi$-limit on ImageNet and transferring to CIFAR-10 raised accuracy to 64.39%, a feat previously impossible for infinite-width kernels.
  • The Power of Projection: The paper suggests that you don't need to optimize in the full, massive weight space to get good performance. Projecting onto a smaller, random subspace preserves most of the feature-learning power of the network.
  • Efficiency: While slower than simple kernel regression, the $\pi$-limit is the first "feature-learning" infinite-width limit that can actually be run on a single GPU for deep networks.

Limitations and Future Work

While a significant breakthrough, the framework has some current limitations:

  • Architecture Constraints: This paper focuses on Multi-Layer Perceptrons (MLPs). While the theory can be extended, the current implementation doesn't yet cover more modern architectures like Convolutional Neural Networks (CNNs) or Transformers.
  • Computational Scaling: Although $\Theta(T^2)$ is much better than exponential, it is still slower than finite-width training for very long training runs or massive datasets.
  • The "Optimal" Limit: The authors acknowledge the $\pi$-limit is a "simplification" of the $\mu$-limit. While it is computable, it might not capture every nuance of how standard SGD learns features.

Future work involves extending this "projection" trick to more complex architectures and finding ways to further reduce the $\Theta(T^2)$ cost to make infinite-width training even more practical.

Summary updated

Abstract

While a popular limit of infinite-width neural networks, the Neural Tangent Kernel (NTK) often exhibits performance gaps from finite-width neural networks on standard datasets, due to lack of feature learning. Although the feature learning *maximal update limit*, or *μ-limit* (Yang and Hu, 2020) of wide networks has closed the gap for 1-hidden-layer linear models, no one has been able to demonstrate this for deep nonlinear multi-layer perceptrons (MLP) because of μ-limit’s computational difficulty in this setting. Here, we solve this problem by proposing a novel feature learning limit, the *π-limit*, that bypasses the computational issues. The π-limit, in short, is the limit of a form of projected gradient descent, and the π-limit of an MLP is roughly another MLP where gradients are appended to weights during training. We prove its almost sure convergence with width using the Tensor Programs technique. We evaluate it on CIFAR10 and Omniglot against NTK as well as finite networks, finding the π-limit outperform finite-width models trained normally (without projection) in both settings, closing the performance gap between finite- and infinite-width neural networks previously left by NTK. Code for this work is available at github.com/santacml/pilim.
BibTeX
@inproceedings{yang2022efficient,
  author = {Greg Yang and Michael Santacroce and Edward J Hu},
  title = {{Efficient Computation of Deep Nonlinear Infinite-Width Neural Networks that Learn Features}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=tUMr0Iox8XW},
}
Figure