Boosting with early stopping: Convergence and consistency

Abstract

Boosting is one of the most significant advances in machine learning for classification and regression. In its original and computationally flexible version, boosting seeks to minimize empirically a loss function in a greedy fashion. The resulting estimator takes an additive function form and is built iteratively by applying a base estimator (or learner) to updated samples depending on the previous iterations. An unusual regularization technique, early stopping, is employed based on CV or a test set. This paper studies numerical convergence, consistency and statistical rates of convergence of boosting with early stopping, when it is carried out over the linear span of a family of basis functions. For general loss functions, we prove the convergence of boosting's greedy optimization to the infinimum of the loss function over the linear span. Using the numerical convergence result, we find early-stopping strategies under which boosting is shown to be consistent based on i.i.d. samples, and we obtain bounds on the rates of convergence for boosting estimators. Simulation studies are also presented to illustrate the relevance of our theoretical results for providing insights to practical aspects of boosting. As a side product, these results also reveal the importance of restricting the greedy search step-sizes, as known in practice through the work of Friedman and others. Moreover, our results lead to a rigorous proof that for a linearly separable problem, AdaBoost with ε\to0 step-size becomes an L^1-margin maximizer when left to run to convergence.

Published at http://dx.doi.org/10.1214/009053605000000255 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (3)

• Local Rademacher complexities
• Complexity regularization via localized random penalties
• Complexities of convex combinations and bounding the generalization error in classification

Cited by in corpus (20)

• Boosting Algorithms: Regularization, Prediction and Model Fitting
• Boosting for high-dimensional linear models
• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Complexities of convex combinations and bounding the generalization error in classification
• Small area estimation of the homeless in Los Angeles: An application of cost-sensitive stochastic gradient boosting
• Boosting in the presence of outliers: adaptive classification with non-convex loss functions
• Analysis of boosting algorithms using the smooth margin function
• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• Robust and Efficient Boosting Method using the Conditional Risk
• Rejoinder: One-step sparse estimates in nonconcave penalized likelihood models
• High-Dimensional Linear Regression via Implicit Regularization
• Coupling the reduced-order model and the generative model for an importance sampling estimator
• SigOpt Mulch: An Intelligent System for AutoML of Gradient Boosted Trees
• Survival ensembles by the sum of pairwise differences with application to lung cancer microarray studies
• Forecasting Player Behavioral Data and Simulating in-Game Events
• Boosted nonparametric hazards with time-dependent covariates
• Generalized Embedding Machines for Recommender Systems
• Generalization Error Curves for Analytic Spectral Algorithms under Power-law Decay
• Rethinking Breiman's Dilemma in Neural Networks: Phase Transitions of Margin Dynamics
• EVIboost for the Estimation of Extreme Value Index under Heterogeneous Extremes