To understand deep learning we need to understand kernel learning

By Mikhail Belkin, Siyuan Ma, Soumik Mandal. 2018

446 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Scaling & Learning Theory

Citations in the corpus

The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, background): “, 2017), kernel machines (Belkin et al., 2018) and boosting (Schapire et al.”
Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, background): “Moreover, in direct challenge to the bias-variance trade-off philosophy, recent empirical evidence indicates that neural networks and kernel machines trained to interpolate the training data obtain near-optimal test results even when the training data are corrupted with high levels of noise [42, 4].”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Finally, we note that the intriguing generalization phenomena in deep learning were observed in kernel methods as well (Belkin et al., 2018).”
On Exact Computation with an Infinitely Wide Neural Net (2019, background): “Indeed, this can be viewed as another example of our lack of understandings of kernel methods [Belkin et al., 2018].”
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation (2020, background): “Another line of research focuses on the generalization error of algorithms that fit the data perfectly (referred to as interpolating) [29, 10, 8, 20, 9, 25, 5, 7, 14, 21].”
Does learning require memorization? a short tale about a long tail (2019, background): “Another line of research studies generalization properties of learning algorithms that fit the training data perfectly, often referred to as interpolating [10, 11].”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, background): “This paper continues the line of work in (Belkin et al., 2018a,c; Belkin, 2018) on understanding theoretical mechanisms for the good out-of-sample performance of interpolation.”
Benign overfitting in linear regression (2019, background): “Belkin, Ma and Mandal [14] described an experimental study demonstrating that this phenomenon of accurate prediction for functions that interpolate noisy data also occurs for prediction rules chosen from reproducing kernel Hilbert spaces, and explained the mismatch between this phenomenon and…”
On the Margin Theory of Feedforward Neural Networks (2018, background): “Liang & Rakhlin (2018) and Belkin et al. (2018) study the generalization of kernel methods.”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, background): “It has been shown that Gaussian kernel can achieve impressive accuracy on MNIST and CIFAR10 data without any explicit regularization (Zhang et al., 2017; Belkin et al., 2018b; Liang and Rakhlin, 2020) and that positive ridge regularization decreases the performance (Liang and Rakhlin, 2020).”
Continual Learning in Linear Classification on Separable Data (2023, background): “Even in the broader deep learning scope, theoreticians often start from very simple models and use them to gain insight into phenomena arising in more practical models (e.g., Belkin et al. (2018); Woodworth et al. (2020)).”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, unknown): “[10] study the generalization of kernel methods.”
The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve (2019, background): “[BMM18] Mikhail Belkin, Siyuan Ma, and Soumik Mandal, To understand deep learning we need to understand kernel learning, arXiv:1802.”
Bad Global Minima Exist and SGD Can Reach Them (2019, background): “Following recent work [2, 3, 4, 5, 6, 7], our study is motivated by the desire to shed some light onto this miracle which stands at the center of the recent machine learning revolution.”
Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits (2019, background): “(1.1) has loss zero (i.e., f p x i q “ y i with p x i , y i q ’s scan the support of P ), we refer to the problem as the interpolation problem (Zhang et al., 2016; Belkin et al., 2018b; Ma et al., 2017; Liang and Rakhlin, 2018; Rakhlin and Zhai, 2018; Belkin et al., 2018a).”
Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS (2020, background): “[7] showed experimentally that the Laplace kernel and neural networks had similar performance in fitting random labels.”
Reconciling modern machine learning and the bias-variance trade-off (2018, background): “Favoring small norm interpolating predictors turns out to be a useful inductive bias on MNIST and many other data sets, a phenomenon that can be explained mathematically under some modeling assumptions that we describe in Appendix A, and that has been empirically observed [3].”
Uniform convergence may be unable to explain generalization in deep learning (2019, background): “However, this dependence was not the focus of these studies, and hence it was not known that generalization bounds could increase with m. Belkin et al. (2018) reported a similar paradox in kernel learning where norms that appear in kernel generalization bounds increase with m.”