ℓ1-penalized quantile regression in high-dimensional sparse models

Alexandre Belloni, Victor ChernozhukovThe Annals of Statistics 2009

TL;DR

This paper introduces and analyzes L1-penalized quantile regression (L1-QR) for high-dimensional sparse models, where many potential predictors have no effect on the outcome. The authors show that L1-QR can achieve near-optimal estimation rates and correctly identify important predictors, even when the number of predictors is vastly larger than the sample size. They also propose a data-driven method for selecting the regularization parameter, making the method practical.

What Problem Does This Paper Address?

In many real-world scenarios, we have a large number of potential predictors (features) that might influence an outcome variable. However, in high-dimensional sparse models, only a small subset of these predictors actually have a non-zero effect on the outcome, and this effect might vary across different quantiles (e.g., median, 90th percentile) of the outcome distribution. Standard quantile regression methods struggle in such settings, leading to inconsistent estimates and poor performance. This paper addresses the challenge of performing quantile regression when the number of predictors ($p$) is very large, potentially exceeding the sample size ($n$), but only a small number ($s$) of these predictors are truly relevant for each conditional quantile.

Methods

The core of the paper is the development and analysis of L1-penalized quantile regression (L1-QR). This method extends traditional quantile regression by adding an L1-norm penalty to the objective function. This penalty encourages sparsity, effectively shrinking the coefficients of irrelevant predictors to zero. The authors also introduce a post-L1-QR estimator, which first uses L1-QR to select a subset of predictors and then applies standard quantile regression to this selected subset. A key methodological contribution is a data-driven, pivotal choice for the regularization parameter (λ), which is crucial for the theoretical guarantees to hold. They also develop sophisticated theoretical tools, including chaining arguments and exponential inequalities, to analyze the properties of these estimators in high-dimensional settings.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses simulated data for its Monte Carlo experiments.

Key Insights and Ideas

  • L1-QR bridges the gap: Standard quantile regression fails in high-dimensional sparse settings. L1-QR provides a principled way to perform quantile regression by leveraging sparsity, achieving near-oracle rates.
  • Near-optimal rates are achievable: The L1-QR estimator can achieve rates close to the "oracle" rate (what you'd get if you knew the true sparse model), specifically $\sqrt{s/n} \sqrt{\log(p \vee n)}$. This is remarkable because it means the rate is only mildly affected by the total number of predictors ($p$), allowing for nearly exponential growth in irrelevant predictors.
  • Data-driven parameter selection is key: A crucial practical aspect is selecting the regularization parameter. The authors propose a novel, pivotal, data-driven method for choosing $\lambda$ that ensures the theoretical guarantees are met.
  • Post-L1-QR offers improvements: The two-step post-L1-QR estimator can perform as well as or even better than L1-QR, especially when the model selection step is imperfect but still captures the most important predictors. It helps reduce bias.
  • Model selection properties are strong: Under certain conditions (e.g., well-separated coefficients), L1-QR can correctly identify the true sparse model, or at least include it as a subset. The dimension of the selected model is shown to be of the same stochastic order as the true dimension.

Key Results

  • L1-QR consistency: The L1-QR estimator is shown to be consistent at the near-oracle rate $\sqrt{s/n} \sqrt{\log(p \vee n)}$ uniformly over a range of quantile indices.
  • Post-L1-QR performance: The post-L1-QR estimator achieves similar or faster rates, especially when model selection is good.
  • Sparsity bounds: The paper derives bounds on the number of selected non-zero coefficients, showing they are of the same order as the true number of non-zero coefficients ($s$).
  • Model selection accuracy: Theoretical conditions are provided under which L1-QR correctly selects the true model or a subset thereof.
  • Monte Carlo simulations: Experiments confirm the theoretical findings, showing that L1-QR performs well in terms of model selection and estimation accuracy, with the post-L1-QR estimator significantly reducing bias and empirical risk. The post-L1-QR estimator's empirical risk was within a factor of $\sqrt{\log p}$ of the oracle estimator.

Limitations and Future Work

  • Perfect model selection is unlikely: The authors acknowledge that perfect model selection (where the L1-QR selected model exactly matches the true model) is unrealistic in practice. This motivates their analysis of the post-L1-QR estimator, which handles imperfect selection.
  • Conditions for theoretical guarantees: While the conditions are relatively weak, they still need to be met for the theoretical guarantees to hold. The paper provides examples (Design 1 and 2) where these conditions are satisfied.
  • Future work: The paper mentions that their results on post-penalized estimators and proof techniques could be of interest in other problems. They also note that their work has been extended to mean regression and that further work is ongoing on devising procedures for confidence intervals that account for model selection. The application to international economic growth suggests potential for L1-QR in empirical economics.

Summary updated

Abstract

We consider median regression and, more generally, a possibly infinite collection of quantile regressions in high-dimensional sparse models. In these models, the number of regressors p is very large, possibly larger than the sample size n, but only at most s regressors have a nonzero impact on each conditional quantile of the response variable, where s grows more slowly than n. Since ordinary quantile regression is not consistent in this case, we consider ℓ1-penalized quantile regression (ℓ1-QR), which penalizes the ℓ1-norm of regression coefficients, as well as the post-penalized QR estimator (post-ℓ1-QR), which applies ordinary QR to the model selected by ℓ1-QR. First, we show that under general conditions ℓ1-QR is consistent at the near-oracle rate $\sqrt{s/n}\sqrt{\log(p\vee n)}$, uniformly in the compact set $\mathcal{U}\subset(0,1)$ of quantile indices. In deriving this result, we propose a partly pivotal, data-driven choice of the penalty level and show that it satisfies the requirements for achieving this rate. Second, we show that under similar conditions post-ℓ1-QR is consistent at the near-oracle rate $\sqrt{s/n}\sqrt{\log(p\vee n)}$, uniformly over $\mathcal{U}$, even if the ℓ1-QR-selected models miss some components of the true models, and the rate could be even closer to the oracle rate otherwise. Third, we characterize conditions under which ℓ1-QR contains the true model as a submodel, and derive bounds on the dimension of the selected model, uniformly over $\mathcal{U}$; we also provide conditions under which hard-thresholding selects the minimal true model, uniformly over $\mathcal{U}$.
BibTeX
@article{belloni2009l,
  author = {Alexandre Belloni and Victor Chernozhukov},
  title = {{ℓ1-penalized quantile regression in high-dimensional sparse models}},
  journal = {The Annals of Statistics},
  year = {2009},
}
Figure