Source-linked AI summary
To understand deep learning we need to understand kernel learning
Mikhail Belkin, Siyuan Ma, Soumik Mandal
TL;DR
The paper asks why overparameterized models can fit training data exactly yet generalize well, and examines whether this phenomenon is specific to deep learning. It combines experiments on kernel classifiers with theoretical analysis of smooth-kernel norms and existing bounds, finding strong parallels with deep networks and similar test behavior across Gaussian and Laplacian kernels. These results motivate new theories of kernel methods as a tractable route toward understanding deep learning.
Problem
Deep networks can interpolate training data while generalizing well, but existing analyses do not adequately explain this phenomenon or establish whether it is unique to deep learning.
Method
The paper studies overfitted and interpolated kernel classifiers experimentally across real and synthetic datasets and analyzes norm lower bounds and existing generalization bounds for smooth kernels.
Results
Overfitted kernel classifiers generalize well under high label noise; Gaussian and Laplacian classifiers have similar test performance, while smooth-kernel norms grow nearly exponentially and existing bounds fail for interpolation.
Takeaways & Limitations
Kernel methods reproduce key overfitting phenomena associated with deep learning, so understanding their inductive bias and kernel structure is important for developing explanatory theory.
Takeaways & Limitations
For deep networks, there is no analogue of the Representer Theorem and no clear counterpart to the RKHS norm used in kernel analysis.
Abstract
from arXiv · showhide
Generalization performance of classifiers in deep learning has recently become a subject of intense study. Deep models, typically over-parametrized, tend to fit the training data exactly. Despite this "overfitting", they perform well on test data, a phenomenon not yet fully understood. The first point of our paper is that strong performance of overfitted classifiers is not a unique feature of deep learning. Using six real-world and two synthetic datasets, we establish experimentally that kernel machines trained to have zero classification or near zero regression error perform very well on test data, even when the labels are corrupted with a high level of noise. We proceed to give a lower bound on the norm of zero loss solutions for smooth kernels, showing that they increase nearly exponentially with data size. We point out that this is difficult to reconcile with the existing generalization bounds. Moreover, none of the bounds produce non-trivial results for interpolating solutions. Second, we show experimentally that (non-smooth) Laplacian kernels easily fit random labels, a finding that parallels results for ReLU neural networks. In contrast, fitting noisy data requires many more epochs for smooth Gaussian kernels. Similar performance of overfitted Laplacian and Gaussian classifiers on test, suggests that generalization is tied to the properties of the kernel function rather than the optimization process. Certain key phenomena of deep learning are manifested similarly in kernel methods in the modern "overfitted" regime. The combination of the experimental and theoretical results presented in this paper indicates a need for new theoretical ideas for understanding properties of classical kernel methods. We argue that progress on understanding deep learning will be difficult until more tractable "shallow" kernel methods are better understood.
1 Introduction
The paper argues that strong generalization despite exact training fit is not unique to deep networks: overfitted kernel classifiers show similar behavior, while existing bounds fail to explain it. Experiments and theory instead highlight kernel structure and minimum-norm inductive bias as central objects for new analysis.
- Empirical properties of overfitted and interpolated kernel classifiers: Zero-error or near-zero-error kernel classifiers generalize well across six real-world and two synthetic datasets, even with substantial label noise.Early stopping provides at most a minor performance improvement.
- Kernel structure and optimization: Interpolated Gaussian and Laplacian classifiers have very similar test performance on real and synthetic data, including after adding label noise.Laplacian kernels fit random labels easily, whereas Gaussian kernels are much harder to optimize on noisy labels.
- Theoretical results and the supporting experimental evidence: Smooth-kernel zero-loss solutions have RKHS norms that grow nearly exponentially with data size, causing most norm-dependent generalization bounds to diverge.Existing bounds also provide no non-trivial guarantees for interpolating classifiers.
- Empirical properties of overfitted and interpolated kernel classifiers: With known or injected label noise, interpolated kernel classifiers achieve test error slightly below the noise level, even at very high noise levels.This behavior makes existing bounds unlikely to explain their observed generalization performance.
- Inductive bias in interpolation: Minimum-RKHS-norm interpolants impose inductive bias despite fitting the data exactly, and their generalization properties depend on kernel and RKHS structure.The Representer Theorem restricts the minimum-norm interpolant to a linear combination of kernel functions supported on the training points.
- Inductive bias in interpolation: Gradient descent initialized in the data-kernel span converges to the minimum-norm interpolating solution, linking optimization-induced bias to the kernel interpolant.Initialization outside that span need not converge to the minimum-RKHS-norm solution.
2 Setup
The setup defines minimum-norm RKHS interpolants, their finite-dimensional kernel representations, and the distinction between interpolation and classification overfitting. It also establishes why these solutions are analytically and computationally tractable, while noting possible inductive-bias parallels with neural networks.
- RKHS and interpolation: A positive-definite kernel induces an RKHS, where the minimum-norm interpolant is defined subject to matching all training labels.The Representer Theorem guarantees existence under the stated non-conflicting-label condition.
- RKHS and interpolation: The interpolant has coefficients α*=K^-1y, and the resulting function exactly matches every training label.Invertibility of the positive-definite kernel matrix ensures the explicit solution interpolates the data.
- Optimization formulation: For any non-negative loss vanishing at correct predictions, the minimum-norm interpolant minimizes empirical loss; strictly convex losses make its coefficient vector unique.The square loss is given as a principal example.
- Optimization formulation: The optimization can be performed over α∈R^n, enabling iterative solvers that avoid the generally prohibitive n^3 cost of matrix inversion.This finite-dimensional formulation supports the computational treatment used in the paper.
- Scope and motivation: Gaussian and Laplacian kernels are used alongside direct linear-system solvers and iterative methods, while neural-network inductive bias lacks an analogous Representer Theorem.The paper presents kernel machines as analytically tractable models for studying such biases.
- Terminology: Interpolation means zero or near-zero training square loss, whereas overfitting means zero or near-zero classification loss, with interpolation implying overfitting but not conversely.The theoretical bounds additionally require a small fixed training margin for overfitted classifiers.
3 Generalization Performance of Overfitted/Interpolating Classifiers
This section evaluates iterative and direct kernel classifiers in the interpolating regime. Across the reported datasets, training error reaches zero or nearly zero while test performance remains stable and is generally optimal or near-optimal, challenging the value of early stopping.
- Iterative training: Kernel classifiers trained with EigenPro-SGD achieve near-zero training loss while maintaining stable test regression and classification error as epochs increase.For Laplacian kernels, test error generally decreases before stabilizing.
- Iterative training: Early stopping provides a small or no improvement in classification or regression error despite reducing training loss.The reported test behavior does not support a substantial regularization benefit from stopping early.
- Iterative training: 20 epochs yield zero training classification error on all reported datasets except 20 Newsgroups with Gaussian/Laplacian kernels and HINT-S with Gaussian kernels.The training classification error is described as similarly small during the iterative experiments.
- Direct interpolation: Direct interpolating solutions are optimal or close to optimal on test for both regression and classification in all reported cases.Their training interpolation error is usually close to numerical precision.
- Broader comparison: The observed behavior parallels deep networks that fit training data exactly and extends prior observations by systematically examining kernel interpolation and square-loss generalization.The authors characterize the phenomenon as apparently ubiquitous for kernel methods.
- Theoretical implications: Existing margin bounds are unlikely to explain generalization in overfitted and interpolated regimes, motivating the section’s analysis of their limitations.The following section is introduced as an examination of why such bounds lack insight here.
4 Existing Bounds Provide No Guarantees for Interpolated Kernel Classifiers
For smooth kernels with nonzero label noise, interpolating or t-overfitted solutions require rapidly growing RKHS norms, while standard generalization bounds become trivial or do not apply. Experiments nevertheless show near-Bayes test performance under substantial noise, exposing a gap between existing bounds and observed behavior.
- Assumptions: Nonzero label noise is assumed: the label is not a deterministic function of the input on a subset of nonzero measure.This assumption ensures the Bayes-optimal classifier has nonzero loss.
- Definitions: A t-overfitted classifier achieves zero classification loss while maintaining margin y_i h(x_i)>t on a fixed portion of training examples.The margin condition prevents trivial norm reduction by scaling an interpolating solution and is weaker than exact interpolation.
- Theoretical result: For Gaussian-kernel RKHSs, any t-overfitted classifier requires a norm lower bound that grows nearly exponentially with dataset size.The theorem states the bound with constants A,B>0 depending on t; the proof applies to RKHS balls and fat-shattering dimension.
- Existing bounds: Existing kernel generalization bounds become trivial because they depend polynomially on the RKHS norm, while bounds with nonzero accuracy parameters do not apply to interpolated classifiers.The paper reports that no known complexity-based bound has sufficiently tight constants for the high-noise experiments.
- Experimental evidence: Adding 1% noise can increase solution norms by more than an order of magnitude while preserving Bayes-level performance, showing little connection between norm and classifier performance.At 10% noise, performance becomes slightly worse than Bayes optimal; norms also increase quickly with data size, consistent with the theorem.
- Experimental evidence: Even at 80% label corruption, interpolated kernel classifiers closely track Bayes risk and remain above chance, with little difference from overfitted classifiers.The comparison covers Gaussian and Laplacian kernels on Synthetic-2 and MNIST across added-noise levels.
5 Fitting noise: Laplacian and Gaussian kernels, connections to ReLU Networks
Laplacian kernels fit random labels with relatively little additional optimization, paralleling ReLU networks, whereas Gaussian kernels require substantially more computation for noisy data. Despite this optimization difference, their test performance is similar.
- Laplacian kernels and ReLU networks: Random labels require no more than twice the epochs needed for original labels with Laplacian kernels.This parallels ReLU networks, which require about three times as many SGD iterations for random labels.
- Laplacian and Gaussian kernels: Gaussian kernels require many more epochs than Laplacian kernels to fit noisy data.The paper relates this greater computational demand to fat-shattering-dimension considerations for smooth kernels.
- Laplacian kernels and ReLU networks: Laplacian kernels are non-smooth, with a derivative discontinuity reminiscent of ReLU units.The authors conjecture that optimization performance is controlled by the type of non-smoothness.
A Experimental Setup
The experiments use standardized versions of several image, speech, and text datasets, with consistent iterative-method settings and cross-validated Gaussian-kernel bandwidths.
- Datasets: Image datasets are converted to grayscale and rescaled to [0, 1], while HINT-S and TIMIT features are z-score normalized.The datasets include MNIST, CIFAR-10, SVHN, HINT-S, TIMIT, and 20 Newsgroups.
- Datasets: Multiclass labels are mapped to multiple binary labels represented as c-length binary vectors.This provides the binary-label representation used for multiclass experiments.
- Hyperparameters: All iterative methods use mini-batches of size m = 256.The EigenPro preconditioner uses k = 160 eigenvectors from a subsampled training set of size M = 5000, when available.
- Kernel Bandwidth Selection: The Gaussian-kernel bandwidth σ is selected by cross-validation on a small subsampled dataset.Final bandwidths are listed in the paper’s accompanying table.
B Detailed experimental results
The detailed results compare interpolated and overfitted classifiers across datasets, training sizes, label-noise levels, and kernel bandwidths, including MNIST baselines such as k-NN and Bayes optimal performance.
- MNIST training-size and noise results: MNIST experiments report test classification error as a function of training-data size under 0% and 10% added label noise.Interpolated classifiers are compared with k-NN in Figure 7 and summarized in Tables 6 and 7.
- Dataset summaries: The summary tables cover MNIST, CIFAR-10, SVHN, TIMIT, HINT-S-20k, and 20 Newsgroups.These tables organize the reported dataset-level results across the paper’s experimental suite.
- MNIST bandwidth results: MNIST comparisons include overfitted classifiers, interpolated classifiers, and a Bayes-optimal reference across kernel bandwidths.Figure 8 uses test classification error as its y-axis.