Grouped Variable Selection with Discrete Optimization: Computational and
  Statistical Perspectives
  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.
