Sparse Quantile Regression

Le‐Yu Chen, Sokbae LeearXiv 2020 · DOI · arXiv

Abstract

This paper investigates $\ell_{0}$-penalized and $\ell_{0}$-constrained quantile regression estimators in high-dimensional settings. We derive non-asymptotic upper bounds on mean-square parameter and regression function estimation errors, demonstrating that $\ell_{0}$-based methods achieve nearly minimax-optimal convergence rates comparable to $\ell_{1}$-penalized and non-convex penalized estimators. To address the computational challenges of $\ell_{0}$ optimization, we implement a mixed integer linear programming (MILP) approach and a scalable first-order approximation algorithm. Our results, validated through Monte Carlo experiments and a real-world application on infant birth weights, show that $\ell_{0}$ methods produce significantly sparser models without compromising predictive precision.

Introduction

In high-dimensional statistics, the goal is often to identify a small subset of relevant features from a large pool of candidates—a property known as sparsity. While mean regression is the standard tool for this task, quantile regression offers a more robust alternative, allowing researchers to model specific percentiles of a distribution. This is particularly valuable when dealing with outliers or when the tails of a distribution are of primary interest, such as in the study of very low birth weights.

To achieve sparsity, the field has traditionally relied on $\ell_{1}$-penalization (e.g., the Lasso) due to its convexity and computational ease. However, $\ell_{1}$ methods frequently suffer from "over-selection," including many irrelevant variables in the final model. The $\ell_{0}$ penalty, which directly counts the number of non-zero coefficients, is the theoretical "gold standard" for sparsity but has historically been avoided due to its non-convexity and computational complexity. This research bridges the gap by providing rigorous theoretical guarantees and efficient algorithms for $\ell_{0}$ quantile regression.

The $\ell_{0}$ Framework

We consider two primary formulations of the sparse quantile regression problem:

  1. $\ell_{0}$-Constrained Quantile Regression (CQR): Minimizing the quantile loss subject to a hard constraint on the number of non-zero variables ($q$).
  2. $\ell_{0}$-Penalized Quantile Regression (PQR): Minimizing the quantile loss plus a penalty term ($\lambda$) proportional to the number of non-zero variables.

Theoretical Contributions

A central contribution of this work is the derivation of non-asymptotic bounds on the tail probability of excess quantile prediction risk. We prove that these $\ell_{0}$ estimators achieve the minimax-optimal convergence rate—the best possible rate any estimator can achieve. Crucially, this demonstrates that there is no theoretical "penalty" in terms of error rates for choosing the more aggressive $\ell_{0}$ approach over $\ell_{1}$ methods.

Computational Methodology

Solving $\ell_{0}$ problems is traditionally NP-hard. We address this through two distinct computational strategies:

  • Mixed Integer Linear Programming (MILP): By reformulating the $\ell_{0}$ problem, we leverage modern optimization solvers (such as Gurobi) to find exact solutions. While highly precise, MILP can be computationally intensive for extremely large datasets.
  • First-Order (FO) Approximation: To scale to higher dimensions, we develop a fast iterative algorithm using Nesterov’s smoothing technique. By approximating the non-smooth quantile loss function with a smooth version, the FO algorithm can find high-quality solutions quickly. This algorithm can serve as a standalone solver or as a "warm-start" to accelerate the MILP process.

Empirical Results

Monte Carlo Simulations

In synthetic tests with up to $p=500$ variables and $n=100$ observations, $\ell_{0}$-PQR and $\ell_{0}$-CQR consistently outperformed $\ell_{1}$ methods in terms of out-of-sample relative risk. Furthermore, the $\ell_{0}$ methods demonstrated superior variable selection, achieving much higher "Oracle" selection rates (identifying the exact true variables) while $\ell_{1}$ methods included significant noise.

Application: Infant Birth Weights

We applied the proposed methods to a real-world dataset of 4,642 infant birth weight observations. By creating high-dimensional feature dictionaries using B-splines and interactions, we reached a covariate space of $p=1,617$.

The results were striking: to achieve the same predictive performance, the $\ell_{1}$ approach required 155 variables, whereas the $\ell_{0}$ approach selected only 9. When used for conformal prediction, the $\ell_{0}$ method produced narrower, more precise prediction intervals while maintaining the required 90% coverage probability. This demonstrates that $\ell_{0}$ methods can achieve extreme sparsity without sacrificing accuracy.

Conclusion

This research establishes that $\ell_{0}$-based quantile regression is both theoretically sound and computationally viable. By producing models that are an order of magnitude sparser than those generated by $\ell_{1}$ methods, our approach offers enhanced interpretability for high-dimensional data analysis. Future work may explore hybrid penalties, such as combining $\ell_{0}$ with $\ell_{2}$ regularization, to improve stability in settings with highly correlated variables.

Summary updated

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.
BibTeX
@misc{chen2020sparse,
  author = {Le‐Yu Chen and Sokbae Lee},
  title = {{Sparse Quantile Regression}},
  year = {2020},
  eprint = {2006.11201},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.11201},
}
Figure