Modern machine learning frequently operates in the "interpolation regime," where models perfectly fit training data (achieving zero training error) yet still generalize remarkably well to unseen data. While classical statistics warns that this should lead to catastrophic overfitting, recent theoretical work has begun to explain why interpolating linear models and certain kernel methods succeed.
However, ensemble methods—such as Random Forests—have remained a theoretical mystery in this context. Until now, there was no known ensemble method proven to be both "interpolating" and statistically "consistent" (guaranteed to converge to the optimal solution as data increases) for a broad class of distributions.
This NeurIPS 2022 paper bridges that gap. By introducing a novel mathematical tool called the manifold-Hilbert kernel, the authors provide the first theoretical demonstration of a consistent, interpolating ensemble method in arbitrary dimensions.
The Manifold-Hilbert Kernel
To achieve this breakthrough, the authors rely on three foundational pillars, starting with the extension of classical kernel theory to curved spaces.
- Riemannian Manifolds: Instead of assuming data lives in flat Euclidean space, the authors define their kernel on Riemannian manifolds (smooth, curved spaces like the surface of a sphere).
- The Manifold-Hilbert Kernel ($K_M^H$): They extend the classical "Hilbert kernel" to these manifolds. The kernel is defined mathematically as $dist_M(x, \xi)^{-d}$, where $d$ is the dimension of the space.
- Singular Kernels for Interpolation: The Hilbert kernel is "singular," meaning its value approaches infinity as the distance between two points drops to zero. While singularities are often viewed as numerical bugs, here, the $1/dist^d$ singularity is a deliberate feature. When used in kernel smoothing (like a Nadaraya-Watson estimator), this singularity forces the model to perfectly "memorize" the training labels at their exact locations, guaranteeing interpolation without destroying the model's ability to generalize elsewhere.
Ensembles as Kernels
The most striking insight of the paper is the mathematical equivalence between this singular kernel and an infinite ensemble of classifiers.
The authors define a new class of kernels called Weighted Random Partition (WRP) Kernels. These can be conceptualized as an infinite, weighted average of "histogram classifiers"—simple models that partition space into discrete cells.
Crucially, the authors prove that on a $d$-dimensional sphere, the manifold-Hilbert kernel is exactly equivalent to a weighted ensemble of classifiers based on random hyperplane arrangements. This geometric bridge allows them to use the rigorous machinery of kernel theory to prove the properties of ensemble methods.
Key Theoretical Results
Because this is a theoretical paper, it relies on mathematical abstractions (like continuous distributions on the $d$-Sphere) rather than empirical datasets like ImageNet. The primary theoretical contributions are:
- Weak Consistency on Manifolds (Theorem 3.2): The paper establishes that kernel smoothing regression using the manifold-Hilbert kernel is "weakly consistent." As the number of training samples $n$ approaches infinity, the model's error converges to the best possible error (the Bayes error), even though it perfectly interpolates every training point.
- Equivalence on the Sphere (Theorem 5.2): It formally proves that on a sphere, this kernel is a Weighted Random Partition Kernel.
- A Theoretical First: This work stands as the first formal proof of an ensemble method that is both interpolating and consistent for a broad class of distributions in arbitrary dimensions.
Limitations and Future Directions
While a significant theoretical milestone, the paper notes several limitations that pave the way for future research:
- Data-Independence: The random partitions (hyperplanes) analyzed in this paper are "data-independent." In practical algorithms like Random Forests, partitions are "data-dependent" (splits are chosen based on the training data). Analyzing data-dependent interpolating ensembles remains a complex, open problem.
- Rates of Convergence: The authors prove that the method converges (consistency), but they leave the question of how fast it converges (the rate of convergence) for future work.
- Computational Complexity: Evaluating an infinite ensemble or a singular kernel is computationally intensive. The paper focuses on theoretical existence and statistical properties rather than providing an optimized algorithm for large-scale, real-world tasks.
Summary updated