Free Probability, Newton lilypads and Jacobians of neural networks

Reda Chhaibi, Tariq Daouda, Ezechiel Kahn

TL;DR

This paper introduces "Newton lilypads," a novel and efficient computational method for analyzing the spectral properties of neural network Jacobians before training. These spectral properties, rooted in Free Probability Theory, are shown to be highly predictive of final test accuracy, offering a way to estimate network performance without costly training.

What Problem Does This Paper Address?

Training deep neural networks is computationally expensive and time-consuming. Estimating an architecture's performance before training would be a significant breakthrough, saving resources and accelerating the design process. A key challenge in understanding neural network behavior is the instability that can arise during gradient descent, often linked to the spectral properties (eigenvalues and singular values) of the network's Jacobian matrix. Analyzing these properties for large, complex networks is analytically difficult.

Methods

The authors leverage Free Probability Theory (FPT) to model the Jacobian of deep feed-forward neural networks. FPT provides tools to analyze the spectral distributions of large random matrices. They extend existing FPT methods to handle rectangular matrices, which is more realistic for neural networks with varying layer widths.

The core innovation is a new computational method called "Newton lilypads" for calculating the spectral density of the Jacobian. This method uses an adaptive Newton-Raphson scheme combined with a doubling strategy to chain together different "basins of attraction." This allows for a globally convergent and robust inversion of the S-transform, a key tool in FPT, which was previously considered practically impossible. This method is significantly faster than prior approaches.

Datasets

The empirical evaluation used standard datasets:

  • MNIST
  • FashionMNIST
  • CIFAR10

The authors trained randomly generated Multi-Layer Perceptrons (MLPs) on these datasets to evaluate the correlation between FPT metrics and test accuracy. No new datasets were introduced.

Key Insights and Ideas

  • Jacobian Hyperbolicity is Desirable: Contrary to the "edge of chaos" hypothesis, the paper suggests that a desirable feature for neural network Jacobians at initialization is hyperbolicity – having both contracting and expanding directions. This allows for stable learning without gradient vanishing or explosion.
  • FPT as a Performance Predictor: The spectral density of the Jacobian, computed using FPT, is a strong indicator of a network's final test accuracy. This metric can be computed before training.
  • Rectangular Matrices Matter: Extending FPT to handle rectangular matrices (varying layer widths) is crucial for accurately modeling modern neural network architectures.
  • Newton Lilypads: A Practical Breakthrough: The development of a reliable and fast numerical method ("Newton lilypads") for computing spectral densities overcomes a significant practical hurdle in applying FPT to neural networks.

Key Results

  • The "Newton lilypads" method is orders of magnitude faster than previous FPT-based methods for computing spectral densities (see Figure 1.1).
  • The 90th percentile of the computed spectral density (vj) shows a high correlation with final test accuracy across MNIST, FashionMNIST, and CIFAR10 datasets, reaching up to 85% correlation (Table 1.1).
  • This correlation is particularly strong for higher quantiles of the spectral density, suggesting that the spread and magnitude of singular values are key.
  • The method is shown to be robust and converges reliably, even for complex architectures.

Limitations and Future Work

  • Skip Connections: The current FPT model, based on the chain rule, does not directly apply to networks with skip connections, as the Jacobian cannot be approximated by a simple product of free matrices. This is identified as a challenging area for future work.
  • "Second-Order Corrections": While FPT metrics are highly correlated with accuracy, the authors suggest they might be considered "second-order corrections" in the sense that their method helps avoid catastrophic gradient issues rather than fundamentally changing the learning process. However, they also note the surprising strength of this correlation.
  • Architecture Sampling: The sampling procedure focused on balanced architectures and did not explicitly consider large fluctuations in layer widths or gains.

The authors suggest that further exploration into accommodating skip connections and refining the understanding of how FPT metrics relate to network dynamics would be valuable future directions.

Summary updated

Abstract

Gradient descent during the learning process of a neural network can be subject to many instabilities. The spectral density of the Jacobian is a key component for analyzing stability. Following the works of Pennington et al., such Jacobians are modeled using free multiplicative convolutions from Free Probability Theory (FPT). We present a reliable and very fast method for computing the associated spectral densities, for given architecture and initialization. This method has a controlled and proven convergence. Our technique is based on an homotopy method: it is an adaptative Newton-Raphson scheme which chains basins of attraction. In order to demonstrate the relevance of our method we show that the relevant FPT metrics computed before training are highly correlated to final test accuracies - up to 85\%. We also nuance the idea that learning happens at the edge of chaos by giving evidence that a very desirable feature for neural networks is the hyperbolicity of their Jacobian at initialization.
BibTeX
@inproceedings{chhaibi2022free,
  author = {Reda Chhaibi and Tariq Daouda and Ezechiel Kahn},
  title = {{Free Probability, Newton lilypads and Jacobians of neural networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=s1s4hBiPCB},
}

Loading related content...

Figure