Understanding the Under-Coverage Bias in Uncertainty Estimation

Yu Bai, Song Mei, Huan Wang, Caiming Xiong

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.

Simulated vs. analytical coverage against the feature-to-sample ratio (d/n)

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.

Coverage results on real-world datasets across different model capacities

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

Abstract

Estimating the data uncertainty in regression tasks is often done by learning a quantile function or a prediction interval of the true label conditioned on the input. It is frequently observed that quantile regression---a vanilla algorithm for learning quantiles with asymptotic guarantees---tends to *under-cover* than the desired coverage level in reality. While various fixes have been proposed, a more fundamental understanding of why this under-coverage bias happens in the first place remains elusive. In this paper, we present a rigorous theoretical study on the coverage of uncertainty estimation algorithms in learning quantiles. We prove that quantile regression suffers from an inherent under-coverage bias, in a vanilla setting where we learn a realizable linear quantile function and there is more data than parameters. More quantitatively, for $\alpha>0.5$ and small $d/n$, the $\alpha$-quantile learned by quantile regression roughly achieves coverage $\alpha - (\alpha-1/2)\cdot d/n$ regardless of the noise distribution, where $d$ is the input dimension and $n$ is the number of training data. Our theory reveals that this under-coverage bias stems from a certain high-dimensional parameter estimation error that is not implied by existing theories on quantile regression. Experiments on simulated and real data verify our theory and further illustrate the effect of various factors such as sample size and model capacity on the under-coverage bias in more practical setups.
BibTeX
@inproceedings{bai2021understanding,
  author = {Yu Bai and Song Mei and Huan Wang and Caiming Xiong},
  title = {{Understanding the Under-Coverage Bias in Uncertainty Estimation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=te8iyHjbPQd},
}
Figure