A Pathwise Coordinate Descent Algorithm for LASSO Penalized Quantile Regression

Music City Center 

L1 penalized quantile regression (PQR) is used in many fields as an alternative to penalized least squares regressions for data analysis. Existing algorithms for PQR either use linear programming, which does not scale well in high dimension, or an approximate coordinate descent (CD) which does not solve for exact coordinatewise minimum of the nonsmooth loss function. Further, neither approaches leverage sparsity structure of the problem in large-scale datasets. To avoid the computational challenges associated with the nonsmooth quantile loss, some recent works have even advocated using smooth approximations to the exact problem. In this work, we develop a fast, pathwise CD algorithm to compute exact L1 PQR estimates for all dimensional data. We derive an easy-to-compute exact solution for the coordinatewise nonsmooth loss minimization, which, to the best of our knowledge, has not been reported in the literature. We also employ a random perturbation to help the algorithm avoid getting stuck along the regularization path. In simulated and real world datasets, we show that our algorithm runs substantially faster than existing alternatives, while retaining the same level of estimation accuracy.

LASSO

penalized quantile regression

coordinate descent

pathwise algorithm 

Section on Statistical Computing