Early Stopping for Kernel Boosting Algorithms: A General Analysis With Localized Complexities

DOI10.1109/TIT.2019.2927563zbMATH Open1432.62115arXiv1707.01543OpenAlexW2961238573MaRDI QIDQ5211468FDOQ5211468

Martin J. Wainwright, Fanny Yang, Yuting Wei

Publication date: 28 January 2020

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1707.01543

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Asymptotic properties of nonparametric inference (62G20) Ridge regression; shrinkage estimators (Lasso) (62J07) Generalized linear models (logistic models) (62J12) Order statistics; empirical distribution functions (62G30) Optimal stopping in statistics (62L15)

Cited In (7)

• Title not available (Why is that?)
• Learning the mapping \(\mathbf{x}\mapsto \sum\limits_{i=1}^d x_i^2\): the cost of finding the needle in a haystack
• Smoothed residual stopping for statistical inverse problems via truncated SVD estimation
• 10.1162/jmlr.2003.3.4-5.863
• Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping
• From inexact optimization to learning via gradient concentration
• Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications

This page was built for publication: Early Stopping for Kernel Boosting Algorithms: A General Analysis With Localized Complexities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5211468)