Early stopping of iterative algorithms is a widely-used form of regularization in statistics, commonly used in conjunction with boosting and related gradient-type algorithms. Although consistency results have been established in some settings, such estimators are less well-understood than their analogues based on penalized regularization. In this paper, for a relatively broad class of loss functions and boosting algorithms (including L2-boost, LogitBoost and AdaBoost, among others), we exhibit a direct connection between the performance of a stopped iterate and the localized Gaussian complexity of the associated function class. This connection allows us to show that local fixed point analysis of Gaussian or Rademacher complexities, now standard in the analysis of penalized estimators, can be used to derive optimal stopping rules. We derive such stopping rules in detail for various kernel classes, and illustrate the correspondence of our theory with practice for Sobolev kernel classes.

本文针对一类损失函数和梯度提升算法，展示了停止迭代估计器的性能与相关函数类的本地高斯复杂度之间的直接联系，并证明了高斯或Rademacher 复杂性的本地不动点分析可以用于推导最佳停止规则，为各种核类别推导了这种停止规则，并说明了我们理论和实践的对应关系。

核提升算法的早停策略：带局部复杂度的普适分析