Sparse weighted voting classifier selection and its linear programming relaxations

By Noam Goldberg, Jonathan Eckstein. 2012

13 citations recorded by the source corpus.

We consider the problem of minimizing the number of misclassifications of a weighted voting classifier, plus a penalty proportional to the number of nonzero weights. We first prove that its optimum is at least as hard to approximate as the minimum disagreement halfspace problem for a wide range of penalty parameter values. After formulating the problem as a mixed integer program (MIP), we show that common ''soft margin'' linear programming (LP) formulations for constructing weighted voting classsifiers are equivalent to an LP relaxation of our formulation. We show that this relaxation is very weak, with a potentially exponential integrality gap. However, we also show that augmenting the relaxation with certain valid inequalities tightens it considerably, yielding a linear upper bound on the gap for all values of the penalty parameter that exceed a reasonable threshold. Unlike earlier techniques proposed for similar problems (Bradley and Mangasarian (1998) [4], Weston et al. (2003) [14]), our approach provides bounds on the optimal solution value.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Supersparse linear integer models for optimized medical scoring systems (2015, background): “One unique benefit in minimizing an approximation-free objective function over a finite set of discrete coefficients is that the free parameters in the objective of (2) have special properties.”
Methods and Models for Interpretable Linear Classification (2014, methodology): “Recent progress in commercial MIP software has made it possible to solve exponentially larger problems [13, 12], and ushered in new MIP classification models that involve feature selection [42, 45, 46, 84], or the creation of a reserved-judgement region [22, 21].”
Supersparse Linear Integer Models for Interpretable Classification (2013, methodology): “Goldberg and Eckstein [27] present a mixed-integer optimization formulation similar to the one we consider in this paper, but they do not advocate solving it.”
IPBoost - Non-Convex Boosting via Integer Programming (2020, methodology): “Previous approaches in the context of LP-based boosting have promoted sparsity by means of cutting planes, see, e.g., (Goldberg & Eckstein, 2010; 2012; Eckstein & Goldberg, 2012).”