Can neural networks extrapolate? Discussion of a theorem by Pedro Domingos

Adrien Courtois, Jean‐Michel Morel, Pablo Arias

Abstract

This paper explores a provocative theorem by Pedro Domingos: that every neural network trained via gradient descent is essentially a "kernel machine" in disguise. By extending this theorem to practical, discrete settings, the authors show that while neural networks can occasionally learn perfect algorithms in toy scenarios, they primarily function as sophisticated interpolators that struggle to extrapolate when faced with data far from their training set.

Introduction

Despite their world-changing success, artificial neural networks (NNs) remain "black boxes." We know they work, but we struggle to explain how they make specific predictions or why they fail on certain "out-of-distribution" samples.

A central debate in AI is whether NNs are learning generalizable, algorithmic logic (extrapolation) or simply performing high-dimensional curve-fitting (interpolation). The authors tackle this by examining Domingos' theorem, which suggests the latter. If a network is just a kernel machine, it makes decisions by comparing new inputs to a weighted sum of training examples. This paper seeks to verify if this interpretation holds up in practice and where the limits of this "interpolation-only" view lie.

Methodology

The authors build upon the Neural Tangent Kernel (NTK) framework. Their primary contributions to the theory include:

  • Discrete Extension: Domingos’ original proof assumed continuous gradient descent (infinitesimal steps). The authors provide a version for discrete steps, which matches how we actually train models using algorithms like Stochastic Gradient Descent (SGD).
  • Multi-dimensional Output: They extend the theorem to cover networks that output vectors (like image-to-image tasks) rather than just single scalar values.
  • Interpretability Tools: They use the NTK and t-SNE (a dimensionality reduction technique) to visualize the "feature space" the network creates, allowing them to see if the network groups data by logical labels or simple geometric similarity.
Algorithm 1: Stochastic gradient descent, the training process analyzed in the paper.

Experimental Setup

The study uses several synthetic, controlled datasets to isolate specific behaviors:

  1. Ball vs. Sphere (2D): Classifying points inside a disk versus points on a surrounding ring.
  2. Linearly Separable Points (2D): A simple binary classification task.
  3. 2D Shape Connectivity: A dataset of connected planar shapes (spirals, rings, etc.). The task is "shape completion"—given the boundary, fill in the interior.
  4. 1D Planar Topology: A simplified version of the shape task using binary sequences (0s and 1s) where the goal is to determine if a specific "pixel" is inside a shape based on a cumulative sum (parity) logic.

Results and Discussion

The "Kernel Machine" Reality

In low-dimensional tasks, the network’s behavior is almost perfectly explained by the NTK. It essentially learns a "similarity measure" where it classifies a new point based on how much it "looks like" training samples in a high-dimensional feature space. The models reached ~100% accuracy on the 2D ball/sphere and 1D topology tasks, showing that the NTK-based feature space becomes linearly separable after training.

Fragile Algorithmic Learning

The authors found that a network can learn a perfect algorithm (like the parity bit for 1D topology) if the architecture is perfectly tuned for it. However, this is extremely fragile; slight changes to the kernel size or adding extra layers often caused the network to revert to simple interpolation.

Interpolation vs. Extrapolation

The paper argues that NNs don't truly "extrapolate" in the way humans do. On the 2D shape completion task, the network achieved 99.8% IOU (Intersection Over Union) on data similar to the training set. However, when presented with "tricky" out-of-domain cases like complex nested spirals, the performance dropped significantly (e.g., an IOU of only 51%). It hadn't learned the logic of connectivity; it had learned to interpolate between the shapes in its training set.

Conclusion

The authors acknowledge that their analysis is largely tied to Stochastic Gradient Descent (SGD). Modern optimizers like Adam are more complex, and a direct mathematical analogue of Domingos' theorem for Adam does not yet exist.

Furthermore, while the NTK provides a "powerful insight" in low dimensions, its utility for explaining massive models (like LLMs or large-scale Vision Transformers) is limited by the sheer mathematical complexity of the resulting kernels. Future work is needed to bridge the gap between this "kernel machine" theory and the emergent behaviors seen in billion-parameter models.

Summary updated

Abstract

Neural networks trained on large datasets by minimizing a loss have become the state-of-the-art approach for resolving data science problems, particularly in computer vision, image processing and natural language processing. In spite of their striking results, our theoretical understanding about how neural networks operate is limited. In particular, what are the interpolation capabilities of trained neural networks? In this paper we discuss a theorem of Domingos stating that "every machine learned by continuous gradient descent is approximately a kernel machine". According to Domingos, this fact leads to conclude that all machines trained on data are mere kernel machines. We first extend Domingo's result in the discrete case and to networks with vector-valued output. We then study its relevance and significance on simple examples. We find that in simple cases, the "neural tangent kernel" arising in Domingos' theorem does provide understanding of the networks' predictions. Furthermore, when the task given to the network grows in complexity, the interpolation capability of the network can be effectively explained by Domingos' theorem, and therefore is limited. We illustrate this fact on a classic perception theory problem: recovering a shape from its boundary.
BibTeX
@inproceedings{courtois2023can,
  author = {Adrien Courtois and Jean‐Michel Morel and Pablo Arias},
  title = {{Can neural networks extrapolate? Discussion of a theorem by Pedro Domingos}},
  booktitle = {Revista},
  year = {2023},
  doi = {10.1007/s13398-023-01411-z},
}
Figure