Timezone: »
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. All obtained results hold for various kernel classes, including Sobolev smoothness classes and Gaussian kernel classes.
Author Information
Meimei Liu (Duke University)
Guang Cheng (Purdue University)
More from the Same Authors
-
2021 : Optimum-statistical Collaboration Towards Efficient Black-boxOptimization »
Wenjie Li · Chi-Hua Wang · Guang Cheng -
2022 Poster: Fair Bayes-Optimal Classifiers Under Predictive Parity »
Xianli Zeng · Edgar Dobriban · Guang Cheng -
2022 Poster: Why Do Artificially Generated Data Help Adversarial Robustness »
Yue Xing · Qifan Song · Guang Cheng -
2022 Poster: Phase Transition from Clean Training to Adversarial Training »
Yue Xing · Qifan Song · Guang Cheng -
2021 Poster: On the Algorithmic Stability of Adversarial Training »
Yue Xing · Qifan Song · Guang Cheng -
2020 Poster: Efficient Variational Inference for Sparse Deep Learning with Theoretical Guarantee »
Jincheng Bai · Qifan Song · Guang Cheng -
2020 Poster: Statistical Guarantees of Distributed Nearest Neighbor Classification »
Jiexin Duan · Xingye Qiao · Guang Cheng -
2020 Poster: Directional Pruning of Deep Neural Networks »
Shih-Kang Chao · Zhanyu Wang · Yue Xing · Guang Cheng -
2019 Poster: Bootstrapping Upper Confidence Bound »
Botao Hao · Yasin Abbasi Yadkori · Zheng Wen · Guang Cheng -
2019 Poster: Rates of Convergence for Large-scale Nearest Neighbor Classification »
Xingye Qiao · Jiexin Duan · Guang Cheng -
2015 Poster: Non-convex Statistical Optimization for Sparse Tensor Graphical Model »
Wei Sun · Zhaoran Wang · Han Liu · Guang Cheng