Just Interpolate: Kernel "Ridgeless" Regression Can Generalize

By Tengyuan Liang, Alexander Rakhlin. 2018

379 citations recorded by the source corpus.

In the absence of explicit regularization, Kernel "Ridgeless" Regression with nonlinear kernels has the potential to fit the training data perfectly. It has been observed empirically, however, that such interpolated solutions can still generalize well on test data. We isolate a phenomenon of implicit regularization for minimum-norm interpolated solutions which is due to a combination of high dimensionality of the input data, curvature of the kernel function, and favorable geometric properties of the data such as an eigenvalue decay of the empirical covariance and kernel matrices. In addition to deriving a data-dependent upper bound on the out-of-sample error, we present experimental evidence suggesting that the phenomenon occurs in the MNIST dataset.

Subfields: Artificial Intelligence, Statistics and Probability, 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 Statistics and Probability

In Scaling & Learning Theory

Citations in the corpus

Scaling description of generalization with number of parameters in deep learning (2019, positive): “In the context of least-squares regression, the improvement of performance with N has been linked to the observed diminishing fluctuations of the DNN function after training [29], a result consistent with the notion of stronger implicit regularization with increasing N [30, 31].”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Examples of such models include logistic regression on linearly-separable data, non-parametric regression (Liang and Rakhlin, 2018; Belkin et al., 2019), boosting (Schapire et al., 1998), and over-parameterized deep neural networks (Zhang et al., 2017).”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, methodology): “These ﬁrst-order methods have been particularly successful for training highly-expressive, over-parameterized models such as non-parametric regression [47, 7] and deep neural networks [9, 92].”
Does learning require memorization? a short tale about a long tail (2019, background): “There is also recent evidence that this holds for kernel methods in certain regimes as well [11, 32, 54].”
Benign overfitting in linear regression (2019, background): “ernels both interpolate and, with suitable bandwidth choice, give optimal rates for nonparametric estimation (building on earlier consistency results [9] for these unusual kernels). Liang and Rakhlin [18] considered minimum norm interpolating kernel regression with kernels deﬁned as nonlinear functi”
Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks (2020, background): “Recently, interest in explaining the phenomenon of interpolation has led to the study of ridgeless regression (Belkin et al., 2018c;b; 2019; Liang & Rakhlin, 2018), where generalization bounds are kernel and data dependent.”
Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation (2019, background): “These observations have led to recent theoretical activity[3, 4, 16].”
Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks (2021, background): “Moreover, we show that the speciﬁc choice of α , the hyper-parameter that balances between the skip and residual connections, has a signiﬁcant effect on the shape of ResNTK for deep architecture, so, for example, with constant α ResNTK too becomes spiky with depth.”
Understanding and Mitigating the Tradeoff Between Robustness and Accuracy (2020, methodology): “Interpolating estimators for linear regression have been studied in many recent works such as (Ma et al., 2018; Belkin et al., 2018; Hastie et al., 2019; Liang & Rakhlin, 2018; Bartlett et al., 2019).”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “(2010); Cheng and Singer (2013); Fan and Montanari (2019) studied the spectral properties of kernel matrix via Taylor series or Hermite polynomials on the nonlinearity, which in turn explains the generalization of high-dimensional kernel ridgeless interpolators (Liang and Rakhlin, 2018).”
Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2019, neutral): “For example, recent work has investigated interpolation—via kernel ridge regression—in reproducing kernel Hilbert spaces [30, 47].”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, methodology): “…in parallel to our work (Advani et al., 2020; Spigler et al., 2019; Belkin et al., 2018a,b, 2019a,b,c; Nakkiran, 2019; Nakkiran et al., 2020a,b; Liang and Rakhlin, 2020; Hastie et al., 2019; Bartlett et al., 2020; Chinot and Lerasle, 2020; Muthukumar et al., 2020; Mei and Montanari, 2019;…”
Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel (2018, background): “Liang and Rakhlin [39] and Belkin et al. [10] study the generalization of kernel methods.”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “Belkin et al. (2018); Liang and Rakhlin (2018) showed that good generalization performance of overfitted/interpolated classifiers is not only an intriguing feature for deep learning, but also for kernel methods.”
On the Similarity between the Laplace and Neural Tangent Kernels (2020, methodology): “NTK methods can be analyzed to explain many properties of neural networks in this limit, including their convergence in training and ability to generalize [8, 9, 13, 32].”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, background): “[2016], Neyshabur et al. [2017a] note that deep learning often exhibits statistical properties that are counterintuitive to conventional wisdom.”
On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels (2019, background): “On the other hand, Liang and Rakhlin (2018) investigated the regime n d and showed that risk can be upper bounded by a quantity that can be small under favorable spectral properties of the data and the kernel matrix.”