-

 

 

 




Optimization Online





 

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization

Hussein Hazimeh(hazimeh***at***mit.edu)
Rahul Mazumder(rahulmaz***at***mit.edu)
Ali Saab(saab***at***mit.edu)

Abstract: We consider the least squares regression problem, penalized with a combination of the L0 and L2 norms (a.k.a. L0 L2 regularization). Recent work presents strong evidence that the resulting L0-based estimators can outperform popular sparse learning methods, under many important high-dimensional settings. However, exact computation of L0-based estimators remains a major challenge. Indeed, state-of-the-art mixed integer programming (MIP) methods for L0 L2-regularized regression face difficulties in solving many statistically interesting instances when the number of features p ~ 10^4. In this work, we present a new exact MIP framework for L0 L2-regularized regression that can scale to p ~ 10^7, achieving over 3600x speed-ups compared to the fastest exact methods. Unlike recent work, which relies on modern MIP solvers, we design a specialized nonlinear BnB framework, by critically exploiting the problem structure. A key distinguishing component in our algorithm lies in efficiently solving the node relaxations using specialized first-order methods, 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 solutions, which certifiably works in high dimensions. Experiments on synthetic and real high-dimensional datasets demonstrate that our method 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.

Keywords: Branch-and-Bound, First-order Methods, Sparsity, L0 Regularization, Sparse Regression

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation:

Download: [PDF]

Entry Submitted: 04/13/2020
Entry Accepted: 04/16/2020
Entry Last Modified: 04/13/2020

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society