Paper Info
Title
Early stopping and non-parametric regression: an optimal data-dependent stopping rule
Abstract
Early stopping is a form of regularization based on choosing when to stop running 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.
Year
DOI
Venue
2014
10.5555/2627435.2627446
Journal of Machine Learning Research
Keywords
Field
DocType
kernel ridge regression,empirical processes,reproducing kernel hilbert space,rademacher complexity,early stopping,non-parametric regression,stopping rule,non parametric regression
Applied mathematics,Optimal stopping,Principal component regression,Nonparametric regression,Mean squared error,Artificial intelligence,Stopping time,Early stopping,Mathematical optimization,Pattern recognition,Kernel embedding of distributions,Mathematics,Reproducing kernel Hilbert space
Journal
Volume
Issue
ISSN
15
1
1532-4435
Citations 
PageRank 
References 
21
1.19
8
Authors
3
Name
Order
Citations
PageRank
Garvesh Raskutti127930.13
Martin J. Wainwright27398533.01
Bin Yu31984241.03