Boosting with structural sparsity

John C. Duchi, Yoram Singer

Abstract

We derive generalizations of AdaBoost and related gradient-based coordinate descent methods that incorporate sparsity-promoting penalties for the norm of the predictor that is being learned. The end result is a family of coordinate descent algorithms that integrate forward feature induction and back-pruning through regularization and give an automatic stopping criterion for feature induction. We study penalties based on the l1, l2, and l∞ norms of the predictor and introduce mixed-norm penalties that build upon the initial penalties. The mixed-norm regularizers facilitate structural sparsity in parameter space, which is a useful property in multiclass prediction and other related tasks. We report empirical results that demonstrate the power of our approach in building accurate and structurally sparse models.
BibTeX
@inproceedings{duchi2009boosting,
  author = {John C. Duchi and Yoram Singer},
  title = {{Boosting with structural sparsity}},
  booktitle = {International Conference on Machine Learning},
  year = {2009},
  doi = {10.1145/1553374.1553412},
}

Loading related content...

Figure