Boosting with early stopping: Convergence and consistency

Details Boosting with early stopping: Convergence and consistency Boosting with early stopping: Convergence and consistency

2005-08-16

arxiv.org/abs/math/0508276v1

Annals of Statistics 2005, Vol. 33, No. 4, 1538-1579

Mathematics

Statistics Theory

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

Scientific paper

10.1214/009053605000000255

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

Affiliated with

Also associated with

No associations

Rating

Boosting with early stopping: Convergence and consistency does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boosting with early stopping: Convergence and consistency, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boosting with early stopping: Convergence and consistency will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-131474