Speed and sparsity of regularized boosting

Boosting algorithms with l₁-regularization are of interest because l₁ regularization leads to sparser composite classifiers. Moreover, Rosset et al. have shown that for separable data, standard l _p- 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 ε-AdaBoost algorithm, in the process providing a new proof that ε-AdaBoost is margin maximizing as ε converges to 0. Because both of these known algorithms are computationally expensive, we introduce a new hybrid algorithm, AdaBoost+L₁, that combines the virtues of AdaBoost with the sparsity of l₁- regularization in a computationally efficient fashion. We prove that the algorithm is margin maximizing and empirically examine its performance on five datasets.