Does data interpolation contradict statistical optimality?

By Mikhail Belkin, Alexander Rakhlin, Alexandre B. Tsybakov. 2018

238 citations recorded by the source corpus.

We show that learning methods interpolating the training data can achieve optimal rates for the problems of nonparametric regression and prediction with square loss.

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

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).”
Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, positive): “Recently, there has been an emerging recognition that certain interpolating predictors (not based on ERM) can indeed be provably statistically optimal or near optimal (11, 12), which is compatible with our empirical observations in the interpolating regime.”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “rizationforlogisticregression. Aninterestinglineofworkestablishconnectionbetweenkernelmethods andneuralnetworksandstudythegeneralizationabilitiesofkernelmethodswhenthemodelinterpolatesthe trainingdata[19,10,11,12,38,13]. [18,54,42,53,49]relatethedistributionofthenetworkweightsto Wassersteingradientﬂ”
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].”
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): “bounds. Belkin, Hsu and Mitra [3] gave an example ofaninterpolating nearestneighbordecisionrule with anasymptotic consistency property as the input dimension gets large. Belkin, Rakhlin, and Tsybakov [4] showed that kernel smoothing methods based on singular kernels both interpolate and, with suitab”
Toward Moderate Overparameterization: Global Convergence Guarantees for Training Shallow Neural Networks (2019, background): “This is the subject of a few interesting recent papers [5], [37], [42]–[48].”
Prevalence of neural collapse during the terminal phase of deep learning training (2020, unknown): “[2]”
On the Risk of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels (2019, background): “…work on nonparametric local rules (Belkin et al., 2018b,d), high-dimensional linear regression (Bartlett et al., 2019; Hastie et al., 2019), random features model (Ghorbani et al., 2019), and kernel (ridgeless) regression (Belkin et al., 2018c; Liang and Rakhlin, 2018; Rakhlin and Zhai, 2018).”
The Computational Limits of Deep Learning (2020, background): “Classically this would lead to overfitting, but stochastic gradient-based optimization methods provide a regularizing effect due to early stopping [71, 7]1, moving the neural networks into an interpolation regime, where the training data is fit almost exactly while still maintaining reasonable predi”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, unknown): “[3, 4] study statistical algorithms that minimize convex losses and perfectly interpolate the data, that is, given a sample {S1, .”
Harmless interpolation of noisy data in regression (2019, background): “These phenomena are being actively investigated in a statistical sense [5], [6] and a computational sense [7]– [9] in classification problems and/or noiseless models.”
The Optimal Ridge Penalty for Real-world High-dimensional Data Can Be Zero or Negative due to the Implicit Ridge Regularization (2020, background): “…statistical models can display \/\-shaped ( double descent ) risk curves as a function of model complexity, extending the classical U-shaped risk curves and having small or even the smallest risk in the overparametrized regime (Advani et al., 2020; Spigler et al., 2019; Belkin et al., 2019a).”
Reconciling modern machine learning and the bias-variance trade-off (2018, result): “Recently, there has been an emerging recognition that certain interpolating predictors (not based on ERM) can indeed be statistically optimal or near-optimal [2, 4], which is compatible with our empirical observations in the interpolating regime.”
Nonparametric regression using deep neural networks with ReLU activation function (2017, background): “While it has been observed that there are nonparametric estimators that can interpolate and also achieve fast convergence rates in the nonparametric regression model ([9]), the argument above indicates that implicit regularization in the overfitted regime will not do that.”