Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives

Understand

We consider a discrete optimization formulation for learning sparse classifiers, where the outcome depends upon a linear combination of a small subset of features.

• Recent work has shown that mixed integer programming (MIP) can be used to solve (to optimality) $\ell_0$-regularized regression problems at scales much larger than what was conventionally considered possible.
• Despite their usefulness, MIP-based global optimization approaches are significantly slower compared to the relatively mature algorithms for $\ell_1$-regularization and heuristics for nonconvex regularized problems.
• We aim to bridge this gap in computation times by developing new MIP-based algorithms for $\ell_0$-regularized classification.