We consider the least squares regression problem, penalized with a
combination of the $\ell_{0}$ and squared $\ell_{2}$ penalty functions (a.k.a.
$\ell_0 \ell_2$ regularization). Recent work shows that the resulting
estimators are of key importance in many high-dimensional statistical settings.
However, exact computation of these estimators remains a major challenge.
Indeed, modern exact methods, based on mixed integer programming (MIP), face
difficulties when the number of features $p \sim 10^4$. In this work, we
present a new exact MIP framework for $\ell_0\ell_2$-regularized regression
that can scale to $p \sim 10^7$, achieving speedups of at least $5000$x,
compared to state-of-the-art exact methods. Unlike recent work, which relies on
modern commercial MIP solvers, we design a specialized nonlinear
branch-and-bound (BnB) framework, by critically exploiting the problem
structure. A key distinguishing component in our framework lies in efficiently
solving the node relaxations using a specialized first-order method, based on
coordinate descent (CD). Our CD-based method effectively leverages information
across the BnB nodes, through using warm starts, active sets, and gradient
screening. In addition, we design a novel method for obtaining dual bounds from
primal CD solutions, which certifiably works in high dimensions. Experiments on
synthetic and real high-dimensional datasets demonstrate that our framework is
not only significantly faster than the state of the art, but can also deliver
certifiably optimal solutions to statistically challenging instances that
cannot be handled with existing methods. We open source the implementation
through our toolkit L0BnB.

本文提出了一种新的混合整数规划框架，结合非线性分支定界和坐标下降方法，用于计算最小二乘回归中的 $l_{0} l_{2}$ 惩罚，证明了该框架不仅比现有方法快很多，而且可以处理一些统计性较强的示例，并提供了 $L0BnB$ 工具箱的开源实现。