Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives

Hussein Hazimeh, Rahul Mazumder, Peter RadchenkoThe Annals of Statistics 2021 · DOI · OpenReview

TL;DR

This paper introduces a novel framework for grouped variable selection using discrete optimization, specifically targeting the computationally challenging $\ell_0$-regularized problem. They develop both fast approximate algorithms and a custom branch-and-bound solver that achieves certified optimality for problem instances significantly larger than previously possible, offering improved statistical performance over existing methods.

What Problem Does This Paper Address?

In high-dimensional statistical modeling, selecting relevant variables is crucial, especially when predictors have a natural group structure (e.g., related features from a categorical variable or basis expansions of a continuous predictor). Traditional methods often rely on convex relaxations (like Group Lasso) or nonconvex heuristics, which provide approximate solutions. However, finding optimal solutions for the $\ell_0$-regularized formulation, which directly penalizes the number of selected groups, has remained computationally challenging and less explored. This paper aims to bridge this gap by developing scalable algorithms that can find optimal or near-optimal solutions for this $\ell_0$-based grouped variable selection problem, offering both computational and statistical advantages.

Methods

The authors propose a two-pronged algorithmic approach:

  • Approximate Algorithms: These leverage a combination of cyclic block coordinate descent (BCD) and local combinatorial search. The BCD algorithm is a novel adaptation for the discontinuous $\ell_0$ objective, designed to provide high-quality feasible solutions with runtimes comparable to existing methods. The local search further refines these solutions by exploring swaps of groups inside and outside the current support.
  • Exact Algorithm (Branch-and-Bound): To achieve certified optimality, they formulate the problem as a Mixed Integer Program (MIP). Crucially, instead of relying on off-the-shelf commercial MIP solvers (which struggle with large instances), they develop a custom, nonlinear Branch-and-Bound (BnB) framework. This custom solver exploits problem-specific structure, enabling it to solve instances with millions of features to optimality, a feat far beyond current commercial solvers.

Datasets

The paper evaluates their methods on:

  • Synthetic Datasets: Generated with varying correlation structures (high, moderate, low, and zero) and signal-to-noise ratios (SNR) to test performance under different conditions.
  • Amazon Reviews Dataset: A real-world dataset used for evaluating performance on a large-scale, pre-grouped feature set.
  • Boston Housing Dataset: Used to demonstrate the framework's application to nonparametric sparse additive modeling.

Key Insights and Ideas

  • The Power of Discrete Optimization for $\ell_0$: The paper demonstrates that directly tackling the $\ell_0$-regularized problem, rather than relying solely on convex relaxations, can lead to sparser and statistically superior models, especially when groups are correlated.
  • Custom BnB for Scalability: The core innovation lies in their custom BnB solver. By exploiting the specific structure of the $\ell_0$-grouped variable selection problem, they achieve a dramatic leap in computational scalability, solving problems orders of magnitude larger than commercial solvers.
  • Hierarchy of Local Minima: The authors establish a hierarchy of local minima (PGD < BCD < Local Search < Global Minima), showing that their algorithms progressively find solutions satisfying stricter optimality conditions.
  • Ridge Regularization for MIP Strength: The inclusion of an optional ridge regularization term ($\lambda_2$) is shown to lead to tighter convex relaxations in the MIP formulation, which can further improve the performance of the BnB solver.

Key Results

  • Computational Speedup: Their custom BnB solver can solve instances with $5 \times 10^6$ features and $10^3$ observations in minutes to hours, outperforming commercial solvers like Gurobi, which struggle beyond $10^3$ features within a 24-hour limit.
  • Statistical Performance: Empirically and theoretically, their $\ell_0$-based estimators show advantages over Group Lasso, MCP, and SCAD in terms of variable selection accuracy (lower support size, fewer false positives) and prediction error (lower Test MSE), particularly in settings with highly correlated features.
  • Algorithm 1 (Approximate): Achieves competitive runtimes with existing methods while delivering improved statistical performance.
  • Algorithm 2 (Approximate + Local Search): Further enhances variable selection accuracy and reduces support size compared to Algorithm 1.
  • Theoretical Guarantees: Non-asymptotic prediction and estimation error bounds are derived, showing favorable comparisons to Group Lasso.

Limitations and Future Work

  • Tuning Parameter Sensitivity: While the paper demonstrates strong performance, the choice of tuning parameters ($\lambda_0$, $\lambda_2$, and $k$ for cardinality constraints) is crucial and typically requires validation sets or cross-validation.
  • Model Misspecification: While the theoretical analysis focuses on correctly specified models, the authors note that results can be generalized to allow for model misspecification.
  • Future Directions: The authors suggest extending their framework to multivariate response variables (matrix-variate regression), exploring different convex relaxations, and investigating group-sparse problems with hierarchical structures. They also highlight the potential for learning the grouping structure simultaneously with the sparse model.

Summary updated

Abstract

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 $\ell_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 \times 10^6$ features and $10^3$ 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 $\ell_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.
BibTeX
@article{hazimeh2021grouped,
  author = {Hussein Hazimeh and Rahul Mazumder and Peter Radchenko},
  title = {{Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives}},
  journal = {The Annals of Statistics},
  year = {2021},
  doi = {10.1214/21-aos2155},
}
Figure