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:
- $\ell_{0}$-Constrained Quantile Regression (CQR): Minimizing the quantile loss subject to a hard constraint on the number of non-zero variables ($q$).
- $\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