  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.
