The rate of convergence of AdaBoost

MaRDI QIDQ2933884zbMATH OpenFDO

Authors Indraneel Mukherjee, Cynthia Rudin, Robert E. Schapire

Publication date 8 December 2014

Full work available at URL https://arxiv.org/abs/1106.6024, http://jmlr.csail.mit.edu/papers/v14/mukherjee13b.html

zbMATH Keywords

AdaBoostconvergence ratecoordinate descentoptimization

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: The AdaBoost algorithm was designed to combine many "weak" hypotheses that perform slightly better than random guessing into a "strong" hypothesis that has very low error. We study the rate at which AdaBoost iteratively converges to the minimum of the "exponential loss." Unlike previous work, our proofs do not require a weak-learning assumption, nor do they require that minimizers of the exponential loss are finite. Our first result shows that at iteration $t$, the exponential loss of AdaBoost's computed parameter vector will be at most $epsilon$ more than that of any parameter vector of $el{l}_1$-norm bounded by $B$ in a number of rounds that is at most a polynomial in $B$ and $1/epsilon$. We also provide lower bounds showing that a polynomial dependence on these parameters is necessary. Our second result is that within $C/epsilon$ iterations, AdaBoost achieves a value of the exponential loss that is at most $epsilon$ more than the best possible value, where $C$ depends on the dataset. We show that this dependence of the rate on $epsilon$ is optimal up to constant factors, i.e., at least $Omega(1/epsilon)$ rounds are necessary to achieve within $epsilon$ of the optimal exponential loss.

Recommendations

• scientific article; zbMATH DE number 5251641
• The dynamics of adaboost: cyclic behavior and convergence of margins
• scientific article; zbMATH DE number 2089372
• A primal-dual convergence analysis of boosting
• Logistic regression, AdaBoost and Bregman distances

Cited in

(12)

• Process consistency for AdaBoost.
• AdaBoost and robust one-bit compressed sensing
• A precise high-dimensional asymptotic theory for boosting and minimum-\(\ell_1\)-norm interpolated classifiers
• The dynamics of adaboost: cyclic behavior and convergence of margins
• AdaBoost is consistent
• scientific article; zbMATH DE number 2044160 (Why is no real title available?)
• Randomized Gradient Boosting Machine
• Toward Efficient Ensemble Learning with Structure Constraints: Convergent Algorithms and Applications
• A primal-dual convergence analysis of boosting
• scientific article; zbMATH DE number 5251641 (Why is no real title available?)
• Fully corrective gradient boosting with squared hinge: fast learning rates and early stopping
• Kernel-based L₂-boosting with structure constraints

This page was built for publication: The rate of convergence of AdaBoost

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