Early stopping and polynomial smoothing in regression with reproducing
  kernels
  In this paper, we study the problem of early stopping for iterative learning
algorithms in a reproducing kernel Hilbert space (RKHS) in the nonparametric
regression framework. In particular, we work with the gradient descent and
(iterative) kernel ridge regression algorithms. We present a data-driven rule
to perform early stopping without a validation set that is based on the
so-called minimum discrepancy principle. This method enjoys only one assumption
on the regression function: it belongs to a reproducing kernel Hilbert space
(RKHS). The proposed rule is proved to be minimax-optimal over different types
of kernel spaces, including finite-rank and Sobolev smoothness classes. The
proof is derived from the fixed-point analysis of the localized Rademacher
complexities, which is a standard technique for obtaining optimal rates in the
nonparametric regression literature. In addition to that, we present simulation
results on artificial datasets that show the comparable performance of the
designed rule with respect to other stopping rules such as the one determined
by V-fold cross-validation.
