B1258
Title: Fast L0 regression: Coordinate descent, local search, and combinatorial optimization
Authors: Hussein Hazimeh - Massachusetts Institute of Technology (United States) [presenting]
Rahul Mazumder - MIT (United States)
Abstract: The computation of estimators for the $L_0$ penalized regression problem with possible additive regularizers is considered. While these estimators exhibit nice statistical properties, current algorithms for this class of problems can be slow when compared to the efficient algorithms for the Lasso (e.g., glmnet). The aim is to reduce this gap. We explore coordinate descent-type methods and show (both in theory and practice) that they outperform the commonly used iterative hard-thresholding type methods in terms of solution quality and computation times. We develop a unified framework in which local search methods, pathwise optimization, and mixed integer optimization are integrated with coordinate descent to escape weak local minima and obtain high-quality sparse solutions. Our specialized C++ implementation is comparable in speed to state-of-the art sparse regression packages such as glmnet.
