Speed and Sparsity of Regularized Boosting

Yongxin Xi, Zhen Xiang, Peter Ramadge, Robert Schapire
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:615-622, 2009.

Abstract

Boosting algorithms with l1 regularization are of interest because l1 regularization leads to sparser composite classifiers. Moreover, Rosset et al. have shown that for separable data, standard lp regularized loss minimization results in a margin maximizing classifier in the limit as regularization is relaxed. For the case p=1, we extend these results by obtaining explicit convergence bounds on the regularization required to yield a margin within prescribed accuracy of the maximum achievable margin. We derive similar rates of convergence for the epsilon AdaBoost algorithm, in the process providing a new proof that epsilon AdaBoost is margin maximizing as epsilon converges to 0. Because both of these known algorithms are computationally expensive, we introduce a new hybrid algorithm, AdaBoost+L1, that combines the virtues of AdaBoost with the sparsity of l1 regularization in a computationally efficient fashion. We prove that the algorithm is margin maximizing and empirically examine its performance on five datasets.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-xi09a, title = {Speed and Sparsity of Regularized Boosting}, author = {Yongxin Xi and Zhen Xiang and Peter Ramadge and Robert Schapire}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {615--622}, year = {2009}, editor = {David van Dyk and Max Welling}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/xi09a/xi09a.pdf}, url = {http://proceedings.mlr.press/v5/xi09a.html}, abstract = {Boosting algorithms with l1 regularization are of interest because l1 regularization leads to sparser composite classifiers. Moreover, Rosset et al. have shown that for separable data, standard lp regularized loss minimization results in a margin maximizing classifier in the limit as regularization is relaxed. For the case p=1, we extend these results by obtaining explicit convergence bounds on the regularization required to yield a margin within prescribed accuracy of the maximum achievable margin. We derive similar rates of convergence for the epsilon AdaBoost algorithm, in the process providing a new proof that epsilon AdaBoost is margin maximizing as epsilon converges to 0. Because both of these known algorithms are computationally expensive, we introduce a new hybrid algorithm, AdaBoost+L1, that combines the virtues of AdaBoost with the sparsity of l1 regularization in a computationally efficient fashion. We prove that the algorithm is margin maximizing and empirically examine its performance on five datasets.} }
Endnote
%0 Conference Paper %T Speed and Sparsity of Regularized Boosting %A Yongxin Xi %A Zhen Xiang %A Peter Ramadge %A Robert Schapire %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-xi09a %I PMLR %J Proceedings of Machine Learning Research %P 615--622 %U http://proceedings.mlr.press %V 5 %W PMLR %X Boosting algorithms with l1 regularization are of interest because l1 regularization leads to sparser composite classifiers. Moreover, Rosset et al. have shown that for separable data, standard lp regularized loss minimization results in a margin maximizing classifier in the limit as regularization is relaxed. For the case p=1, we extend these results by obtaining explicit convergence bounds on the regularization required to yield a margin within prescribed accuracy of the maximum achievable margin. We derive similar rates of convergence for the epsilon AdaBoost algorithm, in the process providing a new proof that epsilon AdaBoost is margin maximizing as epsilon converges to 0. Because both of these known algorithms are computationally expensive, we introduce a new hybrid algorithm, AdaBoost+L1, that combines the virtues of AdaBoost with the sparsity of l1 regularization in a computationally efficient fashion. We prove that the algorithm is margin maximizing and empirically examine its performance on five datasets.
RIS
TY - CPAPER TI - Speed and Sparsity of Regularized Boosting AU - Yongxin Xi AU - Zhen Xiang AU - Peter Ramadge AU - Robert Schapire BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-xi09a PB - PMLR SP - 615 DP - PMLR EP - 622 L1 - http://proceedings.mlr.press/v5/xi09a/xi09a.pdf UR - http://proceedings.mlr.press/v5/xi09a.html AB - Boosting algorithms with l1 regularization are of interest because l1 regularization leads to sparser composite classifiers. Moreover, Rosset et al. have shown that for separable data, standard lp regularized loss minimization results in a margin maximizing classifier in the limit as regularization is relaxed. For the case p=1, we extend these results by obtaining explicit convergence bounds on the regularization required to yield a margin within prescribed accuracy of the maximum achievable margin. We derive similar rates of convergence for the epsilon AdaBoost algorithm, in the process providing a new proof that epsilon AdaBoost is margin maximizing as epsilon converges to 0. Because both of these known algorithms are computationally expensive, we introduce a new hybrid algorithm, AdaBoost+L1, that combines the virtues of AdaBoost with the sparsity of l1 regularization in a computationally efficient fashion. We prove that the algorithm is margin maximizing and empirically examine its performance on five datasets. ER -
APA
Xi, Y., Xiang, Z., Ramadge, P. & Schapire, R.. (2009). Speed and Sparsity of Regularized Boosting. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:615-622

Related Material