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

Abstract

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 $L^2(P)$ and $L^2(P_n)$ 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.

29 pages, 4 figures

References in corpus (1)

• Approximation and learning by greedy algorithms

Cited by in corpus (41)

• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• To understand deep learning we need to understand kernel learning
• Deep Learning Methods for Solving Linear Inverse Problems: Research Directions and Paradigms
• Distributed learning with regularized least squares
• The Internet of Federated Things (IoFT): A Vision for the Future and In-depth Survey of Data-driven Approaches for Federated Learning
• The DNNLikelihood: enhancing likelihood distribution with Deep Learning
• Gradient Descent can Learn Less Over-parameterized Two-layer Neural Networks on Classification Problems
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network
• Simple and Effective Regularization Methods for Training on Noisily Labeled Data with Generalization Guarantee
• Iterative Regularization for Learning with Convex Loss Functions
• High-Dimensional Linear Regression via Implicit Regularization
• Don't relax: early stopping for convex regularization
• Early stopping for kernel boosting algorithms: A general analysis with localized complexities
• Early Stopping is Nonparametric Variational Inference
• Kernel Ridge Regression via Partitioning
• A Partially Linear Framework for Massive Heterogeneous Data
• Coresets for Robust Training of Neural Networks against Noisy Labels
• On the Complexity of Learning with Kernels
• Early Stopping in Deep Networks: Double Descent and How to Eliminate it
• Can Implicit Bias Explain Generalization? Stochastic Convex Optimization as a Case Study
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• Kernel Conjugate Gradient Methods with Random Projections
• Kernel partial least squares for stationary data
• CROP: Towards Distributional-Shift Robust Reinforcement Learning using Compact Reshaped Observation Processing
• Click-through Rate Prediction with Auto-Quantized Contrastive Learning
• Iterative regularization for convex regularizers
• Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Boosting: Why You Can Use the HP Filter
• Data-Adaptive Discriminative Feature Localization with Statistically Guaranteed Interpretation
• Implicit Sparse Regularization: The Impact of Depth and Early Stopping
• Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping
• Fast Calculation of Probabilistic Optimal Power Flow: A Deep Learning Approach
• Revisiting minimum description length complexity in overparameterized models
• An algorithmic view of ${\ell }_2$ regularization and some path-following algorithms
• Diabetic Retinopathy detection by retinal image recognizing
• Minimum discrepancy principle strategy for choosing $k$ in $k$-NN regression
• NYTRO: When Subsampling Meets Early Stopping
• Early stopping and polynomial smoothing in regression with reproducing kernels
• Kernel-based Partial Permutation Test for Detecting Heterogeneous Functional Relationship
• Adaptive Stopping Rule for Kernel-based Gradient Descent Algorithms