eGAD! double descent is explained by Generalized Aliasing Decomposition

Mark K. Transtrum, Gus L. W. Hart, Tyler J. Jarvis, Jared P. Whitehead

TL;DR

Researchers have introduced the Generalized Aliasing Decomposition (GAD), a novel framework that explains the mysterious "double descent" phenomenon where adding more parameters to a model actually improves its performance. By breaking down predictive error into model insufficiency, data insufficiency, and generalized aliasing, GAD provides a unified theory that works where the classical bias-variance trade-off fails.

What Problem Does This Paper Address?

In classical statistics, we are taught the "U-shaped" error curve: as a model gets more complex, bias goes down but variance goes up. The goal is to find the "sweet spot" in the middle. However, modern machine learning has turned this on its head. We often see "double descent": error goes down, then up (at the "interpolation threshold" where parameters equal data points), and then—counterintuitively—goes down again as we add even more parameters.

The traditional bias-variance decomposition struggles to explain this second descent or the even weirder "multiple descent" patterns seen in structured scientific data. This paper aims to provide a rigorous mathematical explanation for these non-monotonic error curves that applies across machine learning, signal processing, and physics.

Methods

The authors propose the Generalized Aliasing Decomposition (GAD). They frame the learning problem as partitioning a "universal" function space into modeled and unmodeled subspaces. The predictive error is decomposed into three distinct, intuitive components:

  1. Model Insufficiency: The error caused by the model being too simple to represent the true signal (roughly equivalent to classical bias). It decreases monotonically as you add parameters.
  2. Data Insufficiency: The error arising because the available data doesn't uniquely constrain the model parameters (related to the "minimal norm" solution in over-parameterized regimes). This increases as the model grows.
  3. Generalized Aliasing: The "star" of the paper. This term quantifies how unmodeled components of the signal are "misinterpreted" or aliased into the modeled parameters.

The authors use linear regression and the Moore-Penrose pseudoinverse as their primary mathematical playground, showing that the "aliasing operator" can be calculated based solely on the model choice and the sampling locations—without ever needing the actual data labels.

Datasets

The paper validates GAD across several diverse domains:

  • Image Classification: MNIST and CIFAR-10 using Random ReLU Features (RRF) and Random Fourier Features (RFF).
  • Synthetic Geometry: Points on the Mei-Montanari (MM) sphere.
  • Differential Equations: Solving a 1D boundary value problem using collocation methods with various bases (Fourier-sine, cubic splines, high-order splines).
  • Materials Science: A cluster expansion model for a Pt-Cu (Platinum-Copper) alloy, predicting formation enthalpy based on atomic configurations.

Key Insights and Ideas

  • Aliasing is Universal: We usually think of aliasing in terms of jagged edges in images or "wagon-wheel" effects in video. This paper shows it's a fundamental property of any model that truncates a complex reality. High-frequency "noise" gets folded into low-frequency "signal" parameters.
  • The Peak is a Projection Issue: The sharp spike in error at the interpolation threshold is mathematically explained by a peak in the norm of the aliasing operator. When the number of parameters matches the number of data points, the model is most sensitive to unmodeled signals.
  • Label-Free Analysis: Because the aliasing operator depends only on the basis functions and the training points, researchers can predict where a model will fail (the peaks) and how to design better experiments before they even collect a single data label.
  • "Over-modeling" vs. "Over-fitting": The authors distinguish between these two. Over-modeling (high data insufficiency) happens when we include parameters that the data cannot possibly resolve, leading to poor performance even if the model is "correct."

Key Results

  • Explaining Double Descent: In random feature models (MNIST/CIFAR), the GAD terms perfectly track the risk curve. The aliasing term creates the characteristic peak at the interpolation threshold, while model insufficiency drops off.
  • Multiple Descent in Physics: In the Pt-Cu alloy model, the risk curve shows multiple peaks and valleys. GAD reveals that these correspond to transitions where new basis functions (like triplet or quadruplet atomic interactions) transition from being linearly independent to dependent on the sampled data.
  • Optimizing ODE Solvers: The authors show that for differential equations, the "classical sweet spot" is often the interpolation threshold itself, but only if the basis is perfectly adapted to the sampling points (like the Fourier basis on uniform points). If points are perturbed, aliasing emerges, and the "sweet spot" shifts.
  • Regularization's Role: They demonstrate that $L_2$ regularization (Ridge regression) works by suppressing the aliasing peak, though it can inadvertently increase data insufficiency.

Limitations and Future Work

  • Linearity: The current formal analysis is rooted in linear regression. While the authors argue that many modern models (like wide neural networks via Neural Tangent Kernels) behave linearly during training, a full non-linear extension of GAD remains an open challenge.
  • The "Asymptotic" Question: A major open question is determining exactly when the over-parameterized "modern" regime will outperform the "classical" sweet spot. GAD provides the tools to ask this question precisely (by comparing data insufficiency to model insufficiency), but a general rule-of-thumb is still elusive.
  • Computational Cost: For very large "universal" spaces, calculating the full aliasing operator might be computationally expensive, though the authors suggest local linearizations as a path forward.

Summary updated

Abstract

A central problem in data science is to use potentially noisy samples of an unknown function to predict values for unseen inputs. In classical statistics, predictive error is understood as a trade-off between the bias and the variance that balances model simplicity with its ability to fit complex functions. However, over-parameterized models exhibit counterintuitive behaviors, such as "double descent" in which models of increasing complexity exhibit decreasing generalization error. Others may exhibit more complicated patterns of predictive error with multiple peaks and valleys. Neither double descent nor multiple descent phenomena are well explained by the bias-variance decomposition. We introduce a novel decomposition that we call the generalized aliasing decomposition (GAD) to explain the relationship between predictive performance and model complexity. The GAD decomposes the predictive error into three parts: 1) model insufficiency, which dominates when the number of parameters is much smaller than the number of data points, 2) data insufficiency, which dominates when the number of parameters is much greater than the number of data points, and 3) generalized aliasing, which dominates between these two extremes. We demonstrate the applicability of the GAD to diverse applications, including random feature models from machine learning, Fourier transforms from signal processing, solution methods for differential equations, and predictive formation enthalpy in materials discovery. Because key components of the GAD can be explicitly calculated from the relationship between model class and samples without seeing any data labels, it can answer questions related to experimental design and model selection before collecting data or performing experiments. We further demonstrate this approach on several examples and discuss implications for predictive modeling and data science.
BibTeX
@misc{transtrum2024egad,
  author = {Mark K. Transtrum and Gus L. W. Hart and Tyler J. Jarvis and Jared P. Whitehead},
  title = {{eGAD! double descent is explained by Generalized Aliasing Decomposition}},
  year = {2024},
  eprint = {2408.08294},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.08294},
}
Figure