Sparse classification: a scalable discrete optimization perspective

摘要

We formulate the sparse classification problem of n samples with p features as a binary convex optimization problem and propose a outer-approximation algorithm to solve it exactly. For sparse logistic regression and sparse SVM, our algorithm finds optimal solutions for n and p in the 10,000 s within minutes. On synthetic data our algorithm achieves perfect support recovery in the large sample regime. Namely, there exists an \(n_0\) such that the algorithm takes a long time to find an optimal solution and does not recover the correct support for \(n0\).