Optimization Online


Tightened L0 Relaxation Penalties for Classification

Noam Goldberg (noamgold***at***tx.technion.ac.il)
Jonathan Eckstein (jeckstei***at***rci.rutgers.edu)

Abstract: In optimization-based classification model selection, for example when using linear programming formulations, a standard approach is to penalize the L1 norm of some linear functional in order to select sparse models. Instead, we propose a novel integer linear program for sparse classifier selection, generalizing the minimum disagreement hyperplane problem whose complexity has been investigated in computational learning theory. Specifically, our mixed-integer problem is that of finding a separating hyperplane with minimum empirical error subject to an L0 penalty. We show that common "soft margin" linear programming formulations for robust classification are equivalent to a continuous relaxation of our model. Since the initial continuous relaxation is weak, we suggest a tighter relaxation, using novel cutting planes, to better approximate the integer solution. We describe a boosting algorithm, based on linear programming with dynamic generation of cuts and columns, that solves our relaxation. 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.

Keywords: Classification, cutting planes, linear separation, Boosting, weighted voting classifiers, sparsity, Minimum Description Length

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: RUTCOR Research Report #23-2009, Rutgers Center for Operations Research, 640 Bartholomew Rd., Piscataway NJ 08854, USA, October 2009

Download: [PDF]

Entry Submitted: 11/08/2009
Entry Accepted: 11/08/2009
Entry Last Modified: 11/08/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society