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:
- 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.
- Novel Concentration Argument: Developed new techniques to handle the learnable bias term ($b$) in linear models, which behaves differently than the slope coefficients ($w$).
- 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.
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