Understanding the Under-Coverage Bias in Uncertainty Estimation
Authors: Yu Bai
Song Mei
Huan Wang
Caiming Xiong
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Under-coverage bias
uncertainty estimation
quantile regression
learning theory

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.

Understanding the Under-Coverage Bias in Uncertainty Estimation
Yu Bai
Song Mei UC Berkeley songmei@berkeley.coo edu
Salesforce Research yu. bai www.essarrrce.oooooooooooool com
Huan Wang
Caiming Xiong
Salesforce Research
Salesforce Research cxiong@saleesorce. com
huan hua..wangeeaeeee www.waealelefrrreeoooomm
Abstract
Estimating the data uncertainty in regression tasks is often done by learning quantile function or a prediction interval of the true label conditioned on the input. It is frequently observed that quantile regression- 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, fundamental understanding of why this under-coverage bias happens in the first place remains elusive.
In this paper, we present 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 a 0.5 and small d/n, the a-quantile learned by quantile regression roughly achieves coverage distribution, where is the input dimension and n the number of training data. Our theory reveals that this under-coverage bias stems from certain high- dimensional parameter estimation error that is not implied by existing theories quantile regression. Experiments and further illustrate the effect of various factors such as sample size and model capacity the under-coverage bias in practical setups.
(a 1/2) d/r regardless of the noise
simulated and real data verify theory
Introduction
This paper is concerned with the problem of uncertainty estimation in regression problems. Uncer- tainty estimation an increasingly important task modern machine learning applications Modieas -Models should not only make high-accuracy predictions. but also have sense of how much the true label may deviate from the prediction. This capability crucial for deploying machine learning in the real world, in particular in risk-sensitive domains such as medical AI [15, 29), self-driving cars [47], and so on. common approach for uncertainty estimation regression to learn quantile function or prediction interval of the true label conditioned on the input, which provides useful distributional information about the label. Such learned quantiles are typically evaluated by their coverage, i.c., probability that it covers the true label quantile function should be an actual upper bound of the true label at least 90% of the time.
new test example. For example, a learned 90% upper
Algorithms for learning quantiles date back to the classical quantile regression [35], which estimates the quantile function by solving an empirical risk minimization problem with a suitable loss function that depends on the desired quantile level a. Quantile regression is conceptually simple, and is
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

theoretically shown to achieve asymptotically correct coverage the sample size goes to infinity [34] or approximately correct coverage finite samples under specific modeling assumptions [46, 60, 56]. However, it is observed that quantile regression often under-cover than the desired coverage level in practice [53]. Various alternative approaches for constructing quantiles and confidence intervals are proposed in more recent work, for example by aggregating multiple predictions using Bayesian neural networks or ensembles [24, 37], or by building on the conformal prediction technique to construct prediction intervals with finite-sample coverage guarantees [68, 66, 39, 53]. However, despite these advances, a more fundamental understanding on why vanilla quantile regression exhibits this under-coverage bias is still lacking.
This paper revisits quantile regression and presents first precise theoretical study on its coverage, in a new regime where the number of samples n is proportional to the dimension d. and the ratio d/ f/n is small (so that the problem is under-pan (ateerparamtrized) Our main result shows that quantile regression exhibits an inherent under-cover bias under this regime, even in the well-specified setting of learning a linear quantile function when the true data distribution follows a Gaussian linear model. To the best juseeiicalssiiiiaattioo
of our knowledge, this is the first rigorous theoretical justification of the under-coverage bias. Our main contributions are summarized as follows.
We prove that linear quantile regression exhibits an inherent under-coverage bias in the well- specified setting where the data is generated from a Gaussian linear model, and the number of samples n is proportional to the feature dimension d with a small d/n (Section 3). More quantitatively. quantile regression nominal level a E (0.5, 1) roughly achieves coverage (a- 1/2)d/n n. regardless of the noise distribution. To the best of our knowledge, this is the first rigorous characterization of the under-coverage bias in quantile regression.
Towards understanding the source of this under-covcrage bias, we disentangle the effect of estimating the bias and estimating the linear coefficient the coverage of the learned linear quantile (Section 4). We show that the estimation error in the bias can have either an under- coverage over-coverage effect, depending on the noise distribution. In contrast, the estimation error in the linear coefficient always drives the learned quantile to under-cover, and we show this effect is present even broader classes of data distributions beyond the Gaussian linear model.
We perform experiments on simulated and real data to test our theory (Section 5). Our simulations show that the coverage of quantile regression in Gaussian linear models agrees well with our precise theoretical formula as well as the a (a- 1/2)d/n n approximation. On real data, we find quantile regression using high-capacity models (such as neural networks) exhibits severe under-coverage biases, while linear quantile regression can also have a mild but non-negligible amount of under-coverage, even after we remove the potential effect of model misspecification.
On the technical end, our analysis builds recent understandings of empirical risk minimiza- tion problems in the high-dimensional proportional limit with a small d/n, and develops new techniques such novel concentration argument deal with additional learnable variable in learning linear models with biases, which we believe could be of further interest (Section 6).
1.1 Related work
Algorithms for uncertainty estimation in regression The earliest methods for uncertainty esti- mation in regression adopted subsampling methods (bootstrap) or leave-one-out methods (Jackknife) for assessing or calibrating prediction uncertainty [52, 63, 58, 25). More recently, a growing line of work builds on the idea of conformal prediction [55] to design uncertainty estimation algorithms for regression. These algorithms provide confidence bounds or prediction intervals by prot-processing any predictor, and can achieve distribution-fire finite-sample marginal coverage guarantees utilizing exchangeability of the data [50, 66, 39, 53, 33, 67, 69, 68, 11]. Further modifications of the conformal prediction technique can yield stronger guarantees such as group coverage [10] or coverage under dis- tribution shift [9] under additional assumptions. Our under-coverage results advocate the necessity of such post-processing techniques, and are complementary in the sense that we provide understandings on the more vanilla quantile regression algorithm. Quantiles and prediction intervals can also be ob- tained by aggregating multiple predictors, such using Bayesian neural networks [41, 24, 32, 44, 42] or ensembles [37, 49, 28, 45]. These methods offer an alternative approach for uncertainty estimation, but do not typically come with coverage guarantees.

---

Theoretical analysis of quantile regression Linear quantile regression with the pinball loss dates back to the late 1970s [34]. The same work proved the asymptotic normality of the regression coefficients in the + co, fixed d limit. Takeuchi et al. [60] studied non-parametric quantile regression using kernel methods, and provided generalization bounds (with the pinball loss) based on the Rademacher complexity. Meinshausen [46] studied non-parametric quantile regression using random forest and showed its consistency under proper assumptions. Christmann and Steinwart [19], Steinwart et al. [56] established "self-calibration"" inequality for the quantile loss, which, when combined with standard generalization bounds, can be translated to an estimation error bound for quantile regression. These works all focus on bounding the parameter function estimation error, which can be translated to bounds on the coverage bias, but does not tell the sign of this coverage bias as we do in this paper. We also remark that conformalization can be used in conjunction with quantile regression to correct its coverage bias [53].
Uncertainty quantification for classification For classification problems, two main types of un- certainty quantification methods have been considered: outputting discrete prediction sets with guarantees of covering the true (discrete) label [70, 71, 38. 7, 12, 18, 17], or calibrating the predicted probabilities [51, 72, 73. 37, 26]. The connection between prediction sets and calibration was dis- cussed in [27]. The sample complexity of calibration has been studied in number of theoretical works [36, 27, 54, 30, 40, 8]. Our work is inspired by the recent work of Bai et al. [8], which showed that logistic regression is over-confident even if the model is correctly specified and the sample size is larger than the dimension.
High-dimensional behaviors of empirical risk minimization There is rapidly growing liter- ature on limiting characterizations of convex optimization-bant based estimators in the n x regime [21, 13, 23, 31, 57, 61, 20, 62, 43, 59, 16]. Our analysis builds results for unregularized M- estimator derived in [62] and generalizes theirs in certain aspects (see also [23, 20, 31)).
2 Preliminaries
In this paper we focus on the problem of learning quantiles. Suppose we observe a training dataset {(xx, (x))); y:)]
drawn i.i.d. from some joint distribution P on IR x R. where x; IRd is the input features and y E R is the real-valued response (label). Let F(t[x) == P(Y < f = x) denote the conditional CDF of Y|X. Our goal to learn the a-(conditional) quantile of Y X::
% (x) == inf {t E R: F(t)x) 2 a).
For example, 9ñ.95 (x) is the ground truth 95% quantile of the true conditional distribution Y|X, and can be seen as the "ideal" 95% upper confidence bound for the label y given the features x. Throughout this paper we work with upper quantiles, that is, E (0.5, 1) (some typical choices are a E {0.8, 0.9, (.95 by symmetry our results hold for learning lower quantiles as well.
Coverage For any learned quantile function f IRd + R, the marginal coverage (henceforth "coverage") of f is the probability of y S f(x) on new test example (x, y):
Coverage( f) = P (xx.))
= (P
E.
(1)
For learning the a-quantile (a > 0.5), we usually expect Coverage (f) v a, i.c. f(x) covers the label y on approximately a proportion of the data, under the ground truth data distribution.
We say that î has under-coverage if Coverage( a and over-coverage if Coverage > a. Note that these two notions are not symmetric: Over-coverage means that the learned upper quantile f(x) is overly conservative (higher than enough), and is typically tolerable; In contrast, under-coverage means that f(x) fails to cover y with a probability, and is typically considered remark that while there exist more fine-graine notions of coverage such as conditional coverage [10]. the (marginal) coverage is still a basic requirement for any quantile learning algorithm.
failure. We
Quantile regression We consider quantile regression, a standard method for learning quantiles from
data [35]. Quantile regression estimates the true quantile function (-) via the pinball loss [34, 56]
ed (t) = (11 a)t1 ft < 0} + af1 (t > 0}.
(2)
3

---

Note that in the special case of a = 0.5, we have (t) / and thus the pinball loss strictly generalizes the absolute loss (for learning medians) learning any quantile. Given the training dataset and any function class (Jo 0 E ) (e.g. linear models or neural networks), quantile regression solves the (unregularized) empirical risk minimization (ERM) problem
1
0 = arg min (0) ==
n (m - -
(3)
8EB
(We take & as any minimizer of Ra when the minimizer is non-unique.) Let R(O) := E[ (0)
denote the corresponding population risk. It is known that the population risk over all (measurable) functions is minimized at the true quantile 2 = arg miny R(f) under minimal regularity conditions (for completeness, we provide a proof in Appendix B.1).
Quantile regression exhibits under-coverage
We analyze quantile regression in the vanilla setting where the input distribution is a standard Gaussian and y follows linear model x:
W. x where x ~ N(,, = P..
(4)
Above, w, E Rd is the ground truth coefficient vector, and the noise = ~ P3 is independent of x. The Gaussian input assumption is required only for technical convenience in the high-dimensional limiting analysis, and we believe it is not strictly required for the same result to hold' (an extension to more general input distributions can also be found in Section 4). The noise distribution P. is required to satisfy the following smoothness assumption, but can otherwise be arbitrary:
Assumption A (Smooth density). The noise distribution P2 has a smooth density d, C (R) (with corresponding CDF F2), with bounded derivatives: suPter lØ (x (t) < co for any 2 O. We further assume that (za) > O, where a (0.5,1) is our pre-specified quantile level, and Za := inf (t E R: 22 (t) 2 a} is the a-quantile of Ps.
Under the above model, it is straightforward to see that the true a-conditional quantile of y|x is also a linear model (with bias):
g. (x) = w x Za.
(5)
Given the training data {(x,, 9:)) learn linear quantile function f(xx w x + via quantile regression:
ww b) arg min R., (w, b) == Σ
(o) (w x, + 6)),
(6)
w.b
1=1
where eo is the pinball loss in (2). As linear function class realizes the true quantile function (5), the population risk is minimized at the true quantile: arg min Riw, b) = (w., Zx).
We are now ready to state our main result, which shows that quantile regression exhibits inherent under-coverage bias even in this vanilla realizable setting.
Theorem (Quantile regression exhibits under- cover-coverage bias). Suppose the data is generated from the linear model (4) and the noise satisfies Assumption A. Let f(x) w x + b be the output of quantile regression (6) at level E (0.5, 1). Then, in the limit of n, d - co and d/n -> k. where
E (0, ro) for some small kq 0, for the coverage (1), we have & denotes convergence in probability)
Coverage( () 2 a Co... for some Co.K > 0.
That is, the limiting coverage of the learned quantile function is less than Further, for small enough t we have the local linear expansion
Ca. = (a- - 1/2)x+ o(K).
+
'Our results can be extended directly any correlated Gaussian input N(O, Σ) by the transform X - 11/2 and w. = 1// We believe our results also hold for i..dd sub- Sub-Gaussian inputs by the universality principle (e.g. [14]).

---

Theorem builds on the precise characterization of ERM problems in the high-ding sigh-dimensional propor- tional limit [62], along with new techniques over existing work for dealing with the unique challenges in quantile regression (such as analyzing the additional learnable bias b). An overview of the main technical steps is provided Section 6, and the full proof deferred to Appendix C.
Implications Theorem can be illustrated by the following numeric example. Suppose we perform quantile regression at a = 0.9, where the data follows the linear model (4), and our y = d/n 0.1 (so that the sample size 10x number of parameters). Then Theorem shows that, even in this realizable, under- parametrizedd setting, the coverage of the learned quantile f is going to be roughly 0.9 Ca,x when n. are large, and further Ca, ~ (a 1/2) 0.04. Thus the actual coverage is around 0.9 - 0.04 = 0.86, and such a 4% under-coverage bias can be rather non-negligible in reality.
We remark that symmetric conclusion of Theorem also holds for lower quantiles, and we further expect similar results also hold for learning prediction intervals, where the coverage is defined as the two-sided coverage of the prediction interval formed by the learned (lower quantile, upper quantile). To the best of our knowledge, this offers a first precise theoretical understanding of why practically trained quantiles or prediction intervals often under-cover than the desired coverage level [53].
Comparison against existing theories An important feature of the under-coverage bias shown in Theorem 1 is that it only shows up in the n, d proportional regime, and is not implied by ex- isting theories quantile regression. Classical asymptotic theory only shows asymptotic normal- ity (n( b] [w., zal) + N(O, V) in the n + oc, fixed d limit [34, 64]. Under this limit, Coverage( (f) consistent at a with O(1/ deviation. Christmann and Steinwart [19], Steinwart al. [56] consider the finite n, d setting and establish self-calibration inequalities (similar to strong
convexity) that bounds the quantile estimation error by the square root excess loss v R(() - R(g;). Combined with standard generalization theories (e.g. via Rademacher complexities) and Lipschitz- ness, this can be turned into a bound on |Coverage( - all, but does not tell the sign (positive or negative) of the coverage bias.
Large n; extension to over-parametrized learning While Theorem requires small d/n, the approximation formula (7) suggests that the under-coverage should get more severe as k-the measure of over-parametriizaioon in this problem-gets larger. We confirm this trend experimentally in our simulations in Section 5.1.
As an extension to Theorem 1, we also show theoretically that the under-coverage bias indeed becomes even more severe in perrpparamerrized learning, under the same linear model (4): When d/n > ((1) and the noise Ps is sub- sub-Gaussian and symmetrically distributed about O, the convergence point of the gradient descent path on the quantile regression risk R., is the minimum norm interpolator of the data, which has coverage 0.5 + Õ(1/Vd) with high probability (see Appendix D for the formal statement and the proof). Notably, this 0.5 coverage does not depend on a and exhibits a severe under-coverage.
Understanding the source of the under-coverage bias
In this section, we take steps towards deeper understanding of how the under-coverage bias shown in Theorem happens. Recall that the quantile regression returns f(x) w T x + +6 where (w, b) is solution to the ERM problem (6) and estimates the true parameters (w., 2a). Our main approach in this section is disentangle the effect of the two sources the estimation error in d and the estimation error in on the coverage of
We show that the estimation error in b can have either an under-coverage or an over-coverage effect, depending on the noise distribution (Section 4.1). In contrast, the estimation error in w always has an under-coverage effect: this holds not only for the linear model assumed in Theorem but also on more general data distributions (Section 4.2). In the setting of Theorem 1, this under-coverage effect of w is always strong enough dominate the effect of b, leading to the overall under-coverage.
5

---

4.1 Effect of estimation error in
To study the effect of b, we use the quantity b Za as a measure for its effect on the coverage Recall that the true quantile is (x) = w x Za. thus having i < Za means that ò contributes to under-coverage, whereas b > zn means b contributes to over-coverage. (This can be seen more straightforwardly in the easier where know w, and only output b to estimate 2a.)
The following corollary shows that, under the same settings of Theorem the error ò - 2a can be understood precisely. The proof can be found in Appendix F.1.
Corollary (Effect of b on coverage depends on noise distribution). Under the same settings as Theorem I. for any E (0.5, 1), as n, d + oo with d/n + K E (0, Ku), we have
(a) The learned bias b from quantile regression (6) converges to the following limil:
byx o(K), b- za & C
where by has closed-form expression:
bo = ((1--)0s((a) (2a 1)03(za)
(8)
20d)
(b) For any a E (0.5, 1), when Ps is the Gaussian distribution (with arbitrary scale), we have by < O in which case Co,, 0 for small enough k. Conversely, for any a E (0.5, 1), there exists some noise distribution P. for which by > 0, in which case Ca > for small enough
Corollary 2 shows that the sign of Co aa, in the limiting regime (and thus the effect of on the coverage) the noise distribution P.. For common noise distributions
depends on by, which in turn depends such as Gaussian we have C a.x < 0 at small K, but there also exists P. such that C. o.x > Note that the second claim in part (b) follows directly from (8):
always design the density oz by
varying Φz (Za) and d', (Za) so that by O. Overall, this result shows that the coveracoverage bias in Theorem cannot be simply explained by the under-estimation error in b.
4.2 Effect of estimation error in w; relaxed data distributions
We now show that the primary source of the under-coverage is the estimation error in w, which happens not only on the linear data distribution assumed in Theorem but also on a broader class of data distributions. We consider the following relaxed data distribution assumption
y p. (x) + o. (x)2,
where the noise P.. We do put structural assumptions (Me,, ox), except that we assume the true a-quantile is still a linear function of x, that is, there exists (w., b.) for which
C (x) n4 (x) + ax (x) w + b..
(10)
Since here we are interested in the effect of estimating w.. for simplicity. we assume that we know b. and only estimate via some estimator w. We now collect assumptions and state the result. Assumption B (Relaxed data distribution). The data is distributed model (9) with linear quantile function (10). Further, the data distribution satisfies the following regularity conditions:
(a) The distribution of E Edd symmetric about 0, has a lower bounded covariance E[xx] 1 2 ILa and is -uuu-auussin,, for constants 7, K > O.
(b) The variance function a a.)-) is bounded and symmetric: For all x E Id we have a S 0,(x) S for some constants a, > O, and o (x) = o-(-x).
(c) The noise density 6z is continuously differentiable and symmetric about 0, iee. Φx(1) = (2(-) for all E R. Further, 6₂ is uni-modal, i.e. (t)())o > O and o' (t)sos 0.

---

(a) Coverage against
(b) Coverage against &. d/n
CAC
14
Figure 1: Coverage of quantile regression on simulated data from the realizable lincar model (4). (a)(b) Each dot represents combination of (a, k) and reports the mean and onc-std coverage over 8 random problem instances. (a) Coverage against the nominal quantile level for fixed values for fixed a E {0.8, 0.9, 0.95). Here "analytical" refers to our analyitical formula a Ca.s; and a 11---11-1 a/2) is its local linear approximation at small (both from Theorem 1).
d/n. (b) Coverage against
Theorem 3 (Estimation error in w leads to under-coverage on a family of data distributions). Under the relaxed data distribution assumption (Assumption B), for any a >> 3/4, there exists constants T x + b, with small estimation error ro > 0 such that for any learned quantile estimate f(x) = w W w.ll2 2 S To, have
Coverage a a -ac
- -w.l22
that is, the learned quantile under-covers by at least D(] w.1l)) Above, is an absolute constant, and ro > depends on (2), K, 22, a) but not (n, dn.d).
Implications; proof intuition Theorem shows that, for a broad class of data distributions, any estimator w will under-cover by at least S?( w w,ll If particular, any estimator satisfying || -w-ll2 = Ō( (d///) (e.g. from standard generalization theory) will under-cover by (dd/n). This confirms that the estimation error in the (bulk) regression coefficient w is the primary source of the under-coverage bias, under assumptions that are more general than Theorem in certain aspects (such the distribution of x and y/xx. We remark that as opposed Theorem Therorem 3 does not give an end-to-end characterization of any specific algorithm, but assumes we have an estimator W with a small error.
At a high-level, Theorem follows from the fact that any estimator w x + b, must be lower than the true quantile w w_'x+ 6, for some x and higher for some other x. Averaging the coverage indicator over such under-coverage and over-coverage cancel out on the first-order if x has a symmetric distribution, but aggregate to yield a under-coverage effect on the second-order long (t)(t) is concave (which holds if P- is unimodal). The proof of Theorem 3 can be found in Appendix E.2.
5 Experiments
5.1
Simulations
Setup We first test our Theorem 1 via simulations. We generate data from the linear model (4) in = 100 dimensions with ||w=ll2 and noise distribution P. = N(O. 0.25). We vary k = d/n E (0.02, 0.04...., 0.5) where x determines sample size n, and vary E (0.5, 0.52. ..., 0.98}.
For each combination of (a, k), generate 8 random problem instances, and solve the quantile regression ERM problem (6) on each instance via (sub)-gradient descent. We evaluate the coverage of the learned quantile f (thanks to the linear model (4), the coverage can be computed exactly without needing to introduce test set). Additional details about the setup can be found Appendix F.I.
Results Figure 1 plots the coverage of the learned quantiles. Observe that quantile regression exhibits under-coverage consistently across different values of (a) Figure Ia shows that at fixed k, the amount of under-coverage gets more severe at a higher which is qualitatively consistent with our approximation formula (a - 1/2)s. Figure 1b further compares simulations with our analytical formula Ca,x. (found numerically through solving the system of equations 12), as well as the
7

---

Table 1: Coverage (%) of quantile regression real data nominal level 0.9. Each entry reports the test-set coverage with mean and std over 8 random seeds. (d, v) denotes [feature dim, training examples).
Dataset
Linear
MLP---64
MLP-3-512
MLP-ffreee--i 3-512
d
πt
Community
88 1.53
76.461 1.41
63.09:1291
87.83=1.34
100
1599
Bike
89. 09.6
88.75=0..1
87.67:0.449
89.27=0.57
18
8708
Star
89.48+22.56
83.14#1.76
69.71=1.82
88.05=2.42
39
1728
MEPS_
90.09=00.22
85.46+0.96
78.55=0.93
89.03=0.51
139
12628
MEPS __
90.06=0.577
86.5220.65
80.77=0.72
89.60=0.28
139
14032
MEPS 21
89.99-10.39
83.7910.52
73.09
0936
139
12524
Nominal (ox)
90.00
90.00
90.00
90.00
local linear approximation a- (a- (a2m/ claimed in Theorem 1. Note that the simulations agree
extremely well with the analytical formula. The approximation a - (a 1/2) is also very accurate for almost all & 0.8, and accurate for small and suggests it holds at rather realistic values of the dimension (d 100).
0.9, 0.95. These verify our Theorem
5.2 Real data experiments
Datasets and models We take six real-world regression datasets: community and crimes (Community) [2], bike sharing (Bike) [1], Tennessee's s student teacher achievement ratio (STAR) [6], as well as the medical expenditure survey number 19 (MEPS_19 [3], number 20 (MEPS_20) [4], and number 21 (MEPS_2 __ [5]. All datasets are pre-processed to have standarized features and randomly split into a 80% train set and 20% test set.
To go beyond linear quantile functions, we perform quantile regression with one of the following four models as our fe: linear model (Linear), 3-layer MLP (two non-linear layers) with width 64 and variant of the width-512 MLP where all representation layers
MLP-3-64), 512 (MLP-3-513 are frozen and only the last linear layer is trained (MLP-freeze (f-freeeee--112) All linear layers include trainable bias. We minimize the a-quantile loss (3) via momentum SGD with batch size 64. For each setting, we average over random seeds where each seed determines the nallvvaiitttion split, model initialization, and SGD batching. In real experiments we fix 0.9. (Results at E {0.8, 0.95) as well as additional experimental setups can be found in Appendix F.2).
Results Table reports the coverage of the learned quantile functions (evaluated the test sets). Observe that all MLPs exhibit under-coverage compared with the nominal level 90%. Additionally, the amount of under-coverage correlates well with model capacity two vanilla MLPs under- covers more severely than the MLP-freeze and the linear model. Notice that the linear model does have a notable under-coverage on most datasets-we believe this a consequence of d/n being small on these datasets. The only exception is the Community ty dataset with the highest d/n z 1/16, on which the linear model does under-cover mildly by roughly 1%.
5.3 Linear quantile regression on pseudo-labels
To further test the coverage of linear quantile regression real data distributions, make two modifications: (I) We subset the training data by fixing and reducing n, so as to test the coverage across differerent values of k d/n; n (2) We compare linear quantile regression on both true labels yi. and aseudo-labet y peeudo generated from estimated linear models. These pseudo-labels are generated by first fitting a linear model w E ædd (with square loss) on the training data, and then generating new label using the fitted linear model W:
y pscudo
x; 0z:
where ă is estimated as V (Bx.wi [(y motivation for the pseudo-labels is to make sure that the data comes from a true linear model, removing the potential effect of model misspecification.
x)2] on a separate hold-out split, and 2; N(O, 1). The
Table shows that on the MEPS_20 20 dataset, linear quantile regression exhibits under-coverage at relatively large values of (0.1, 0.2, 0.5) for both kinds of labels. Also, there is no notable difference

---

between pseudo-labels and true labels. This provides evidence that our theory on linear quantile regression may hold broadly on real-world data distributions.
Table 2: Coverage of linear quantile regression on labels vs. pscudo-labels.
R: = d/n
0.01
0.02
0.05
0.1
0.2
0.5
MEPS_22 ___0
89.83=10.67
0.88
89.54400.2
88.7441..51
87.15+1.552
84.75+1..81
MEPS_22 Pseudo
90.05:+0.85
89.95=0.64
89.49-#0.64
88.90:+1.60
86.96-+1.30
83.70-+2.98
Nominal (a)
90.00
90.00
90.00
90.00
90.00
90.00
Proof overview of Theorem 1
Closed-form expression for coverage coverage. Recall that
Our first step obtain closed-fomm expression for the
Coverage = :=::=P(xxx)) ((x.x) f(x)) (x.x.) (ex.))((w,,) ((w,;)) + S (W,x) x) + +
As x is standard Gaussian, and the random variable = has cumulative distribution function 4.. standard calculation then yields the closed form expression (Lemma B.1)
Coverage( TEGG-N (I w. + D)).
Concentration of || - -w.ll and b We generalize results from recent advances in high- dimensional M-estimator in linear models [23, 20, 31, 62] to show that | w.ll2 and obtained by quantile regression 6 concentrates around fixed values in the high-ding nigh-dimensional limit. We show that, in the limit of d, oo and d/n the following concentration happens:
w w. 112 E (x),, and 2. (x)..
(11)
Above, T. and b, determined by the solutions of system of nonlinear equations with three variables (r, X, b):
- B...G. (TG 2;)) T =
TK X- A.G (). b (7G A;A)G,
(12)
0 = E(c,z)~N(0,) 1 (TG + Z: A)],
where <e(2;;) = min, 27 (x - u)² {(v) and = ( b) is the shifted pinball loss (2). (See Theorem C.1 for the formal statement.) This established via main steps: We first build on the results of Thrampoulidis et al. [62] to show that variant of the risk minimization problem with fixed bias b concentrates around the solution to the first two equations (12). We then develop novel concentration argument to deal with the additional learnable bias b in the minimization problem (6), which introduces the third equation in (12) that will used in characterizing the limiting value of the minimizer b.
The concentration (11) implies that Coverage (f) also converges to the following limiting coverage value (Lemma C.3):
Coverage(f) &s EG. bx))) =: a -C.k-
(13)
Calculating the limiting coverage via local linear analysis In this final step, another technical crux of the proof, we further evaluate the small approximation coverage value (13), and determine the sign of Ca.x- This is achieved by local linear analysis on the solutions of the aforementioned system equations at small x (Lemma C.2) in similar fashion as in [8], and precise analysis on the interplay between the concentration values b., and the noise density dz. Combining these calculations yields that Ca,z/K = (a 1/2) + o11) for small enough k. (Lemma C.4). As a > 1/2, this establishes Theorem I. All details these analyses can be found in proofs in Appendix C.

---

7 Conclusion
This paper presents a first theoretical justification the under-coverage bias quantile regression. We prove that quantile regression suffers from an inherent under-coverage bias even in well-specified linear settings, and provide a precise quantitative characterization the amount the under-coverage bias on Gaussian linear models. Our theory further identifies the high-dimensional estimation error in the regression coefficient as the main source of this under-coverage bias, which holds more generally broad class of data distributions. We believe work opens up several interesting directions for future work, such as analyzing non-linear quantile regression, as well as analyzing other notions of uncertainty in regression problems.
Funding transparency statement
YB, HW, CX are funded through employment with Salesforce.
References
[1] Bike sharing data set. https://archive http::ee.......c..eeooeeeeeeeeee http:///......a////a////aaaaaaaa dataset, Accessed: May, 2021.
[2] Communities and crime data set. http://archive. uei. www..edd/nl/daaaseeee commuitiies+andtrriine Accessed: May, 2021.
[3] Medical expenditure panel survey, panel 19, Accessed: May, 2021.
URL
https://neps... ahrq. http:///aappsaabr..ggoe/eeeeeeee httpp//seeeeaaaasstttttoooaooooa fata__iles___eeee_e_eeeeeeeeeeee j=p7choPPufluumbe::0---181
[4] Medical expenditure panel survey, panel 20. http:///a
Accessed: May,
2021.
[5] Medical expenditure panel survey, panel 21. http:://aags..rrrrggg///psssssts stats/domnload data wille__eetailjjpee. htt..//aeoeccottttbbebb--------- 192, Accessed: May, 2021.
[6] C. Achilles, H. P. Bain, F. Bellott, J. Boyd-Zaharias, J. Finn, J. Folger, J. Johnston, and E. Word. Tennessee's student teacher achievement ratio (star) project. Harvard Dataverse, 1:2008, 2008.
[7] A. Angelopoulos, S. Bates, J. Malik, and M. Jordan. Uncertainty for image classifiers using conformal prediction. arXiv preprint arXiv:2009. 14193, 2020.
Y. Bai, S. Mei, H. Wang, and C. Xiong. Don't just blame ree-paraaettiizaionn for confidence: Theoretical analysis of calibration in binary classification. arXiv preprint arXiv:2102.07856. 2021.
[9] R. F. Barber, E. J. Candes, A. Ramdas, and R. J. Tibshirani. Conformal prediction under covariate shift. arXiv preprint arXiv:1904.0m EEt::1904.0609,, 2019.
[10] R. F. Barber, E. J. Candes, A. Ramdas, and R. J. Tibshirani. The limits of distribution-fie conditional predictive inference. arXiv preprint 1903:::9900046880 2019.
[11] R. F. Barber, E. J. Candes, A. Ramdas, and R. J. Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-50 00448665077200 2021.
[12] S. Bates, A. Angelopoulos, I.. Lei, Malik, and M. I. Jordan. Distribution-free, risk-controlling prediction sets. arXiv preprint arXiv:2101.0277 2021.
[13] M. Bayati and A. Montanari. The dynamics of message passing dense graphs, with appli- cations to compressed sensing. IFEE Transactions on Information Theory, 57(2):764-785, 2011.
10

---

[14] M. Bayati, M. Lelarge, A. Montanari, et al. Universality in polytope phase transitions and message passing algorithms. Annals of Applied Probability, 25(2):753-88) 2015.
[15] E. Begoli, T. Bhattacharya, and D. Kusnezov. The need for uncertainty quantification in machine-assisted medical decision making. Nature Machine Intelligence, 1(1):20-23, 20, 2019.
[16] E. J. Candès, Sur, et al. The phase transition for the existence of the maximum likelihood estimate in high-dimensional logistic regression. The Annals of Statistics, 48(1):27-42, 2020.
[17] M. Cauchois, S. Gupta, A. Ali, and J. C. Duchi. Robust validation: Confident predictions even when distributions shift. arXiv preprint arXiv:2008. 04267, 2020.
[18] M. Cauchois, S. Gupta, and J. C. Duchi. Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction. Journal of Machine Learning Research, 22(81):1 2021.
[19] A. Christmann and I. Steinwart. How swms estimate quantiles and the median. In Advances in neural information processing systems, pages 305-312, 2007.
[20] D. Donoho and A. Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. Probability Theory and Related Fields, 166(3):935-969 2016.
[21] D. L. Donoho, A. Maleki, and A. Montanari. Message-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences, 106(45))18914418119 2009.
[22] D. Dua and C. Graff. UCI machine learning repository, 2017. URL http://archiie. uci. adu/ml.
[23] N. El Karoui, D. Bean, P. J. Bickel, C. Lim, and B. Yu. On robust regression with high- dimensional predictors. Proceedings of the National Academy of Sciences, 110(36):14577- 14562, 2013.
[24] Y. Gal and Z. Ghahramani. Dropout bayesian approximation: Representing model uncer- tainty in deep learning. In international conference on machine learning, pages 1050-1059, PMLR, 2016.
[25] S. Geisser. The predictive sample reuse method with applications. Journal of the American statistical Association, 70(350):320-322 1975.
[26] C. Guo, G. Pleiss. Y. Sun, and K. Q. Weinberger. On calibration of modern neural networks. arXiv preprint arXiv: 700.04590
[27] C. Gupta, A. Podkopaev, and A. Ramdas. Distribution binary classification: prediction sets, confidence intervals and calibration. arXiv preprint arXiv:2006.10564 2020.
[28] G. Huang, Y. Li, G. Pleiss, Z. Liu, J. E. Hopcroft, and K. Q. Weinberger. Snapshot ensembles: Train 1, get m for free. arXiv preprint arXiv: 1704. 00444.00199, 2017.
[29] X. Jiang, M. Osl, J. Kim, and L. Ohno-Machado. Calibrating predictive model estimates to support personalized medicine. Journal of the American Medical Informatics Association, 19 (2):263-274, 2012.
[30] C. Jung, C. Lee, M. M. Pai, A. Roth, and R. Vohra. Moment multicalibration for uncertainty estimation. arXiv preprint Xiiv:2008.08037 2020.
[31] N. E. Karoui. Asymptotic behavior of unregularized and ridge-regularized high- robust regression estimators: rigorous results. arXiv preprint urXiv:1311.24455 2013.
[32] A. Kendall and Y. Gal. What uncertainties do need in bayesian deep learning for computer vision? arXiv preprint arXiv: 2017.
[33] D. Kivaranovic, K. D. Johnson, and H. Leeb. Adaptive, distribution-fres prediction intervals for deep networks. In International Conference on Artificial Intelligence and Statistics, pages 4346-4356. PMLR, 2020.
11

---

[34] R. Koenker and G. Bassett Jr. Regression quantiles. Econometrica: journal of the Econometric Society, pages 33-50, 1978.
[35] R. Koenker and K. F. Hallock. Quantile regression. Journal of economic perspectives, 15(4): 143-156, 2001.
[36] A. Kumar, P. Liang and T. Ma. Verified uncertainty calibration. arXiv: 10155 2019.
arXiv preprint
[37] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. arXiv preprint arXiv:6612.01474, 2016.
[38] Lei. Classification with confidence. Biometrika, 101(4):755-769) 2014.
[39] J. Lei, M. G'Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 1136623):109411111 2018.
[40] L. Liu, M. Simchowitz, and M. Hardt. The implicit fairness criterion of unconstrained learning. In International Conference on Machine Learning, pages 4051-4060. PMLR, 2019,
[41] D. C. Mackay, Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
[42] W. J. Maddox, P. Izmailov, Garipov, D. P. Vetrov, and A. G. Wilson. simple baseline for bayesian uncertainty in deep learning, Advances in Neural Information Processing Systems, 32: 13153-13164, 2019.
[43] X. Mai, Z. Liao, and R. Couillet. A large scale analysis logistic regression: Asymptotic performance and new insights. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3357-3361. IEEE, 2019.
[44] A. Malinin and M. Gales. Predictive uncertainty estimation via prior networks. arXiv preprint /802 10501, 2018.
[45] A. Malinin, B. Mlodozeniee, and M. Gales. Ensemble distribution distillation. arXiv preprint arXiv:1905.00076 2019.
[46] N. Meinshausen. Quantile regression forests. Journal of Machine Learning Research, 7(35): 983-999, 2006.
[47] R. Michelmore, M. Kwiatkowska, and Y. Gal. Evaluating uncertainty quantification in end-to- end autonomous driving control. arXiv preprint arXiv:18/1.068177 2018.
[48] F. Orabona. Accessed: May. 2021.
Last iterate of sgd converges (even in unbounded domains), 2020;
URL https://parametertee wttp://rrrreeeeeoo////////////// last cest-iterate-of-ee converges-even. in- un-unbounded dosaadddoomann//......
[49] Y. Ovadia, Fertig, Ren, Z. Nado, D. Sculley, S. Nowozin, J. V. Dillon, B. Lakshminarayanan. and J. Snoek. Can you trust your model's 's uncertainty? evaluating predictive uncertainty under dataset shift. arXiv preprint arXiv: (tte::9900.055333 2019.
[50] H. Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools in artificial intelligence. Citeseer, 2008
[51] J. Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. 1999.
[52] M. H. Quenouille. Approximate tests of correlation time-series. Journal of the Royal Statistical Society: Series B (Methodological), (1(1):6-844, 1949.
[53] Y. Romano, E. Patterson, and Candès. Conformalized quantile regression. arXiv preprint 1xXiv:190..03222, 2019.
12

---

[54] E. Shabat, L. Cohen, and Y. Mansour, Sample complexity of uniform convergence for multicali- bration. arXiv preprint arXiv:2005.01757, 2020.
[55] G. Shafer and V. Vovk. tutorial on conformal prediction. Journal of Machine Learning Research, 9()), 2008.
[56] I. Steinwart, A. Christmann, et al. Estimating conditional quantiles with the help of the pinball loss. Bernoulli, 17(1)2211-225, 2011.
[57] M. Stojnic. framework to characterize performance of lasso algorithms. arXiv preprint arXiv:1303.7291, 2013.
[58] M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society: Series B (Methooologicall, 36(2):1111133 1974.
[59] P. Sur and J. Candès. A modern maximum-likellhove theory for high-dlimensionll logistic regression. Proceedings of the National Academy of Sciences, 116629)114516-14555 2019.
[60] I. Takeuchi, Q. V. Le, D. Sears, and A. J. Smola. Nonparametric quantile estimation. Journal of Machine Learning Research, 7:1231- 2006.
[61] C. Thrampoulidis, S. Oymak, and B. Hassibi. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pages 1683-1709. PMLR, 2015.
[62] C. Thrampoulidis, E. Abbasi, and B. Hassibi, Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory, 64(8) 5628, 2018
[63] Tukey. Bias and confidence in not quite large samples. Ann. Math. Statist., 29:614, 14, 1958.
[64] A. W. Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
[65] R. Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[66] V. Vovk. Conditional validity of inductive conformal predictors. Asian conference on machine learning, pages 475-490. PMLR, 2012.
[67] V. Vovk. Cross-conformn predictors. Annals of Mathematics and Artificial Intelligence, 74(1): 9-28, 2015.
[68] V. Vovk, A. Gammerman, and G. Shafer. Algorithmic learning in a random world. Springer Science & Business Media, 2005.
[69] V. Vovk, I. Nouretdinov, V. Manokhin, and A. Gammerman. Cross-conformal predictive distributions. In Conformal and Probabilistic Prediction and Applications, pages 37-51. PMI.R 2018.
[70] S. S. Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathe- matical Statistics, 12(1):91-96, 1941.
[71] S. S. Wilks. Statistical prediction with special reference to the problem of tolerance limits. The annals of mathematical statistics, 13(4):400-409 1942.
[72] B. Zadrozny and C. Elkan. Obtaining calibrated probability estimates from decision trees and naive bayesian classifiers. Citeseer.
[73] B. Zadrozny and C. Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694-699, 2002.
13


Reviews:
[{"review_id": "thLBKPn9Ole", "reviewer": "Reviewer_sjsB", "summary": "This paper presents a theoretical study on the coverage of quantile regression algorithms. More specifically, the authors prove theoretically that linear quantile regression exhibits an inherent under-coverage bias, with an order d/n difference in the marginal coverage regardless of the noise distribution (but Gaussian for the covariates). They also show that the primary source of this under-coverage bias is the estimation error in the linear coefficients, while the estimation error in the bias term can have either an under- or over-coverage effect. Numerical experiments further support their findings.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Quality and Significance:\n\nPros: The authors give a clear contribution in explaining the under-coverage phenomenon in linear quantile regression. The analysis, as the authors claim, is unlike existing results in that it captures the sign of the bias, and is the first rigorous theoretical justification on the under-coverage phenomenon. The study can open up more research questions along this line.\n\nCons: The biggest limitation seems to be that only the classical linear quantile regression algorithm with pinball loss is analyzed, and it is unclear whether the insight is generalizable. As the authors are aware, there are many advanced uncertainty estimation algorithms (e.g., conformal-prediction-based approaches, quantile regression forests etc.), and the paper would be much stronger if similar insights could be drawn to these advanced approaches. For instance, the bias term which can have either under- or over-coverage effect seems to be very specific to the linear model, and it is unclear any generalization of such insights could be drawn to other models. \n\nRelated to above, a relatively milder concern is that Theorem 1 requires that both n and d go to infinity. I don't know how easy/meaningful it is to \"model\" an increasing data dimension beyond linear (although I understand the authors' motivation in letting d go to infinity to highlight the nontrivial impact of the under-coverage bias).\n\n\nClarity:\n\nThe paper is well-written. It is easy to read and understand the main theorems, and intuitions are well presented.\n\nIn line 192, “the over-coverage should get more severe as κ—the measure of over-parametrization in this problem—gets larger”. Should “over-coverage” be under-coverage bias?\n\n\nOriginality:\n\nThe authors present a rigorous theoretical study on the under-coverage of uncertainty estimation algorithms in learning quantiles, focusing on linear quantile regression. The analysis giving rise to the sign of the coverage bias seems novel.\n\nOn the other hand, except for the sign of the coverage bias, the finite-sample estimation error of linear quantile regression is well-studied, e.g., in Steinwart et al., 2011. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors only study linear quantile regression under specific assumptions, and the theoretical results are viewed as somewhat restrictive. On the other hand, it sets up a good direction and opens up new questions to explore. This paper is mostly a theoretical work and I do not foresee any negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "lYA2RwVKMX6", "reviewer": "Reviewer_FCrS", "summary": "In this work, the authors consider linear quantile regression, paying particular attention to the \"coverage\" properties of the resulting predictor. The traditional goal of quantile regression is to learn a quantile of the conditional distribution of output $Y$, conditioned on the inputs $X$. Denoting the predictor returned by any quantile regression algorithm by $\\hat{f}(\\cdot)$, one can use this to construct a predictive interval for a freshly-drawn $Y$. The authors consider the one-sided interval $C(X) = (-\\infty, \\hat{f}(X)]$, and the event $\\\\{ Y \\in C(X) \\\\}$. The authors call the probability of this event (over the draw of a pair $(X,Y)$) the coverage of $\\hat{f}$. Their main results elucidate conditions under which the traditional pinball-loss based ERM quantile regression solution is biased below the desired quantile level, that is, the predictive interval tends to be \"too small,\" due to $\\hat{f}$ under-estimating the desired quantile.\n\nIn particular, they show that in the limit where the sample size and dimensionality are proportional, the coverage (the aforementioned probability, which depends on $\\hat{f}$ and thus the training data) converges below the desired quantile, with this error depending directly on the ratio of dimension to sample size $d/n$. Furthermore, they show (under fixed $n$ and $d$) how for a certain family of data distributions and a linear quantile model, given any estimator of the weights, the downward bias term scales with the weight estimation error. Their empirical tests also effectively highlight the phenomena described formally.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is quite clearly written, easy to follow, and the authors describe their contributions in a transparent fashion. My only reservations are related to the significance of the results, particularly for the machine learning community. As the authors mention, there are plenty of ways of getting around the aforementioned under-estimation bias, and in the context of \"uncertainty estimation,\" it is arguably more common to use quantile regression as a sub-routine in a larger conformal prediction type of procedure,  rather than to pay particular attention to the coverage of the quantile regressor itself. The results here are of a fundamentally statistical nature, which I still think is fine for NeurIPS, but considering that quantile regression is a now-classical and well-studied topic, I would be surprised if similar insights did not already exist in the statistics literature, but I am not sufficiently familiar with that literature. Taking these points together, my recommendation is a borderline accept.\n\n**Update:**\nI thank the authors for their response. Having read through the authors' response and the other reviews, my overall opinion remains unchanged.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "cuWsBd_GgQ", "reviewer": "Reviewer_bjfV", "summary": "This paper gives theoretical insights into the under-coverage phenomenon often observed in quantile regression, i.e., for a continuous distribution, the probability of observing  a true label below a learned  $\\alpha$-quantile is often below $\\alpha$, which is consider a failure in estimating the uncertainty.\nTwo important results are shown. The first one provides a characterization of the under-coverage in the setting of a Gaussian linear model in the under-parameterized high-dimensional proportional limit (i.e. $d,n \\rightarrow \\infty$ , $d/n\\rightarrow\\kappa$ with small $\\kappa$) independently of the noise distribution.\nThe experimental results show that the formulas match pretty well the observed coverage in realistic situations of dimension around 100, on synthetic and real data.\nThe second important result shows that the source of the under-coverage stems essentially from the error in estimating the high-dimensional linear coefficient, under some assumptions on the underlying source.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: As far as I know, the analysis is new and sheds light on a known but unexplained phenomenon. It builds on recent advances in high-dimensional  M-estimation but introduces a novel concentration argument to deal with the additional learnable bias, which was not considered in previous works.\n\n**Quality**: This paper is a complete and sound piece of work addressing an important problem of quantile regression.I am not familiar with all the technical elements of the proofs in the Appendix, so I can't say too much about their correctness.  The proof overviews in the main text are helpful.  The noise smoothness assumptions of the main theorem seem reasonable and those of theorem 3 allow to consider more general data distributions. The experimental results nicely match the proposed theory in realistic situations.\n\n**Clarity**: The paper is very well organized and written which makes it very pleasant to read. There is a very  good literature review that positions it with respect to prior work.\n\n**Significance**: these results will be of interest for the machine learning communities working on quantile regression to potentially build on these results and extend them to more general settings.\n\n\n**Minor comments:**\n\nAssumption A should specify what is $\\alpha$ , is it $\\alpha\\in(0.5,1)$  ?\n\nLine 162:  \"small\" should be more precise\n\nLine 192: I think it should say \"under-coverage\" instead of \"over-coverage\"\n\nLine 245: K-sub-Gaussian should be defined\n\nLine 252: \"small\" should be more precise\n\nReferences:\narXiv versions should be replaced by their peer-reviewed versions when possible, e.g.:\n\nY. Romano, E. Patterson, and E. J. Candès. Conformalized quantile regression. arXiv preprint\n471 arXiv:1905.03222, 2019.\n\n[57] is incomplete\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are clearly related to the mathematical assumptions and are properly discussed.  They are reasonable to show this kind of results and do not make them less relevant or interesting for future research. \n\nThe authors do not foresee any negative societal impact of this work because\nit is a theoretical paper on understanding existing uncertainty estimation algorithms.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "T2GOgDvgGMX", "reviewer": "Reviewer_SQgW", "summary": "Quantifying predictive uncertainty is a crucial task for high-stakes prediction problems. The paper focus on quantile regression, a common approach for quantifying predictive uncertainty in regression problems. Authors consider realizable linear setting when the true model belongs to the considered functional class. With a focus on the under-parameterized setting, they theoretically justify the under-coverage of the learnt quantile regressors. Established theoretical results are backed up with supporting empirical evidence.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written making it easy to follow for a non-expert in the area. The authors discuss the ways in which the results presented in the paper differ from the ones available in the literature. The main contribution of the paper is on the theoretical side, and it seems quite interesting and convincing. While pure reliance on prediction intervals constructed through learning two separate quantiles could be unfounded (which particularly motivated applying conformal techniques for performing appropriate corrections), studying the nature of the underlying biases, even in simplified settings, is important.\n\nCouple of minor typos:\n--- line 98 --> with quantile regression to correct ITS coverage bias\n--- line 192  --> under-coverage?\n--- line 215 --> $w_\\star^\\top x + z_\\alpha$ should be present instead of $w_\\star^\\top + z_\\alpha$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention the limitations of a simplified setting considered in the work. Still, it would be nice to have a more detailed discussion section (with more focus on the impact of the established results). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This article provides a theoretical explanation for the empirical observation that quantile regression tends to exhibit an under-coverage bias, in the sense of frequentist coverage of prediction intervals.  The theory shows that this under-coverage stems from the error in estimating high-dimensional parameters when the number of parameters $d$ grows proportionally with the sample size $n$.  An explicit formula for the bias is provided (Eqn 7) in the case of a linear Gaussian model when $d/n$ is small, under quite general conditions on the noise distribution.  This under-coverage occurs even in the well-specified setting of learning a linear quantile function when the true data distribution follows a linear Gaussian model.  The theory is validated in empirical experiments on simulated and real data.

The paper is well-written and successfully addresses an important problem in a compelling way.  To my knowledge, the results are novel.  The reviews were consistently positive, and I believe the paper provides a valuable contribution to the literature.  The experimental results on neural networks (e.g., in Table 1) are particularly interesting and relevant to the NeurIPS community.

The main limitation (as mentioned by Reviewer sjsB) is that the analysis considers only the classical linear quantile regression algorithm with pinball loss.  It would be interesting to extend the results to more advanced algorithms.  However, this is a minor limitation and the paper opens up directions of future research into such extensions.

Decision: Accept (Spotlight)