# Sparse Classification: a scalable discrete optimization perspective

arXiv: https://arxiv.org/abs/1710.01352 · HTML: https://mlsanity.com/paper/1710.01352/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2017.

## Built on by (most cited first, 18 of 18)

- [Finding Neurons in a Haystack: Case Studies with Sparse Probing](https://mlsanity.com/paper/2305.01610/) (2023)
- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [Variable Selection for Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.07415/) (2023)
- ["Oh LLM, I'm Asking Thee, Please Give Me a Decision Tree": Zero-Shot Decision Tree Induction and Embedding with Large Language Models](https://mlsanity.com/paper/2409.18594/) (2024)
- [Cost-Sensitive Best Subset Selection for Logistic Regression: A Mixed-Integer Conic Optimization Perspective](https://mlsanity.com/paper/2310.05464/) (2023)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Patient Outcome Predictions Improve Operations at a Large Hospital Network](https://mlsanity.com/paper/2305.15629/) (2023)
- [In Search of Grandmother Cells: Tracing Interpretable Neurons in Tabular Representations](https://mlsanity.com/paper/2601.03657/) (2026)
- [Feature subset selection for kernel SVM classification via mixed-integer optimization](https://mlsanity.com/paper/2205.14325/) (2022)
- [Path Signatures for Seizure Forecasting](https://mlsanity.com/paper/2308.09312/) (2023)
- [Automated Model Selection for Generalized Linear Models](https://mlsanity.com/paper/2404.16560/) (2024)
- [A GPU-Accelerated Bi-linear ADMM Algorithm for Distributed Sparse Machine Learning](https://mlsanity.com/paper/2405.16267/) (2024)
- [Variable Selection Methods for Multivariate, Functional, and Complex Biomedical Data in the AI Age](https://mlsanity.com/paper/2501.06868/) (2025)
- [El0ps: An Exact L0-regularized Problems Solver](https://mlsanity.com/paper/2506.06373/) (2025)
- [MOSS: Multi-Objective Optimization for Stable Rule Sets](https://mlsanity.com/paper/2506.08030/) (2025)
- [Choosing the Right Regularizer for Applied ML: Simulation Benchmarks of Popular Scikit-learn Regularization Frameworks](https://mlsanity.com/paper/2604.03541/) (2026)
- [ConceptTracer: Interactive Analysis of Concept Saliency and Selectivity in Neural Representations](https://mlsanity.com/paper/2604.07019/) (2026)
- [Variable Selection for Feature-Based Newsvendor](https://mlsanity.com/paper/2609.01544/) (2026)

## Abstract (arXiv)

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,000s within minutes. On synthetic data our algorithm achieves perfect support recovery in the large sample regime. Namely, there exists a n0 such that the algorithm takes a long time to find the optimal solution and does not recover the correct support for n<n0, while for ngeqslant n0, the algorithm quickly detects all the true features, and does not return any false features. In contrast, while Lasso accurately detects all the true features, it persistently returns incorrect features, even as the number of observations increases. Consequently, on numerous real-world experiments, our outer-approximation algorithms returns sparser classifiers while achieving similar predictive accuracy as Lasso. To support our observations, we analyze conditions on the sample size needed to ensure full support recovery in classification. Under some assumptions on the data generating process, we prove that information-theoretic limitations impose n0 < C left(2 + σ2right) k log(p-k), for some constant C>0.