Boosting with early stopping: convergence and consistency
From MaRDI portal
Publication:2583412
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.
Recommendations
Cites work
- 10.1162/153244303321897690
- 10.1162/1532443041424300
- 10.1162/1532443041424319
- 10.1162/153244304773936108
- A decision-theoretic generalization of on-line learning and an application to boosting
- A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
- Additive logistic regression: a statistical view of boosting. (With discussion and a rejoinder by the authors)
- Arcing classifiers. (With discussion)
- Boosting the margin: a new explanation for the effectiveness of voting methods
- Boosting With theL2Loss
- Complexities of convex combinations and bounding the generalization error in classification
- Convexity, Classification, and Risk Bounds
- Efficient agnostic learning of neural networks with bounded fan-in
- Empirical margin distributions and bounding the generalization error of combined classifiers
- Greedy function approximation: A gradient boosting machine.
- scientific article; zbMATH DE number 2089354 (Why is no real title available?)
- scientific article; zbMATH DE number 1804107 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 47282 (Why is no real title available?)
- scientific article; zbMATH DE number 1332320 (Why is no real title available?)
- scientific article; zbMATH DE number 1869443 (Why is no real title available?)
- Improved boosting algorithms using confidence-rated predictions
- Local Rademacher complexities
- Logistic regression, AdaBoost and Bregman distances
- Matching pursuits with time-frequency dictionaries
- On the Bayes-risk consistency of regularized boosting methods.
- Population theory for boosting ensembles.
- Process consistency for AdaBoost.
- Sequential greedy approximation for certain convex optimization problems
- Statistical behavior and consistency of classification methods based on convex risk minimization.
- The elements of statistical learning. Data mining, inference, and prediction
- Universal approximation bounds for superpositions of a sigmoidal function
- Weak convergence and empirical processes. With applications to statistics
Cited in
(92)- A stochastic approximation view of boosting
- On boosting kernel regression
- Bi-cross-validation for factor analysis
- Deformation of log-likelihood loss function for multiclass boosting
- Population theory for boosting ensembles.
- Random classification noise defeats all convex potential boosters
- Variational networks: an optimal control approach to early stopping variational methods for image restoration
- Boosted nonparametric hazards with time-dependent covariates
- SVM-boosting based on Markov resampling: theory and algorithm
- Adaptive step-length selection in gradient boosting for Gaussian location and scale models
- AdaBoost and robust one-bit compressed sensing
- A new accelerated proximal boosting machine with convergence rate \(O(1/t^2)\)
- Coupling the reduced-order model and the generative model for an importance sampling estimator
- Interpreting initial offset boosting via reconstitution in integral domain
- Mathematical foundations of machine learning. Abstracts from the workshop held March 21--27, 2021 (hybrid meeting)
- A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
- Aggregation of estimators and stochastic optimization
- Supervised projection approach for boosting classifiers
- Optimal rates for spectral algorithms with least-squares regression over Hilbert spaces
- Fast and strong convergence of online learning algorithms
- Double machine learning with gradient boosting and its application to the Big N audit quality effect
- Accelerated gradient boosting
- Early stopping in \(L_{2}\)Boosting
- Analysis of boosting algorithms using the smooth margin function
- Boosting for high-dimensional linear models
- Complexities of convex combinations and bounding the generalization error in classification
- Consistency and generalization bounds for maximum entropy density estimation
- Early stopping and non-parametric regression: an optimal data-dependent stopping rule
- scientific article; zbMATH DE number 2089370 (Why is no real title available?)
- scientific article; zbMATH DE number 2089371 (Why is no real title available?)
- Boosting as a regularized path to a maximum margin classifier
- Nonparametric stochastic approximation with large step-sizes
- AdaBoost is consistent
- Boosting algorithms: regularization, prediction and model fitting
- Fully corrective boosting with arbitrary loss and regularization
- The implicit bias of gradient descent on separable data
- 10.1162/jmlr.2003.3.4-5.863
- Boosting in the presence of outliers: adaptive classification with nonconvex loss functions
- Randomized Gradient Boosting Machine
- Dimension reduction boosting
- Analyzing the discrepancy principle for kernelized spectral filter learning algorithms
- Tweedie gradient boosting for extremely unbalanced zero-inflated data
- Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications
- scientific article; zbMATH DE number 7306853 (Why is no real title available?)
- Random gradient boosting for predicting conditional quantiles
- Convergence and Consistency of Regularized Boosting With Weakly Dependent Observations
- scientific article; zbMATH DE number 5251641 (Why is no real title available?)
- A boosting inspired personalized threshold method for sepsis screening
- Optimization by Gradient Boosting
- Implicit regularization with strongly convex bias: Stability and acceleration
- AdaBoost Semiparametric Model Averaging Prediction for Multiple Categories
- Deep learning: a statistical viewpoint
- Stochastic boosting algorithms
- Stochastic boosting algorithms
- Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping
- Explainable subgradient tree boosting for prescriptive analytics in operations management
- Infinitesimal gradient boosting
- Deep learning for natural language processing: a survey
- Small area estimation of the homeless in Los Angeles: an application of cost-sensitive stochastic gradient boosting
- Estimation and inference of treatment effects with L₂-boosting in high-dimensional settings
- Unbiased Boosting Estimation for Censored Survival Data
- Survival ensembles by the sum of pairwise differences with application to lung cancer microarray studies
- Early stopping for L^2 -boosting in high-dimensional linear models
- A boosting method for maximization of the area under the ROC curve
- A large-sample theory for infinitesimal gradient boosting
- Tree-based boosting with functional data
- Fast iterative regularization by reusing data
- Use of majority votes in statistical learning
- The vanishing learning rate asymptotic for linear L^2-boosting
- Insurance Premium Prediction via Gradient Tree-Boosted Tweedie Compound Poisson Models
- Pinball boosting of regression quantiles
- A new perspective on boosting in linear regression via subgradient optimization and relatives
- Consistency of the oblique decision tree and its boosting and random forest
- A tree-based varying coefficient model
- Additive tree latent variable models with applications to insurance loss prediction
- Improving randomized controlled trial analysis via data-adaptive borrowing
- SID-NET: machine learning based system identification framework for rigid and flexible multibody dynamics
- High-dimensional L₂-Boosting: rate of convergence
- Kullback-Leibler-based discrete failure time models for integration of published prediction models with new time-to-event dataset
- Variable Selection and Estimation for Misclassified Binary Responses and Multivariate Error-Prone Predictors
- Minimum discrepancy principle strategy for choosing k in k-NN regression
- Loss-guided stability selection
- Back-testing credit risk parameters on low default portfolios: a simple Bayesian transfer learning approach with an application to sovereign risk‖
- Ensemble projection pursuit for general nonparametric regression
- Iterative regularization in classification via hinge loss diagonal descent
- Synchronizing pretrained kernel regressors with applications to American option pricing
- Nonparametric efficient estimation of marginal structural models with continuous time-varying treatments
- Kernel-based L₂-boosting with structure constraints
- Decentralized EM algorithm for Gaussian mixtures under data heterogeneity and partial labeling
- Explainable boosting machine for predicting claim severity and frequency in car insurance
- Regularization in statistics
- Rejoinder: One-step sparse estimates in nonconcave penalized likelihood models
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)
