Fast Active-set-type Algorithms for L1-regularized Linear Regression


Jingu Kim, Haesun Park ;
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:397-404, 2010.


In this paper, we investigate new active-set-type methods for l1-regularized linear regression that overcome some difficulties of existing active set methods. By showing a relationship between l1-regularized linear regression and the linear complementarity problem with bounds, we present a fast active-set-type method, called block principal pivoting. This method accelerates computation by allowing exchanges of several variables among working sets. We further provide an improvement of this method, discuss its properties, and also explain a connection to the structure learning of Gaussian graphical models. Experimental comparisons on synthetic and real data sets show that the proposed method is significantly faster than existing active set methods and competitive against recently developed iterative methods.

Related Material