140. Strict cardinality control in feature selection for linear Support Vectors: a scalable conic decomposition approach
Invited abstract in session MC-13: Cardinality control in optimization problems for Data Science, stream Sparsity guarantee and cardinality-constrained (MI)NLPs.
Monday, 14:00-16:00Room: B100/6009
Authors (first author is the speaker)
| 1. | Laura Palagi
|
| Department of Computer, Control, and Management Engineering A. Ruberti, Sapienza University of Rome | |
| 2. | Immanuel Bomze
|
| Dept. of Statistics and OR, University of Vienna | |
| 3. | Federico D’Onofrio
|
| IASI, CNR | |
| 4. | Bo Peng
|
| University of Vienna |
Abstract
In this talk, we present the embedded feature selection problem in linear Support Vector Machines (SVMs), in which an explicit cardinality constraint is employed. These models try to achieve fairness, transparency and explainability in AI applications, ranging from Math. Finance/Economics to social and life sciences.
The problem is NP-hard due to the presence of the cardinality constraint, even though the original linear SVM amounts to a problem solvable in polynomial time. To handle the hard problem, we introduce two mixed-integer formulations for which novel semidefinite relaxations are proposed. Exploiting the sparsity pattern of the relaxations, we decompose the problems and obtain equivalent relaxations in a much smaller cone, making the conic approaches scalable. We propose heuristics using the information on the optimal solution of the relaxations. Moreover, an exact procedure is proposed by solving a sequence of mixed-integer decomposed semidefinite optimization problems. Numerical results on classical benchmarking datasets are reported, showing the efficiency and effectiveness of our approach.
Keywords
- Nonlinear mixed integer optimization
- Global optimization
- Optimization for learning and data analysis
Status: accepted
Back to the list of papers