Sparse regression at scale: branch-and-bound rooted in first-order optimization

• 成果类型: Article
• 署名作者: Hazimeh, Hussein; Mazumder, Rahul; Saab, Ali
• 署名单位: Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01712-4
• 发表日期: 2022
• 页码: 347-388
• 关键词: subset-selection; extended formulations; scalable algorithms; integer; PROGRAMS; models; Lasso

摘要

We consider the least squares regression problem, penalized with a combination of the l(0) and squared l(2) penalty functions (a.k.a. l(0)l(2) regularization). Recent work shows that the resulting estimators enjoy appealing statistical properties in many high-dimensional settings. However, exact computation of these estimators remains a major challenge. Indeed, modern exact methods, based on mixed integer programming (MIP), face difficulties for problems where the number of features p similar to 10(4). In this work, we present a new exact MIP framework for l(0) l(2)-regularized regression that can scale to p similar to 10(7), achieving speedups of at least 5000x, compared to state-of-the-art exact methods. Unlike recent work, which relies on 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 firstorder method, based on coordinate descent (CD). Our CD-based method effectively leverages information across the BnB nodes through usingwarm 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 solved with existing methods. We open source the implementation through our toolkit L0BnB.