Understanding the Under-Coverage Bias in Uncertainty Estimation

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 $\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.

References in corpus (17)

• What Uncertainties Do We Need in Bayesian Deep Learning for Computer Vision?
• Message Passing Algorithms for Compressed Sensing
• A tutorial on conformal prediction
• Predictive Uncertainty Estimation via Prior Networks
• Universality in polytope phase transitions and message passing algorithms
• A framework to characterize performance of LASSO algorithms
• Verified Uncertainty Calibration
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Evaluating Uncertainty Quantification in End-to-End Autonomous Driving Control
• Conformalized Quantile Regression
• Adaptive, Distribution-Free Prediction Intervals for Deep Networks
• Robust Validation: Confident Predictions Even When Distributions Shift
• The implicit fairness criterion of unconstrained learning
• Uncertainty Sets for Image Classifiers using Conformal Prediction
• Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification
• Moment Multicalibration for Uncertainty Estimation
• Sample Complexity of Uniform Convergence for Multicalibration

Cited by in corpus (1)

• Quantifying Epistemic Uncertainty in Deep Learning