Boosting with early stopping: Convergence and consistency

By Tong Zhang, Bin Yu. 2005

499 citations recorded by the source corpus.

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 E → 0 step-size becomes an L 1 -margin maximizer when left to run to convergence.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/b0816b4f1fdf1ebc324663f66485e05d58cbd1a7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistics and Probability

Citations in the corpus

Small Area Estimation of the Homeless in Los Angeles: An Application of Cost-Sensitive stochastic Gradient Boosting (2010, methodology): “Beyond the minimum cross-validation error iterations, the models overfit the data (Zhang and Yu, 2005).”
Field-aware Factorization Machines for CTR Prediction (2016, background): “Early stopping, which terminates the training process before reaching the best result on training data, can be used to avoid over-fitting for many machine learning problems [17, 18, 19].”
Early stopping for non-parametric regression: An optimal data-dependent stopping rule (2011, unknown): “Early stopping has also been widely used in neural networks (e.g., [28]), in which stochastic gradient descent is used to estimate the network parameters.”
On Early Stopping in Gradient Descent Learning (2007, methodology): “The gradient descent view on boosting triggers a series of studies on consistency and regularization in boosting [e.g. Jiang 2004; Breiman 2004; Lugosi and Vayatis 2004; Zhang and Yu 2003], going beyond margin analysis in early studies [Schapire, Freund, Bartlett, and Lee 1998].”
Margin-based Ranking and an Equivalence between AdaBoost and RankBoost (2009, methodology): “Now we move onto the convergence proofs, which were loosely inspired by the analysis of Zhang and Yu (2005).”
Generalizing from a Few Examples (2019, background): “ in machine learning, which helps to reduce estimation error and get better learning performance [78]. Classical examples include Tikhonov regularizer [48], lasso regularizer [115] and early stopping [140]. However, these simple regularization techniques, cannot address the problem of FSL. The reaso”
Robust early-learning: Hindering the memorization of noisy labels (2021, methodology): “It was used in supervised learning early (Prechelt, 1998; Caruana et al., 2001; Zhang et al., 2005; Yao et al., 2007).”
Machine Learning Advances for Time Series Forecasting (2020, background): “See, for instance, Jiang (2004), Lugosi and Vayatis (2004), Bartlett and Traskin (2007), Zhang and Yu (2005), Bühlmann (2006), and Bühlmann (2002).”
Convolutional Neural Networks for Classification of Alzheimer's Disease: Overview and Reproducible Evaluation (2019, background): “ct the model parameters corresponding to the lowest validation error rather than the last updated parameters. Various other stopping criterions have been proposed ( Prechelt, 2012; Yao et al., 2007; Zhang and Yu, 2005). 7 eMethod 3. M RI p r e p r oc e s s i n g A proper image preprocessing procedur”
Selecting Instrumental Variables in a Data Rich Environment (2009, background): “Zhang and Yu (2005) and Buhlmann (2006) showed that boosting will consistently estimate the true conditional mean of x2.”
Estimation Stability With Cross-Validation (ESCV) (2013, methodology): “In the case of the Lasso, the computation quickly gets expensive with larger data sets (Efron et al. 2004; Mairal and Yu 2012).”
Functional Gradient Boosting based on Residual Network Perception (2018, methodology): “In this paper, we rely on early stopping (Zhang et al., 2005) and some restriction on optimization methods for solving the problem.”
Explaining AdaBoost (2013, result): “” In this sense, the algorithm is said to be universally consistent, a property that was proved by Bartlett and Traskin [1] following the work of many others [3, 5, 14, 19, 21, 38, 39].”
Convexity, Classification, and Risk Bounds (2006, methodology): “Regarding the numerical optimization to determine ˆ f , Zhang and Yu (2005) gave novel bounds on the convergence rate for generic forward stage-wise additive modeling (see also Zhang 2003).”
Boosting Algorithms: Regularization, Prediction and Model Fitting. Rejoinder. (2007, background): “Later, Zhang and Yu [92] generalized the results for a functional gradient descent with an additional relaxation scheme, and their theory covers also more general loss functions than the exponential loss in AdaBoost.”