To understand deep learning we need to understand kernel learning

Abstract

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.

References in corpus (11)

• Densely Connected Convolutional Networks
• Understanding deep learning requires rethinking generalization
• An Analysis of Deep Neural Network Models for Practical Applications
• Deep Image Prior
• Spectrally-normalized margin bounds for neural networks
• Early stopping and non-parametric regression: An optimal data-dependent stopping rule
• Empirical Analysis of the Hessian of Over-Parametrized Neural Networks
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Diving into the shallows: a computational perspective on large-scale shallow learning

Cited by in corpus (43)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Benign Overfitting in Linear Regression
• On Exact Computation with an Infinitely Wide Neural Net
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• The Role of Neural Network Activation Functions
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Accelerating SGD with momentum for over-parameterized learning
• Bad Global Minima Exist and SGD Can Reach Them
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Universality Laws for High-Dimensional Learning with Random Features
• A Corrective View of Neural Networks: Representation, Memorization and Learning
• The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers
• On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
• Chaining Mutual Information and Tightening Generalization Bounds
• Minnorm training: an algorithm for training over-parameterized deep neural networks
• Distributional Generalization: A New Kind of Generalization
• On the Similarity between the Laplace and Neural Tangent Kernels
• On the Estimation of Derivatives Using Plug-in Kernel Ridge Regression Estimators
• Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networks
• Interpolating Predictors in High-Dimensional Factor Regression
• To Each Optimizer a Norm, To Each Norm its Generalization
• Interpolation and Learning with Scale Dependent Kernels
• A Differential Topological View of Challenges in Learning with Feedforward Neural Networks
• On Mitigating the Utility-Loss in Differentially Private Learning: A new Perspective by a Geometrically Inspired Kernel Approach
• Limitations of Implicit Bias in Matrix Sensing: Initialization Rank Matters
• On the Universality of the Double Descent Peak in Ridgeless Regression
• Extreme Memorization via Scale of Initialization
• Generalization Error of Generalized Linear Models in High Dimensions
• A Survey on Large-scale Machine Learning
• Provable Robust Classification via Learned Smoothed Densities
• A finite sample analysis of the benign overfitting phenomenon for ridge function estimation
• Trading Signals In VIX Futures
• Convolutional Spectral Kernel Learning
• Prediction in latent factor regression: Adaptive PCR and beyond
• Double Descent Risk and Volume Saturation Effects: A Geometric Perspective
• A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks
• Revisiting minimum description length complexity in overparameterized models
• Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective
• On Generalization of Adaptive Methods for Over-parameterized Linear Regression