# Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 89 references that are in the map.
- First posted on arXiv 14 Apr 2021.

## Builds on (most cited first, 16 of 16)

- [Ups and Downs: Modeling the Visual Evolution of Fashion Trends with One-Class Collaborative Filtering](https://mlsanity.com/paper/1602.01585/) (2016)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives](https://mlsanity.com/paper/2001.06471/) (2020)
- [Integer Programming for Learning Directed Acyclic Graphs from Continuous Data](https://mlsanity.com/paper/1904.10574/) (2019)
- [Subset Selection with Shrinkage: Sparse Linear Modeling when the SNR is low](https://mlsanity.com/paper/1708.03288/) (2017)
- [Minimax Optimal Rates of Estimation in High Dimensional Additive Models: Universal Phase Transition](https://mlsanity.com/paper/1503.02817/) (2015)
- [Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection](https://mlsanity.com/paper/1510.06083/) (2015)
- [Sparse and Smooth Signal Estimation: Convexification of L0 Formulations](https://mlsanity.com/paper/1811.02655/) (2018)
- [Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators](https://mlsanity.com/paper/1503.03188/) (2015)
- [Estimating the error variance in a high-dimensional linear model](https://mlsanity.com/paper/1712.02412/) (2017)
- [Using L1-relaxation and integer programming to obtain dual bounds for sparse PCA](https://mlsanity.com/paper/1810.09062/) (2018)
- [The Discrete Dantzig Selector: Estimating Sparse Linear Models via Mixed Integer Linear Optimization](https://mlsanity.com/paper/1508.01922/) (2015)
- [Learning Hierarchical Interactions at Scale: A Convex Optimization Approach](https://mlsanity.com/paper/1902.01542/) (2019)

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

- [OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization](https://mlsanity.com/paper/2403.12983/) (2024)
- [L0Learn: A Scalable Package for Sparse Learning using L0 Regularization](https://mlsanity.com/paper/2202.04820/) (2022)
- [Variable Selection for Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.07415/) (2023)
- [A Splicing Approach to Best Subset of Groups Selection](https://mlsanity.com/paper/2104.12576/) (2021)
- [Predicting Census Survey Response Rates With Parsimonious Additive Models and Structured Interactions](https://mlsanity.com/paper/2108.11328/) (2021)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Scalable Subset Selection in Linear Mixed Models](https://mlsanity.com/paper/2506.20425/) (2025)
- [Group selection and shrinkage: Structured sparsity for semiparametric additive models](https://mlsanity.com/paper/2105.12081/) (2021)
- [The Directional Bias Helps Stochastic Gradient Descent to Generalize in Kernel Regression Models](https://mlsanity.com/paper/2205.00061/) (2022)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [End-to-end Feature Selection Approach for Learning Skinny Trees](https://mlsanity.com/paper/2310.18542/) (2023)
- [Differentially Private High-dimensional Variable Selection via Integer Programming](https://mlsanity.com/paper/2510.22062/) (2025)

## Abstract (arXiv)

We present a new algorithmic framework for grouped variable selection that is based on discrete mathematical optimization. While there exist several appealing approaches based on convex relaxations and nonconvex heuristics, we focus on optimal solutions for the ℓ0-regularized formulation, a problem that is relatively unexplored due to computational challenges. Our methodology covers both high-dimensional linear regression and nonparametric sparse additive modeling with smooth components. Our algorithmic framework consists of approximate and exact algorithms. The approximate algorithms are based on coordinate descent and local search, with runtimes comparable to popular sparse learning algorithms. Our exact algorithm is based on a standalone branch-and-bound (BnB) framework, which can solve the associated mixed integer programming (MIP) problem to certified optimality. By exploiting the problem structure, our custom BnB algorithm can solve to optimality problem instances with 5 × 106 features and 103 observations in minutes to hours -- over 1000 times larger than what is currently possible using state-of-the-art commercial MIP solvers. We also explore statistical properties of the ℓ0-based estimators. We demonstrate, theoretically and empirically, that our proposed estimators have an edge over popular group-sparse estimators in terms of statistical performance in various regimes. We provide an open-source implementation of our proposed framework.