Boosting classifiers with tightened L0-relaxation penalties

Noam Goldberg, Jonathan Eckstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


We propose a novel boosting algorithm which improves on current algorithms for weighted voting classification by striking a better balance between classification accuracy and the sparsity of the weight vector. In order to justify our optimization formulations, we first consider a novel integer linear program as a model for sparse classifier selection, generalizing the minimum disagreement half-space problem whose complexity has been investigated in computational learning theory. Specifically, our mixed integer problem is that of finding a separating hyper-plane with minimum empirical error subject to an L0-norm penalty. We note that common "soft margin" linear programming formulations for robust classification are equivalent to the continuous relaxation of our formulation. Since the initial continuous relaxation is weak, we suggest a tighter relaxation, using novel cutting planes, to better approximate the integer solution. To solve this relaxation, we propose a new boosting algorithm based on linear programming with dynamic generation of variables and constraints. We demonstrate the classification performance of our proposed algorithm with experimental results, and justify our selection of parameters using a minimum description length, compression interpretation of learning.

Original languageEnglish (US)
Title of host publicationICML 2010 - Proceedings, 27th International Conference on Machine Learning
Number of pages8
StatePublished - 2010
Event27th International Conference on Machine Learning, ICML 2010 - Haifa, Israel
Duration: Jun 21 2010Jun 25 2010

Publication series

NameICML 2010 - Proceedings, 27th International Conference on Machine Learning


Other27th International Conference on Machine Learning, ICML 2010

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Education


Dive into the research topics of 'Boosting classifiers with tightened L0-relaxation penalties'. Together they form a unique fingerprint.

Cite this