Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives

MaRDI QIDQ6333079arXivFDO

Authors Antoine Dedieu, Hussein Hazimeh, Rahul Mazumder

Publication date 17 January 2020

Published in arXiv

Has companion code repository https://github.com/hazimehh/L0Learn

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

arXiv classification

cs.LGmath.OCstat.COstat.ML

Abstract: 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) $el{l}_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 $el{l}_1$-regularization and heuristics for nonconvex regularized problems. We aim to bridge this gap in computation times by developing new MIP-based algorithms for $el{l}_0$-regularized classification. We propose two classes of scalable algorithms: an exact algorithm that can handle $papprox50,000$ features in a few minutes, and approximate algorithms that can address instances with $papprox10^6$ in times comparable to the fast $el{l}_1$-based algorithms. Our exact algorithm is based on the novel idea of extsl{integrality generation}, which solves the original problem (with $p$ binary variables) via a sequence of mixed integer programs that involve a small number of binary variables. Our approximate algorithms are based on coordinate descent and local combinatorial search. In addition, we present new estimation error bounds for a class of $el{l}_0$-regularized estimators. Experiments on real and synthetic data demonstrate that our approach leads to models with considerably improved statistical performance (especially, variable selection) when compared to competing methods.

This page was built for publication: Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333079)