# Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jan 2020.

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

- [FasterRisk: Fast and Accurate Interpretable Risk Scores](https://mlsanity.com/paper/2210.05846/) (2022)
- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [Forgetting, Ignorance or Myopia: Revisiting Key Challenges in Online Continual Learning](https://mlsanity.com/paper/2409.19245/) (2024)
- [Foundations of Top-k Decoding For Language Models](https://mlsanity.com/paper/2505.19371/) (2025)
- [Interpretable Generalized Additive Models for Datasets with Missing Values](https://mlsanity.com/paper/2412.02646/) (2024)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [A New Branch-and-Bound Pruning Framework for ℓ0-Regularized Problems](https://mlsanity.com/paper/2406.03504/) (2024)
- [Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique](https://mlsanity.com/paper/2308.00251/) (2023)
- [Cost-Sensitive Best Subset Selection for Logistic Regression: A Mixed-Integer Conic Optimization Perspective](https://mlsanity.com/paper/2310.05464/) (2023)
- [Scalable Subset Selection in Linear Mixed Models](https://mlsanity.com/paper/2506.20425/) (2025)
- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [Group selection and shrinkage: Structured sparsity for semiparametric additive models](https://mlsanity.com/paper/2105.12081/) (2021)
- [Feature subset selection for kernel SVM classification via mixed-integer optimization](https://mlsanity.com/paper/2205.14325/) (2022)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [Joint Score-Threshold Optimization for Interpretable Risk Assessment](https://mlsanity.com/paper/2510.21934/) (2025)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [Learning Locally Interpretable Rule Ensemble](https://mlsanity.com/paper/2306.11481/) (2023)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [Prediction Models That Learn to Avoid Missing Values](https://mlsanity.com/paper/2505.03393/) (2025)
- [A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions](https://mlsanity.com/paper/2505.03899/) (2025)
- [A Generic Branch-and-Bound Algorithm for ℓ0-Penalized Problems with Supplementary Material](https://mlsanity.com/paper/2506.03974/) (2025)
- [El0ps: An Exact L0-regularized Problems Solver](https://mlsanity.com/paper/2506.06373/) (2025)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

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) ℓ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 ℓ1-regularization and heuristics for nonconvex regularized problems. We aim to bridge this gap in computation times by developing new MIP-based algorithms for ℓ0-regularized classification. We propose two classes of scalable algorithms: an exact algorithm that can handle p≈ 50,000 features in a few minutes, and approximate algorithms that can address instances with p≈ 106 in times comparable to the fast ℓ1-based algorithms. Our exact algorithm is based on the novel idea of textslintegrality 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 ℓ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.