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

arXiv: https://arxiv.org/abs/1306.3574 · HTML: https://mlsanity.com/paper/1306.3574/

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2013.

## Built on by (most cited first, 30 of 89)

- [A Solvable Model of Neural Scaling Laws](https://mlsanity.com/paper/2210.16859/) (2022)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Neural Network-Based Score Estimation in Diffusion Models: Optimization and Generalization](https://mlsanity.com/paper/2401.15604/) (2024)
- [A Statistical Theory of Regularization-Based Continual Learning](https://mlsanity.com/paper/2406.06213/) (2024)
- [Implicit Sparse Regularization: The Impact of Depth and Early Stopping](https://mlsanity.com/paper/2108.05574/) (2021)
- [Generalization Ability of Wide Neural Networks on ℝ](https://mlsanity.com/paper/2302.05933/) (2023)
- [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023)
- [The loss landscape of deep linear neural networks: a second-order analysis](https://mlsanity.com/paper/2107.13289/) (2021)
- [The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning](https://mlsanity.com/paper/2111.05326/) (2021)
- [The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods](https://mlsanity.com/paper/2111.07167/) (2021)
- [A Non-parametric View of FedAvg and FedProx: Beyond Stationary Points](https://mlsanity.com/paper/2106.15216/) (2021)
- [Channel-Wise Early Stopping without a Validation Set via NNK Polytope Interpolation](https://mlsanity.com/paper/2107.12972/) (2021)
- [Optimal Rate of Kernel Regression in Large Dimensions](https://mlsanity.com/paper/2309.04268/) (2023)
- [On Regularization via Early Stopping for Least Squares Regression](https://mlsanity.com/paper/2406.04425/) (2024)
- [Strong inductive biases provably prevent harmless interpolation](https://mlsanity.com/paper/2301.07605/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterization](https://mlsanity.com/paper/2502.01347/) (2025)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (2022)
- [Data adaptive RKHS Tikhonov regularization for learning kernels in operators](https://mlsanity.com/paper/2203.03791/) (2022)
- [Graph Neural Networks for Low-Energy Event Classification & Reconstruction in IceCube](https://mlsanity.com/paper/2209.03042/) (2022)
- [The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [Click-through Rate Prediction with Auto-Quantized Contrastive Learning](https://mlsanity.com/paper/2109.13921/) (2021)
- [Random features models: a way to study the success of naive imputation](https://mlsanity.com/paper/2402.03839/) (2024)
- [Random Smoothing Regularization in Kernel Gradient Descent Learning](https://mlsanity.com/paper/2305.03531/) (2023)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (2023)
- [Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping](https://mlsanity.com/paper/2107.05341/) (2021)
- [Comparing Classes of Estimators: When does Gradient Descent Beat Ridge Regression in Linear Models?](https://mlsanity.com/paper/2108.11872/) (2021)
- [A Neural Phillips Curve and a Deep Output Gap](https://mlsanity.com/paper/2202.04146/) (2022)
- [Lazy Estimation of Variable Importance for Large Neural Networks](https://mlsanity.com/paper/2207.09097/) (2022)
- [Learning Lipschitz Functions by GD-trained Shallow Overparameterized ReLU Neural Networks](https://mlsanity.com/paper/2212.13848/) (2022)

## Abstract (arXiv)

The strategy of early stopping is a regularization technique based on choosing a stopping time for an iterative algorithm. Focusing on non-parametric regression in a reproducing kernel Hilbert space, we analyze the early stopping strategy for a form of gradient-descent applied to the least-squares loss function. We propose a data-dependent stopping rule that does not involve hold-out or cross-validation data, and we prove upper bounds on the squared error of the resulting function estimate, measured in either the L2(P) and L2(Pn) norm. These upper bounds lead to minimax-optimal rates for various kernel classes, including Sobolev smoothness classes and other forms of reproducing kernel Hilbert spaces. We show through simulation that our stopping rule compares favorably to two other stopping rules, one based on hold-out data and the other based on Stein's unbiased risk estimate. We also establish a tight connection between our early stopping strategy and the solution path of a kernel ridge regression estimator.