This paper, presented at NeurIPS 2021, provides a long-awaited theoretical explanation for a common frustration in machine learning: why uncertainty estimates often turn out to be "overconfident" or "under-covering" in practice.
The Under-Coverage Problem in Quantile Regression
In regression tasks, practitioners often need more than just a single predicted value; they need a "prediction interval." For example, a self-driving car needs to know not just the most likely location of a curb, but the range of where it might be with 95% certainty. This is typically achieved using quantile regression, which optimizes a specific "pinball loss" to learn a boundary that should theoretically stay above the true label $\alpha$% of the time.
However, practitioners have long noticed a persistent gap: a model trained to provide 90% coverage might only achieve 86% on new data. Historically, this discrepancy was blamed on "model misspecification" (the model being too simple) or "finite sample noise." This paper argues that the bias is actually a fundamental mathematical property stemming from the ratio between the number of features ($d$) and the number of training samples ($n$).
Theoretical Insights: The $d/n$ Penalty
The authors perform a rigorous theoretical analysis of linear quantile regression in a high-dimensional setting. Specifically, they examine the "proportional regime" where both the number of features ($d$) and samples ($n$) are large, but their ratio ($\kappa = d/n$) is a small, non-zero constant.
Using tools from high-dimensional M-estimation, they derive a precise formula for the expected coverage. The paper’s most striking finding is a simple approximation for the coverage of an $\alpha$-quantile:
$$\text{Coverage} \approx \alpha - (\alpha - 0.5) \frac{d}{n}$$
If you want 90% coverage ($\alpha=0.9$) and your feature-to-sample ratio is 0.1, you will likely end up with only 86% coverage.
By disentangling the estimation errors, the authors discovered that while errors in the intercept (bias) can sometimes help coverage, errors in the linear coefficients (weights) always drive the model toward under-coverage. Furthermore, they proved this bias isn't just caused by the model being "wrong" about the data distribution; using "pseudo-labels" that perfectly match a linear model, the bias still persists.
Real-World Impact and Model Capacity
The theory was validated using both synthetic Gaussian linear models and real-world regression benchmarks (e.g., predicting crime rates, bike rental demand, and healthcare utilization). The under-coverage effect was found to be largely independent of the specific noise distribution in the data, suggesting it is a universal property of the quantile regression algorithm itself.
Crucially, the bias is exacerbated in high-capacity models like Multi-Layer Perceptrons (MLPs). Because these models have many more parameters (a higher effective $d$), the $d/n$ ratio increases, causing the coverage to plummet.
As shown in the results above, on the "Community" dataset, a standard linear model showed a mild under-coverage (88.63% for a 90% target). However, a large Neural Network (MLP-3-512) exhibited a massive ~27% gap, achieving only 63.09% coverage.
Limitations and Future Work
While the paper provides a breakthrough in understanding linear models, there are several areas for further exploration:
- Non-Linear Theory: The rigorous proofs are currently limited to linear quantile regression. While the authors empirically show the effect exists in Neural Networks, a precise mathematical characterization for deep learning is still needed.
- Corrective Algorithms: The paper identifies the "why" but doesn't focus on a "fix." While conformal prediction is mentioned as a potential remedy, developing a more efficient way to "de-bias" standard quantile regression remains an open challenge.
- Gaussian Assumptions: Much of the high-dimensional theory relies on the assumption that input features follow a Gaussian distribution, which may not strictly hold for all real-world tabular data.
Summary updated