Boosting with early stopping: convergence and consistency

DOI10.1214/009053605000000255zbMATH Open1078.62038arXivmath/0508276OpenAlexW3098897816WikidataQ56169183 ScholiaQ56169183MaRDI QIDQ2583412FDOQ2583412

Authors: Tong Zhang, Bin Yu 

Publication date: 16 January 2006

Published in: The Annals of Statistics (Search for Journal in Brave)

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 epsilon o0 step-size becomes an L^1-margin maximizer when left to run to convergence.

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

Recommendations

• Boosting as a regularized path to a maximum margin classifier
• scientific article; zbMATH DE number 2089371
• Early stopping in \(L_{2}\)Boosting
• Some theory for generalized boosting algorithms
• scientific article; zbMATH DE number 2089370

zbMATH Keywords

cross validationmatching pursuitgreedy optimization

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Nonparametric regression and quantile regression (62G08) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Stopping times; optimal stopping problems; gambling theory (60G40)

Cites Work

• A decision-theoretic generalization of on-line learning and an application to boosting
• The elements of statistical learning. Data mining, inference, and prediction
• Greedy function approximation: A gradient boosting machine.
• Weak convergence and empirical processes. With applications to statistics
• Title not available (Why is that?)
• A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
• Universal approximation bounds for superpositions of a sigmoidal function
• Boosting the margin: a new explanation for the effectiveness of voting methods
• Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
• Title not available (Why is that?)
• Matching pursuits with time-frequency dictionaries
• Arcing classifiers. (With discussion)
• Title not available (Why is that?)
• Boosting With theL₂Loss
• Statistical behavior and consistency of classification methods based on convex risk minimization.
• Improved boosting algorithms using confidence-rated predictions
• Local Rademacher complexities
• Empirical margin distributions and bounding the generalization error of combined classifiers
• 10.1162/153244303321897690
• Convexity, Classification, and Risk Bounds
• Sequential greedy approximation for certain convex optimization problems
• 10.1162/1532443041424300
• Logistic regression, AdaBoost and Bregman distances
• Efficient agnostic learning of neural networks with bounded fan-in
• On the Bayes-risk consistency of regularized boosting methods.
• Population theory for boosting ensembles.
• Process consistency for AdaBoost.
• Complexities of convex combinations and bounding the generalization error in classification
• Title not available (Why is that?)
• 10.1162/1532443041424319
• 10.1162/153244304773936108
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (74)

• Variational networks: an optimal control approach to early stopping variational methods for image restoration
• Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting)
• A new perspective on boosting in linear regression via subgradient optimization and relatives
• A new accelerated proximal boosting machine with convergence rate \(O(1/t^2)\)
• Aggregation of estimators and stochastic optimization
• Boosting in the presence of outliers: adaptive classification with nonconvex loss functions
• Title not available (Why is that?)
• Interpreting initial offset boosting via reconstitution in integral domain
• Boosting as a regularized path to a maximum margin classifier
• Dimension reduction boosting
• SVM-boosting based on Markov resampling: theory and algorithm
• Fast and strong convergence of online learning algorithms
• Random gradient boosting for predicting conditional quantiles
• Consistency and generalization bounds for maximum entropy density estimation
• Coupling the reduced-order model and the generative model for an importance sampling estimator
• Boosting for high-dimensional linear models
• Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces
• 10.1162/jmlr.2003.3.4-5.863
• Title not available (Why is that?)
• Accelerated gradient boosting
• The implicit bias of gradient descent on separable data
• A boosting inspired personalized threshold method for sepsis screening
• Title not available (Why is that?)
• AdaBoost is consistent
• Fully corrective boosting with arbitrary loss and regularization
• Stochastic boosting algorithms
• Stochastic boosting algorithms
• On boosting kernel regression
• Small area estimation of the homeless in Los Angeles: an application of cost-sensitive stochastic gradient boosting
• Population theory for boosting ensembles.
• Boosted nonparametric hazards with time-dependent covariates
• Early stopping and non-parametric regression: an optimal data-dependent stopping rule
• Early stopping in \(L_{2}\)Boosting
• Survival ensembles by the sum of pairwise differences with application to lung cancer microarray studies
• Nonparametric stochastic approximation with large step-sizes
• Deep learning: a statistical viewpoint
• Deformation of log-likelihood loss function for multiclass boosting
• Boosting algorithms: regularization, prediction and model fitting
• Deep learning for natural language processing: a survey
• Bi-cross-validation for factor analysis
• Random classification noise defeats all convex potential boosters
• Randomized Gradient Boosting Machine
• A stochastic approximation view of boosting
• Supervised projection approach for boosting classifiers
• Analysis of boosting algorithms using the smooth margin function
• Double machine learning with gradient boosting and its application to the Big \(N\) audit quality effect
• Complexities of convex combinations and bounding the generalization error in classification
• Title not available (Why is that?)
• Convergence and Consistency of Regularized Boosting With Weakly Dependent Observations
• Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications
• Title not available (Why is that?)
• A boosting method for maximization of the area under the ROC curve
• Regularization in statistics
• Optimization by Gradient Boosting
• Rejoinder: One-step sparse estimates in nonconcave penalized likelihood models
• Adaptive step-length selection in gradient boosting for Gaussian location and scale models
• AdaBoost and robust one-bit compressed sensing
• A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
• A large-sample theory for infinitesimal gradient boosting
• Tree-based boosting with functional data
• Fast iterative regularization by reusing data
• Implicit regularization with strongly convex bias: Stability and acceleration
• AdaBoost Semiparametric Model Averaging Prediction for Multiple Categories
• Use of majority votes in statistical learning
• Early stopping for $ L^2 $-boosting in high-dimensional linear models
• Unbiased Boosting Estimation for Censored Survival Data
• The vanishing learning rate asymptotic for linear \(L^2\)-boosting
• Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping
• Pinball boosting of regression quantiles
• Explainable subgradient tree boosting for prescriptive analytics in operations management
• Tweedie gradient boosting for extremely unbalanced zero-inflated data
• Estimation and inference of treatment effects with \(L_2\)-boosting in high-dimensional settings
• Insurance Premium Prediction via Gradient Tree-Boosted Tweedie Compound Poisson Models
• Infinitesimal gradient boosting

Uses Software

• AdaBoost.MH

This page was built for publication: Boosting with early stopping: convergence and consistency

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