Solving l1 Regularization Problems With Piecewise Linear Losses

This article is concerned with the computational aspect of Pi regularization problems with a certain class of piecewise linear loss functions. The problem of computing the l(1) regularization path for a piecewise linear loss can be formalized as a parametric linear programming problem. We propose an efficient implementation method of the parametric simplex algorithm for such a problem. We also conduct a simulation study to investigate the behavior of the number of "breakpoints" of the regularization path when both the number of observations and the number of explanatory variables vary. Our method is also applicable to the computation of the regularization path for a piecewise linear loss and the blockwise l(infinity) penalty. This article has supplementary material online.