Sparse Boosting

Abstract

We propose Sparse Boosting (the Sparse L 2 Boost algorithm), a variant on boosting with the squared error loss. Sparse L 2 Boost yields sparser solutions than the previously proposed L 2 Boosting by minimizing some penalized L 2 -loss functions, the FPE model selection criteria, through small-step gradient descent. Although boosting may give already relatively sparse solutions, for example corresponding to the soft-thresholding estimator in orthogonal linear models, there is sometimes a desire for more sparseness to increase prediction accuracy and ability for better variable selection: such goals can be achieved with Sparse L 2 Boost. We prove an equivalence of Sparse L 2 Boost to Breiman's nonnegative garrote estimator for orthogonal linear models and demonstrate the generic nature of Sparse L 2 Boost for nonparametric interaction modeling. For an automatic selection of the tuning parameter in Sparse L 2 Boost we propose to employ the gMDL model selection criterion which can also be used for early stopping of L 2 Boosting. Consequently, we can select between Sparse L 2 Boost and L 2 Boosting by comparing their gMDL scores.