Understanding the Under-Coverage Bias in Uncertainty Estimation

Yu Bai, Song Mei, Huan Wang, Caiming Xiong

This paper, presented by researchers from Salesforce Research and UC Berkeley, provides a long-overdue theoretical explanation for a phenomenon well-known to practitioners: quantile regression tends to be overconfident. Even when you have more data than parameters, your "95% confidence interval" might only cover 91% of the actual data points.

TL;DR

The authors prove that quantile regression suffers from an inherent "under-coverage bias" in high-dimensional settings, even when the model is perfectly specified. They provide a simple, elegant formula to quantify this: an $\alpha$-quantile roughly achieves a coverage of $\alpha - (\alpha - 0.5) \cdot d/n$, where $d$ is the number of features and $n$ is the number of samples.

What Problem Does This Paper Address?

In fields like medical AI or autonomous driving, knowing how much to trust a prediction is as important as the prediction itself. Quantile regression is the standard "vanilla" algorithm for this, designed to estimate values (quantiles) that should bound the true label a specific percentage of the time (e.g., the 95th percentile).

While classical theory says quantile regression is asymptotically correct as you get infinite data, real-world models consistently "under-cover"—they fail to bound the true label as often as they should. Until now, it wasn't clear if this was due to model misspecification, noise, or something fundamental to the algorithm. This paper proves it's the latter.

Methods

The authors study linear quantile regression in the high-dimensional proportional limit, where both the number of features ($d$) and samples ($n$) are large, but their ratio ($d/n$) is a fixed, small constant.

To analyze this, they:

  1. Theoretical Framework: Built upon recent advances in high-dimensional M-estimation (specifically the Convex Gaussian Comparison Theorem) to characterize how empirical risk minimizers behave when $d/n$ is non-zero.
  2. Novel Concentration Argument: Developed new techniques to handle the learnable bias term ($b$) in linear models, which behaves differently than the slope coefficients ($w$).
  3. Disentanglement: They mathematically separated the coverage error caused by estimating the bias from the error caused by estimating the slope.

Datasets

The authors validated their theory using both synthetic and real-world benchmarks:

  • Simulations: Gaussian linear models where the ground truth is known.
  • Real-world Regression:
    • Community and Crimes: Predicting crime rates.
  • Bike Sharing: Predicting rental demand.
  • STAR: Tennessee’s student-teacher achievement ratio.
  • MEPS (19, 20, 21): Medical Expenditure Panel Survey data.

Key Insights and Ideas

  • The "Slope" is the Culprit: The authors found that while errors in estimating the bias term ($b$) can lead to either under- or over-coverage depending on the noise distribution, errors in the slope coefficients ($w$) always drive the model toward under-coverage.
  • The $d/n$ Penalty: The bias is directly proportional to the "complexity-to-data" ratio. If you have 100 features and 1000 samples ($d/n = 0.1$), a 90% quantile will actually cover only about 86% of the data ($0.9 - (0.9 - 0.5) \cdot 0.1 = 0.86$).
  • Over-parametrization Collapse: In the extreme case where the model has enough capacity to interpolate the data ($d > n$), the coverage collapses to 0.5 (50%) regardless of the target $\alpha$. In other words, the model's uncertainty estimates become no better than a coin flip.
  • Model Capacity Matters: Experiments with Neural Networks (MLPs) showed much more severe under-coverage than linear models, suggesting that high-capacity models effectively "consume" more of the $d/n$ budget.

Key Results

The simulation results (Figure 1) show a near-perfect match between the authors' analytical formula and actual experimental outcomes.

Figure 1: Coverage of quantile regression on simulated data from the realizable linear model (4). (a)(b) Each dot represents a combination of (α, κ) and reports the mean and one-std coverage over 8 random problem instances. (a) Coverage against the nominal quantile level α for fixed values of κ = d/n. (b) Coverage against κ for fixed α ∈{0.8, 0.9, 0.95}. Here “analytical” refers to our analyitical formula α −Cα,κ and α −(1 −α/2)κ is its local linear approximation at small κ (both from Theorem 1).

On real-world data (Table 1 in the paper), the results were striking. For a nominal 90% coverage target:

  • Linear models stayed close (e.g., 88.6% on the Community dataset).
  • Large MLPs failed significantly, dropping as low as 63.1% coverage on the same dataset.

Limitations and Future Work

  • Linearity Assumption: The core proof assumes a linear quantile function and Gaussian inputs. While the experiments suggest the bias persists in non-linear models (MLPs) and non-Gaussian data, a rigorous theory for neural networks remains for future work.
  • Fixes: The paper focuses on understanding the bias rather than fixing it, though the authors note that post-processing techniques like conformal prediction are likely necessary to achieve guaranteed coverage.
  • Beyond Regression: Exploring whether similar inherent biases exist in uncertainty quantification for classification (e.g., temperature scaling or label smoothing) is a promising next step.

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 \emph{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 $α>0.5$ and small $d/n$, the $α$-quantile learned by quantile regression roughly achieves coverage $α- (α-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},
}

Loading related content...

Figure