Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel

Yutong Wang, Clayton ScottNeurIPS 2022 · OpenReview

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.

  1. 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).
  2. 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.
Geometric mapping between flat Euclidean space and a spherical manifold
  1. 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.

Combining individual partition-based classifiers into a smooth, interpolating ensemble

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

Abstract

Recent research in the theory of overparametrized learning has sought to establish generalization guarantees in the interpolating regime. Such results have been established for a few common classes of methods, but so far not for ensemble methods. We devise an ensemble classification method that simultaneously interpolates the training data, and is consistent for a broad class of data distributions. To this end, we define the manifold-Hilbert kernel for data distributed on a Riemannian manifold. We prove that kernel smoothing regression using the manifold-Hilbert kernel is weakly consistent in the setting of Devroye et al. 1998. For the sphere, we show that the manifold-Hilbert kernel can be realized as a weighted random partition kernel, which arises as an infinite ensemble of partition-based classifiers.
BibTeX
@inproceedings{wang2022consistent,
  author = {Yutong Wang and Clayton Scott},
  title = {{Consistent Interpolating Ensembles via the Manifold-Hilbert Kernel}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=zqQKGaNI4lp},
}
Figure