Early stopping for non-parametric regression: An optimal data-dependent stopping rule

By Garvesh Raskutti, Martin J. Wainwright, Bin Yu. 2011

336 citations recorded by the source corpus.

The goal of non-parametric regression is to estimate an unknown function f∗ based on n i.i.d. observations of the form y<inf>i</inf> = f∗(x<inf>i</inf>) + w<inf>i</inf>, where {w<inf>i</inf>}n<inf>i=1</inf> are additive noise variables. Simply choosing a function to minimize the least-squares loss 1/2n ∑n<inf>i=1</inf> (y<inf>i</inf> − f(x<inf>i</inf>))2 will lead to “overfitting”, so that various estimators are based on different types of regularization. The early stopping strategy is to run an iterative algorithm such as gradient descent for a fixed but finite number of iterations. Early stopping is known to yield estimates with better prediction accuracy than those obtained by running the algorithm for an infinite number of iterations. Although bounds on this prediction error are known for certain function classes and step size choices, the bias-variance tradeoffs for arbitrary reproducing kernel Hilbert spaces (RKHSs) and arbitrary choices of step-sizes have not been well-understood to date. In this paper, we derive upper bounds on both the L2(P<inf>n</inf>) and L2(P) error for arbitrary RKHSs, and provide an explicit and easily computable data-dependent stopping rule. In particular, it depends only on the sum of step-sizes and the eigenvalues of the empirical kernel matrix for the RKHS. For Sobolev spaces and finite-rank kernel classes, we show that our stopping rule yields estimates that achieve the statistically optimal rates in a minimax sense.

Subfields: Statistics and Probability

How researchers see this paper

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

In Statistics and Probability

Citations in the corpus

Causal Regularization (2019, background): “See also [21] for regularization by early stopping in a different context.”
Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, background): “A second line of research has considered early-stopping of iterative optimization algorithms for KRR, including gradient descent (Yao et al., 2007; Raskutti et al., 2011) and conjugate gradient methods (Blanchard and Kr¨amer, 2010), where early-stopping provides regularization against over-ﬁtting…”
To understand deep learning we need to understand kernel learning (2018, methodology): “One proposed explanation for the performance of deep networks is the idea of implicit regularization introduced by methods such as early stopping in gradient descent [YRC07, RWY14, NTS14, CARR16].”
Refined Generalization Analysis of Gradient Descent for Over-parameterized Two-layer Neural Networks with Smooth Activations on Classification Problems (2019, background): “3 Brief Review of Functional Gradient Methods Functional gradient methods have been mainly studied for gradient boosting [22, 23] and kernel methods [24, 25, 26, 27, 28] in the machine learning community, but more recently it has been found to be useful in explaining the behavior of gradient descent”
A Fine-Grained Spectral Perspective on Neural Networks (2019, background): “A coarse-grained theory, concerned with big-O asymptotics, exists from classical kernel literature [73, 50, 59, 36, 53].”
Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2019, neutral): “Indeed, in a thought-provoking experiment, Zhang et al. (2016) showed that state-of-the-art deep neural network architectures are complex enough that they can be trained to interpolate the data even when the actual labels are replaced by entirely random ones.”
An Overview of Overfitting and its Solutions (2019, background): “The idea has a fairly long history which can be dating back to the 1970s in the context of the Landweber iteration [4].”
Distributed Learning with Regularized Least Squares (2016, methodology): “…of kernel matrices for kernel principal component analysis (Sch¨olkopf et al., 1998; Bach, 2013), incomplete Cholesky decomposition (Fine, 2002), early-stopping of iterative optimization algorithms for gradient descent methods (Yao et al., 2007; Raskutti et al., 2014), and greedy-type algorithms.”
Early Stopping is Nonparametric Variational Inference (2015, methodology): “Raskutti et al. (2014) derived a SURE estimate for SGD in a regression setting.”
Field-aware Factorization Machines for CTR Prediction (2016, background): “Early stopping, which terminates the training process before reaching the best result on training data, can be used to avoid over-fitting for many machine learning problems [17, 18, 19].”
Uncovering Prognosis-Related Genes and Pathways by Multi-Omics Analysis in Lung Cancer (2020, methodology): “Based on our results, a batch size of 1 and epochs of 150, or even between 100 and 150, gave reasonable res lts, while avoiding overfitting by early stopping [47] and/or Rectifi d Linea Unit (ReLU) function replacing t nh function at the last layer [48] did not work well in our autoencoder.”
Modeling, Inference and Optimization With Composable Differentiable Procedures (2016, methodology): “[84] derived a SURE estimate for SGD in a regression setting.”
ASPEN: High-Throughput LoRA Fine-Tuning of Large Language Models with a Single GPU (2023, neutral): “Raskutti et al. [38] apply early stopping as regularization in non-parametric regression.”
Machine learning-based prediction of COVID-19 diagnosis based on symptoms (2021, methodology): “The validation set was used for early stopping 26 , with auROC as the performance measure.”
Non-parametric Stochastic Approximation with Large Step sizes (2014, methodology): “data in Rd, d > 1, and so-called Mercer kernels (continuous kernels over a compact set) that lead to dense subspaces of the space of square-integrable functions and non parametric estimation [4], has been widely studied in the last decade starting with the works of Smale and Cucker [5, 6] and being ”
Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee (2019, background): “It was shown to perform comparably to early-stopped gradient descent (Bauer et al., 2007; Gerfo et al., 2008; Raskutti et al., 2014; Wei et al., 2017).”
Divide and Conquer Kernel Ridge Regression (2013, neutral): “A second line of research has considered early-stopping of iterative optimization algorithms for KRR, including gradient descent (Yao et al., 2007; Raskutti et al., 2011) and conjugate gradient methods (Blanchard and Krämer, 2010), where early-stopping provides regularization against over-fitting…”