Early Stopping for Nonparametric Testing
This work provides a theoretical foundation for early stopping in nonparametric testing, which is incremental but clarifies optimality conditions for practitioners in statistics and machine learning.
The authors tackled the problem of applying early stopping to achieve minimax optimal testing in nonparametric settings, showing that a sharp stopping rule yields optimal testing performance, with similar results for estimation.
Early stopping of iterative algorithms is an algorithmic regularization method to avoid over-fitting in estimation and classification. In this paper, we show that early stopping can also be applied to obtain the minimax optimal testing in a general non-parametric setup. Specifically, a Wald-type test statistic is obtained based on an iterated estimate produced by functional gradient descent algorithms in a reproducing kernel Hilbert space. A notable contribution is to establish a "sharp" stopping rule: when the number of iterations achieves an optimal order, testing optimality is achievable; otherwise, testing optimality becomes impossible. As a by-product, a similar sharpness result is also derived for minimax optimal estimation under early stopping studied in [11] and [19]. All obtained results hold for various kernel classes, including Sobolev smoothness classes and Gaussian kernel classes.