  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 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.
