Sparse Classification and Phase Transitions: A Discrete Optimization Perspective
Preprint
Abstract
In this paper, we formulate the sparse classification problem of $n$ samples with $p$ features as a binary convex optimization problem and propose a cutting-plane 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 exhibits a phase transition phenomenon: there exists a $n_0$ for which for $n 6 \pi^2 \left(2 + \sigma^2\right) k \log(p-k)$. In contrast, while Lasso accurately detects all the true features, it persistently returns incorrect features, even as the number of observations increases. Finally, we apply our method on classifying the type of cancer using gene expression data from the Cancer Genome Atlas Research Network with $n=1,145$ lung cancer patients and $p=14,858$ genes.Sparse classification using logistic regression returns a classifier based on $50$ genes versus $171$ for Lasso and using SVM $30$ genes versus $172$ for Lasso with similar predictive accuracy.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- Sparse learning via Boolean relaxationsMathematical Programming, 2015
- Dual coordinate descent methods for logistic regression and maximum entropy modelsMachine Learning, 2010
- Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement MatricesIEEE Transactions on Information Theory, 2010
- Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy SettingIEEE Transactions on Information Theory, 2009
- Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processingPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- A Fast Dual Algorithm for Kernel Logistic RegressionMachine Learning, 2005
- Gene Selection for Cancer Classification using Support Vector MachinesMachine Learning, 2002
- Solving mixed integer nonlinear programs by outer approximationMathematical Programming, 1994
- An outer-approximation algorithm for a class of mixed-integer nonlinear programsMathematical Programming, 1986