Sparse Quantile Regression

Abstract

We consider both ${\ell }_0$-penalized and ${\ell }_0$-constrained quantile regression estimators. For the ${\ell }_0$-penalized estimator, we derive an exponential inequality on the tail probability of excess quantile prediction risk and apply it to obtain non-asymptotic upper bounds on the mean-square parameter and regression function estimation errors. We also derive analogous results for the ${\ell }_0$-constrained estimator. The resulting rates of convergence are nearly minimax-optimal and the same as those for ${\ell }_1$-penalized and non-convex penalized estimators. Further, we characterize expected Hamming loss for the ${\ell }_0$-penalized estimator. We implement the proposed procedure via mixed integer linear programming and also a more scalable first-order approximation algorithm. We illustrate the finite-sample performance of our approach in Monte Carlo experiments and its usefulness in a real data application concerning conformal prediction of infant birth weights (with $n\approx 10^3$ and up to $p>10^3$). In sum, our ${\ell }_0$-based method produces a much sparser estimator than the ${\ell }_1$-penalized and non-convex penalized approaches without compromising precision.

51 pages, 3 figures, 3 tables