Abstract
Despite the ubiquity of neural networks, the mechanisms behind their generalization remain a subject of intense debate. This paper explores a provocative theorem by Pedro Domingos, which suggests that neural networks trained via gradient descent are essentially "kernel machines" that interpolate between training samples. The authors extend this theorem to practical settings—discrete gradient descent and multi-dimensional outputs—and demonstrate through empirical testing that while these models are powerful interpolators, they often fail to extrapolate to radically new data or learn underlying algorithmic rules.
The Black Box Problem
The "black box" nature of neural networks (NNs) is a primary hurdle in AI theory. While we observe their success, explaining how they generalize from training data to unseen samples is difficult. A central question in AI theory is whether NNs learn fundamental logical rules (extrapolation) or if they act as sophisticated "lookup tables" that compare new inputs to similar training examples (interpolation).
This research investigates a theorem by Pedro Domingos which argues for the latter. If NNs are approximately kernel machines, their predictions are simply weighted sums of similarities to training data. This paper seeks to verify this claim, adapt the mathematics to real-world conditions, and test the limits of NN reasoning on tasks requiring algorithmic logic, such as topology and shape filling.
Theoretical Extensions: From Continuous to Discrete
Domingos' original theorem focused on continuous gradient descent with scalar outputs. To make this applicable to modern deep learning, the authors provide a practical version for discrete gradient descent and multi-dimensional outputs, such as those found in image-to-image tasks.
By analyzing the Neural Tangent Kernel (NTK), the researchers can visualize the "feature space" induced by the network. The NTK describes how outputs change relative to parameters during training, effectively acting as a bridge to understand which training samples the network considers "similar" to a new input. As shown in Algorithm 1, the discrete update steps are the foundation for these gradient estimates.
Experimental Methodology and Datasets
The authors employed several synthetic datasets to isolate specific behaviors:
- Ball vs. Sphere: A 2D classification task distinguishing a solid disk from a hollow ring.
- Linearly Separable Data: A toy problem used to verify the feature space induced by the kernel.
- 2D Shape Completion: 10,000 binary images where the model must fill a shape's interior based on its boundary.
- 1D Planar Topology: A simplified bit-sequence task (e.g.,
00100100) to test if the network can learn an "inside vs. outside" rule.
The Interpolation Barrier
The study's findings confirm that NNs often act as "mirrors" of their training data. For simple problems, the network's similarity measure closely aligns with standard Euclidean distance. Furthermore, the authors found that even with an architecture perfectly suited for a 1D topology problem, gradient descent often failed to find the optimal solution unless initialized very close to it. This suggests that having the "capacity" to learn a rule does not mean gradient descent will actually "find" it.
The most striking result came from the shape-filling task. A U-Net model achieved a near-perfect 99.8% score on shapes similar to its training set. However, when presented with a complex spiral—a shape absent from the training data—it failed significantly, achieving an Intersection Over Union (IOU) of only 51%. This supports the hypothesis that the network did not learn the "algorithm" for filling shapes, but rather learned to interpolate between known examples.
Conclusion and Future Directions
The research reinforces the idea that current neural networks are "mere kernel machines" limited by the interpolation barrier. While the NTK provides a powerful tool for understanding small networks, its interpretability scales poorly with high-dimensional data. Additionally, the theorem currently holds for standard Stochastic Gradient Descent (SGD), while the more complex Adam optimizer remains a challenge for theoretical derivation. Future work must determine if new architectures or training objectives can finally break this barrier and achieve true algorithmic extrapolation.
Summary updated