Distribution-free inference for regression: discrete, continuous, and in between
Authors: Yonghoon Lee
Rina Barber
Venue: NeurIPS 2021 Poster (2021)
Keywords: distribution-free inference
nonparametric inference

Abstract: In data analysis problems where we are not able to rely on distributional assumptions, what types of inference guarantees can still be obtained? Many popular methods, such as holdout methods, cross-validation methods, and conformal prediction, are able to provide distribution-free guarantees for predictive inference, but the problem of providing inference for the underlying regression function (for example, inference on the conditional mean $\mathbb{E}[Y|X]$) is more challenging. In the setting where the features $X$ are continuously distributed, recent work has established that any confidence interval for $\mathbb{E}[Y|X]$ must have non-vanishing width, even as sample size tends to infinity. At the other extreme, if $X$ takes only a small number of possible values, then inference on $\mathbb{E}[Y|X]$ is trivial to achieve. In this work, we study the problem in settings in between these two extremes. We find that there are several distinct regimes in between the finite setting and the continuous setting, where vanishing-width confidence intervals are achievable if and only if the effective support size of the distribution of $X$ is smaller than the square of the sample size.


Distribution-free inference for regression: discrete, continuous, and in between
Yonghoon Lee Department of Statistics University of Chicago Chicago, IL 60637 yhoony31@uchi hatpsteechhcaaae cago. edu
Rina Foygel Barber Department of Statistics University of Chicago Chicago, IL 60637 rina@uchicago edu
Abstract
In data analysis problems where we are not able to rely on distributional assump- tions, what types of inference guarantees can still be obtained? Many popular methods, such as holdout methods, cross-validation methods, and conformal pre- diction, are able provide distribution-free guarantees for predictive inference, but the problem providing inference for the underlying regression function (for example, inference on the conditional mean EE [X] is more challenging. In the setting where the features X are continuously distributed, recent work has estab- lished that any confidence interval for E [Y| must have non-vanishing width, even as sample size tends to infinity. At the other extreme,
takes only small number of possible values, then inference on E Y [X] trivial to achieve. In this work, we study the problem in settings in between these two extremes. We find that there are several distinct regimes in between the finite setting and the continuous setting, where vanishing- width confidence intervals are achievable if and only if the effective support size of the distribution of X is smaller than the square of the sample size.
Introduction
Consider a regression problem, where our aim is to model the distribution of a response variable Y E (X,,, Yn).
R based on the information carried by features X X. Given training data we aim to build fitted model to estimate the conditional distribution of Y X, or some summary of this distribution such as the conditional mean or conditional median. In this type of setting, our goals are to simultancously perform two tasks, estimation and inference-that is, we want to accurately estimate the conditional distribution, and also about this estimate.
reliable way of quantifying our uncertainty
To make this concrete, suppose the training data {(X,, Yi) are drawn i..d. from some unknown distribution P on Rd x IR, and we want to estimate the true conditional mean, (x) := E [ = x). of this distribution. Given the training data, we construct a fitted regression function ñ Rd + IR using any algorithm, for instance, a parametric method such as least squares procedure such as a Gaussian kernel method. For many regression algorithms, assuming certain conditions on the underlying distribution P will ensure an accurate estimate of jır; however, unless we are able verify these assumptions, we cannot be confident that the corresponding error rates will indeed lead valid confidence interval for jup. The goal of distribution inference is to provide inference guarantees in this case, confidence intervals for pp(( (Xx+1) at newly observed feature vector X,-I-th that are valid universally over any underlying distribution P.
nonparametric
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

1.1 Our contributions
In this work, we study the problem of constructing a confidence interval (z)x) for pr(z), that satisfies the following property:
Definition 1.
An algorithm Ö, provides distribution-free ---offideeecc interval for the conditional mean if it holds that
P (X. { (pp(X++1) E (x(t1)))) 2 1 a for all distributions P on (X,Y) E R x [0.1]. 1].
Here the probability is taken with respect to the distribution of both the training data (I),Y)..... (Xn, Yn) and the test point (Xn+1, Yn+1), all drawn i.i.d. from an arbitrary P
Recent work by Vovk et al. 2005 Barber 2020]_ Gupta et al. 2020 (studying the conditional mean of binary response Y) and by Medarametla and Candès| [021 (studying the conditional median of a vellev Y) proves that distribution free coverage properties similar to Definition Iead to fundamental limits on the accuracy of inference. Writing Px to denote the marginal distribution of X under P. these results show that if Px is nonatomic (meaning that there are no point masses, i.e., Fryx (X =} O for all points E Rd), then any distribution-free confidence interval On cannot have vanishing length as sample size n tends to infinity, regardless of the smoothness of P. or any other "nice" properties of this distribution. Specifically, these works show that if Px is nonatomic, then C₂ must also be a valid predictive interval, i.c., must contain Y Y2+1 itself with probability 2 1-1000 a. This implies that the length of Ön cannot be vanishing, since Yn+1 is inherently noisy. An explicit lower bound on the length is proved in Barber (2020).
Our new results examine the possibility of constructing confidence intervals C, that are both distribution-free (Definition[] I and have vanishing length, when Px may be discrete, nonatomic, or a mixture of the two. We find that the hardness of this problem can be characterized by the effective support size of e's-estetilllyy, how many points x E Rd needed to capture most of the mass of Px (for example, if Px is uniform over M points, then its effective support size is S M).
Our main theoretical results show that there two regimes. If the effective support size is >> n². then Px essentially behaves like a nonatomic distribution because in sample of size n, with high probability all the X values are observed at most once; in this regime, we find that the average length of (X,,1) is bounded away from zero, i.e., no distribution-free confidence interval can have vanishing length. If instead the effective support size is < n², then it becomes possible for M1/4 (X...) to have vanishing length, and in particular, the minimum possible length scales as n:77 for effective support size M. Interestingly, vanishing length is possible even when M is larger than n, meaning that distribution-free inference for E X|] possible even if most X values were never observed in the training set.
1.2 Additional related work
The problem of distribution inference has been studied extensively in the context of predictive inference, where the goal is to provide a confidence band for the response value Y,+1 given a new feature vector Xx+1- The prediction problem is fundamentally different from the goal of covering the conditional mean. In particular, by splitting the data and using a holdout set, we can always empirically validate the coverage level of any constructed predictive band. Methods such as conformal prediction (see, e.g.. Vovk et al. [2005], PapadooppPssssssss et al. [2002] Lei et al. [2018] 8] Vovk al. (2088) or jackknife+ [Barber et al. 2021 Kim al. 2020) can ensure valid distribution- free predictive inference without the need to split the data set (thus avoiding reducing the sample size).
As mentioned earlier, Vovk al. 2005 Barber 2020 , Gupta et al. 20200 Medarametla and Candès (2021) also study the problem of confidence intervals for the conditional mean or median of YIX, establishing impossibility results the setting of nonatomic Px. These results are connected to earlier results on the impossibility of adaptation to smoothness, in the nonparametric inference specifclr if up 3-Hölder smooth, then it is possible to build confidence interval of
In this definition and throughout our work. C. can be either a deterministic or randomized function of the training data; if the construction is randomized then the definition above should be interpreted as computing probability with respect to the distribution of the data and the randomization of the construction.

---

length Onn " if is known (e-g., using k-nearest-neiighbors with appropriately chosen k:), but this cannot be achieved when 3 is unknown (see, e.g., Giné and Nickl 2016 Section 8.3] for an overview of results of this type).
While the results above establish the challenges for distribution- inference when the features X nonatomic, at the other extreme we consider scenarios where X has discrete distribution. In this setting, the problem of estimating μip related to the discrete distribution testing. where the aim is to test properties of a discrete distribution for instance,
might wish to test equality of two distributions where we draw samples from each [Chan et al. 2014 Acharya et al. 2014 Diakonikolas and Kane 2016 Canonne al. 2013]; to test whether sample drawn from known distribution P or not Diakonikolas and Kane 2016 Acharya et al. 2015 Valiant and Valiant 2017 Diakoninko
class P or not [Acharya et al. [0155] Canonne et al. 2018); or to estimate certain characteristics of a distribution such as its entropy or Acharya et al.) [014]. The distribution-free confidence intervals we will construct in Section are closely related to methods developed in this literature.
al. 2018]. or drawn from any distribution belonging
support size [Valiant and Valiant 20 TT
Main results: lower bound
Before presenting our main result, we begin with several definitions. For any distribution Px on X E IR we first define the effective support size of Px at tolerance level E [0,1):
(Px) = min {|x] : X C Rd and Ppx {X E ( 2
where | denotes the cardinality of the set X' In particular, if Px is distribution supported on M points, then M,, (Px) S M for any y. If instead Px is nonatomic, then M,, = for all 7 > We note that, in many practical settings, the effective support size (Pxx) may be substantially smaller than the overall support size. For example, if X E Rd measures dl categorical covariates with my possible values for the jth covariate, then the support of Px is potentially large IT;= mj. which will grow extremely rapidly with the dimension d even if each my is small; in real data, however, may be the case that most combinations of covariate values are extremely unlikely, and so the effective support size M,(P) would be substantially smaller, and might grow more slowly with d.
Next, for any distribution P on (X,Y) Rd x [0, 1], we define
P. the --quantile of Varp (YIX), under the distribution ~ Px.
With these definitions in place, our first main result establishes lower bound on the expected length of any distribution- confidence interval Čz-- Let Leb denote the Lebesgue measure on R.
Theorem 1. Fix any a > O, and let On be a distribution-free (1 - ->-oofiidence interval (i.e., satisfying Definition 7. Then for any distribution P on Rd x R. for any 3 > 0 and y > a + 3,
(Mx( 1/2
E Leb (Cu(Xx+1))] 1op.o - -a -B)1 min
where the expected value is taken over data points (X,, Y2) id Po i I...., 1.
2.1 Special cases
To help interpret this result, now examine its implications in several special cases.
Uniform discrete features If Px is a uniform distribution over M points, then for any 7 > the effective support size is (Px) = [[1 M) Therefore, Theorem | iiplies that for any P with nonatomic marginal Px.
E [Leb (Cn(Xn+1))) 10 a 11 0.20. min
{
1/4 1/2
for any 3 E (0, - a). In particular, we see that M > n² implies constant lower bound on the width of any distribution-free confidence interval, while M & n² allows for the possibility of vanishing width for distribution-free confidence interval.
3

---

Binary response If the response Y is known to be binary (i.e., Y E {0. we might relax the requirement of distribution- coverage only include distributions of this type, i.e, we require
(X. (pr(Xx+1) E (X 2 a for all distributions P on Rd x (0.1).
(1)
This condition is strictly weaker than Definition where the coverage property is required to hold for all distributions P on Rd x [0, 1), i.e., for a broader class of distributions. However, it turns out that relaxing the requirement does not improve the lower bound. Specifically, we have an algorithm to construct a confidence interval C₂, satisfying ( then we can easily convent On into a method that does satisfy Definition | Given data (X1, ....... (Xn, Yn), for each i = I....,P draw binary response Y; ~ Bernouli(YY). Then we clearly have n ii.d draws from a distribution on (X.Y) E Rd x {0, 1). where E[(Y | x = E x] = (x After running our algorithm construct C, the new data (X1, Yi)...., (Xn; Y.), the binary distribution-free coverage property ① satisfied by Cn ensures that this modified procedure satisfies Definition
To summarize, then, we see that the problem of distribution-free coverage is equally hard for the binary response case (Y {0, 13) for the more general bounded response case (Y 1)).
Nonatomic features We now consider the setting where the marginal distribution of X is nonatomic, i.c., Px {X = x} for all æ. (In particular, this includes the continuous case, where X has continuous distribution on R In this case, for any y 0 the effective support size is M, [x)) = cc. Therefore, Theorem iimplies that for any P with nonatomic marginal Px, for any E (0, a))
E Leb (Cn(Xn+t))] 2 a1-a B)
- a
In particular, this lower bound does not depend on n, and so the width of any distribution confidence interval is non-vanishing even for arbitrarily large sample size n (as long as 02,3 > 0).
In case of a binary response. where P is a distribution on Rd x {0, 1} with nonatomic marginal distribution Px, BBrber (2200) establishes that any distribution-fres confidence interval for μ must satisfy a lower bound that is a function only of and does not depend on n (and, in particular, does not vanish as oc). In this sense, our result can be viewed generalization of this work, since the nonvanishing minimum length for nonatomic Px is consequence of our result.
2.2 Adding knowledge of Px
One way might try to weaken the notion of distribution- -free coverage would be allow as- sumptions about the marginal distribution Px, while remaining assumption-frea for the function pop determining the conditional mean. In other words, we might weaken Definition [ to require coverage over all distributions P for which Px Px for a known P (or, all P for which Px satisfies some assumed property). Interestingly, the lower bound in Theorem I remains the same even under this milder definition of validity-we will see in the proof that knowledge of Px does not affect the lower bound, since the argument relies only on our uncertainty about the conditional distribution of Y YJX.
2.3 Bounded unbounded?
The lower bound established in Theorem assumess distribution-fied coverage for distributions with bounded response that is, Definition T requires coverage to hold for distributions where the response Y is supported on [0, 1] (although no other assumptions are placed on P). Would be possible for us to instead consider the general case, where P is an unknown distribution on IR x R?? The following result shows that this more general question is not meaningful:
Proposition 1. Suppose an algorithm On satisfies
(X.,x)fer {up(Xn+i) E (a(Xn+t) 2 21-a a for all distributions on RRd R.
Then for all distributions P. for all y E IR it holds that
P (Xx,Y))Pp {ur T Cn (x(xtt)))) 2 -a. a.

---

This means that if we require Cn to have distribution feeributtion-fre coverage over distributions with unbounded response, then inevitably, every point in the real line is contained in the resulting confidence interval substantial portion of the time. (In particular, C₁ (Xn+1) will of course have infinite expected width.) Clearly unbounded Y cannot result in any meaningful distribution- free inference, and for this reason we therefore restrict our attention to the setting where the response Y takes values in [0, 1] (of course, these results can easily generalize to Y [a. for any known < b).
3
Main results: upper bound
We next construct an algorithm that, for certain "nice" distributions P. can achieve confidence interval length that matches the rate of the lower bound. Our procedure requires two main ingredients as input:
1. A hypothesized ordered support set {-((1), ( ..... C 12d for the marginal Px, and 2. A hypothesized mean function μr Rd + [0, 1].
One possible way of obtaining these inputs would be to use data splitting, where one portion of our data (combined with prior knowledge if available) is used construct hypothesized support set and mean function, and the second portion of the data is then used for constructing the confidence interval (note that the sample size n in our construction below refers to the size of this second part of the data, e.g., half of the total available sample size). Any algorithm can be applied for estimating for example, logistic regression, nearest neighbors regression, or a neural network.
We emphasize that the coverage guarantee provided by our method does not rely in any way on the accuracy of these initial guesses the constructed confidence interval will satisfy distribution-fia validity (Definition D even if these initial parameters are chosen in a completely uninformed way. In particular, while the algorithm that fits μ might be able guarantee accuracy of μ under some assumptions placed on P, the validity of our inference procedure does not rely on these assumptions. However, the length of the resulting confidence interval will be affected, since high accuracy in these initial guesses can be expected to result in a shorter confidence interval. In particular, the hypothesized support set (z(1), (,)))... should aim to list the highest- probbbbiip values X early in the list, while the hypothesized mean function μ should aim to be close to the true conditional mean μ as possible. (Our theoretical results below will make these goals more precise.)
Given the hypothesized support and hypothesized mean function, to run our algorithm, we first choose parameters 7,8
satisfying 7 + 8 < a, and then compute the following steps.
Step 1: estimate the effective support size. First, we compute an upper bound on the support size needed to capture --y of the probability under Px,
M, = min m Σ 1 f ..... (.....,.mmm))) 2 21 - (1->)n +
n log(2/6)
2
M, oc if there no m that satisfies the inequality. Applying the Hoeffding inequality the Binom(n, 7) distribution, we see that IP M, 2 M2x()) 2 8/2, where
Mr = min { m FPx {x E (2(1) ,.. (m]) } 7}
(2)
(Note that M2 2 M.x) by definition.)
Step 2: estimate error at each repeated X value. Next, for each m = 1.2,..., let
Nmm Em= 1 { (m)) denote the number of times (m) was observed, and let
N22 Σ (nm 2 2}
m21
be the number of X values observed at least twice. For each with n. > 2, let Im (X;=
Rem Di. Ye- [X, = m(m) and 5", = - 1 - fm)² (x, = (m)) be the
sample mean and sample variance of the corresponding values. Define
Z =
(nm - 1) ((0m ()) - n 2
(4)
1.21.2.
2
5

---

This construction is inspired by analogous statistics appearing in the literature for testing properties of discrete distributions for instance. the work of Chan et [2014]. To see the intuition behind this construction, observe that {Y; X; x = is collection of
i.i.d. observations with mean uu (p(()))) Therefore, conditional on 7mm (with 7mm 2),
[m]] = (2 (x(()) and Var (7m) = nm _ [
and therefore E [Tmm (m(=) Rmm smm] = (u(x(()) (r(x))))) 2 is an estimate of our error this X value.
Step 3: construct the confidence interval. Finally, define our confidence interval. Let
2M, + n n(n 1) V 42+ + + BBNN2222 N22/6 24/6,
where Z4 denotes max (2. Then for each E Rd, define
(z) max 0, 0,
min [,
(5)
a 8--8771
We now verify that this construction yields a valid distribution-free confidence interval. Theorem 2. The confidence interval constructed in (5) is a distribution-fre ---ofiiieeecc interval (i.e., On satisfies Definition
Next, will see how this construction is able match the rate of the lower bound established scenario where the hypothesized support set and mean function
in Theorem D spseccifial "chosen well", i.e., good approximation to the true distribution P. For simplicity, we only consider the case where the marginal Px is approximately uniform over some finite subset of the hypothesized support, and the hypothesized function y has uniformly bounded error.
Theorem 3. Suppose the distribution P on (X, E Rd R has marginal Px that is supported on (x(1),.. ..... 2.h)) ..M. and satisfies Fpx {x- = =m(m)) } I n//M for all m, and suppose that P has conditional mean pap: Rd > R that satisfies Epx [(ur(X) (x I en? Then the confidence
interval constructed in (5) satisfies
1/4
E [Leb(Ch(Xnt1))) s
etT, + (
1/2
where e depends only on the parameters ot, 5, 7, 13.
To see some concrete examples of where this upper bound might be small, suppose that fi is constructed via data splitting (i.e., our initial data set has sample size 2n, and we use n data points to train z and then the remaining to construct the confidence interval). If μu is constructed via logistic regression, and the distribution P follows this model, then under standard conditions on Px we would have e9r, = 0( O(/d/n); in a k-sparse regression setting where we use logistic lasso we might instead obtain err, Olv log(d)/n) Negahban et al. 2012). If instead is constructed via neaestt neighbors, æ +> (x:) H-Hdöler smooth (and & chosen appropriately), then as
mentioned earlier we have err, = O(n 20(n-8/(84)) 3/(8+d)) [Györfi et al. 2002
Giné and Nickl 2016).
Discussion
Our main result, Theorem T shows that the problem of constructing distribution-free confidence intervals for a conditional mean has hardness characterized by the effective support size M,, (Px) of the feature distribution; distribution free confidence intervals may have vanishing length if the sample size at least as large as the square root of the effective support size, but must have length bounded away from zero if the sample size is smaller. The rate of the lower bound on length,
scaling as ming (Px))) 1}. 1),i. is achievable in certain settings- Thhooesss-hheessss 2 and 3 establish that 1/ distribution-fii confidence intervals may achieve this length if we have good hypothesis μ for pr. Of course, the specific construction used for these matching bounds may not be optimal- both in

---

terms of constant factors that may inflate its length, and in terms of the range of settings in which it is able (up to constants) match the lower bound. Improving this construction to provide a practical and accurate algorithm is an important question for future work.
One counterintuitive implication of our result is that a meaningful distribution-fres inference can be achieved even in the case (Fxx > n, where with high probability, the new observation Xn-1 is value that was never observed in the training set. The reason inference is possible in this regime is that the repeated X values in the training set provide some information we need to construct a meaningful confidence interval, and since the set of X values that are repeated is random, this leads to coverage guarantee (recall that these repeated X values were central to the construction of our confidence interval in Section B). An interesting possible application of this finding is for distribution- free calibration, where the aim is to cover within- -ii averages of the form f4b = E [Y X E X,] where Ed = Ub=1.....B. B. is a partition into bins. Gupta et al. [2020] study this problem in the dirtribution-free setting, and develop methods for guaranteeing coverage of each 44 when the number of bins satisfies B < n; in contrast, the methods studied in our present work suggest that we may be able to cover μ4l on average over all bins b in the regime n < B < n²
Generally, all inference methods must inherently involve a tradeoff between the strength of the guarantees, and the precision of the resulting answers. In this present work, consider a universally strong guarantee (i.e., coverage of the conditional mean for all distributions P), which results in precise inference (i.e., vanishing-length confidence intervals) for only some distributions P, namely, those with effective support size < n². This tradeoff may not be desirable in practice, since in an applied setting we might instead prefer relax the required coverage properties for more challenging distributions P' in order to allow for more precise answers. In practice, we may be satisfied with a validity condition that yields weaker guarantees in nonatomic setting, but still yields the stronger coverage guarantee in the achievable regime where M,, (Px) & n²², In future work, we aim to study whether this more adaptive type of validity definition, which is weaker than distribution free coverage, may enable us to build confidence intervals that have vanishing length even in the nonatomic setting.
A Proofs
In this section we will prove Proposition D [and Theorem I
The proofs of Theorems 2 and 3 as well
as of all the supporting lemmas appearing in this section, are given in the Supplementary Materials.
A.1 Proof of Proposition 1
To prove this proposition, we will consider replacing P with a distribution that places vanishing probability on some extremely large value 2 Fix any distribution P. and any y E IR. For any fixed e > O, define a new distribution Q as follows:
Draw X ~ Px, then draw Y|X (1 Prix + -d-
where Pyjx is the conditional distribution of Y|X under P. and 8, denotes the point mass at t. Then we can trivially calculate that drv( (mM x Px, Q" Qx) I ne. Therefore,
PpnxPs Px {u E (Xn+))) 2 xxx {ue Cn(Xn=1)) NE.
On the other hand, the distribution Q has conditional mean - (E- (c -1)p(())) = y:
(z(x)= = (1- - c)pp()= + e (c- (ell))))((((ppppp
and so the conditional mean /n (ng(X++1) is equal to y almost surely. Therefore,
Por xx {uE (X Po { {no(Xn=1) (n( 2 a,
where the last step holds since On must satisfy distribution-free coverage and, therefore, must satisfy coverage with respect to Q. Since > 0 is arbitrarily small, this completes the proof.
"Similar constructions are used in many related results in the literature e.g., Lei and Wasserman 2014 Lemma I] proves an analogous infinite-width result for the problem of prediction intervals required to be valid conditional on X while here we are interested in confidence intervals but only require marginal validity.
7

---

A.2 Proof of Theorem
To prove the theorem, we will need several supporting lemmas:
Lemma 1. Let Q be any distribution on [0. 1] with variance o². Then write Q as mixture of two distributions Qo Q1 on [0, 1] such that
Q = 0.5Qu + 0.5Q1 and EQ, [X] - Eqq [X] 2 20
Lemma 2. Let Px be any distribution RR, and let Rd X1 U U U ... be fixed partition. Define a distribution Po on (X, 2) E Id x {0,1} as:
Draw X Px, and draw Z Bemoulli(0.5)) independently from X.
For any fixed sequence (01, 02 ..... of signs d1; 02,,.. ... {=1}, and any fixed 61, 62,
[0, 0.5), define distribution Pa on (X, Z) E R x {0. 1)
Draw X ~ Px. and conditional on X, draw Z|X E Xm ~ Bernoulli(0.5 + am -mm).
Finally define Po (Po) (i.e., i..dd draws from Po), and define mixture distribution P1 (X1,Z) Zi)....... (X,, Zn) as
Draw A1, A2,.. iid Unif(+1), then conditional on A = A2, draw (X,, idd PA-
Then
drv dTv(Po, P1) S 2n
Σ m21
mm
Ppx {X E 2mm}?
We are now ready to prove the theorem. Define = f (x=xxxxx > M, }. We must have | M,, x since Px a probability measure, and therefore IPxx (X X2 < <1 by definition of MPxx)) On the set R any point masses of the distribution Px must each have probability < 1/M, (Px), by definition of X1; Pxx may also have a nonatomic component. Applying Dudley et al. 201 (011 Proposition A. we can partition RdXX, into countably many sets, X2UXUU...
such that I PPxx {X } S 1/M,(xx) for all m 2. Define pm
Pxx (X X.
For each x in the support of Px. let Py|x= denote the conditional distribution of Y given = x. we can construct distributions P1 y|X=> and Po Y|X=z such that
By Lemma
Py|x== = = 0.5P% + 0.5P xp- and E Ept
[
Epp x
M 2 (x)
VIX==
where (x) = Var (Y X = v) is the variance of Py|x= Next fix e = 0 and 62 = = ...
for some 6 E (0, 0.5). For any vector a = (01, .2,...) of signs a1, 02 ... E {+1}, define the distribution Pa over (X, Y) follows:
Draw X ~ Px, i.e., the same as the marginal distribution of X under P. Conditional on = x E Xm for any m 2 1, draw Y as
Y X x (0.5 + cm Ptix = + (0.5 amc) pd Pr|x=a
Thus, Pa differs from in that, conditional on X Xm for any m 2 2, the distribution of Y is perturbed to be slightly more likely (if am = +1) or slightly less likely (if am = -1) be drawn from Pxxx rather than Pe Finally, we define a mixture distribution Pmix on (X1, Yi)...,, (X,,, Yn) as:
Draw AI, A2,... U1), then conditional on A (A,, ... ) draw (X,, Y.) iid PA-
In the Supplementary Materials, we verify that we can apply Lemma 2 to obtain
2c2n
drv (Pmix: P*) < 2n
Σ e.eP = 2n
Ap2 <
(6)
(Mx(Px
m21
m22
where the last step holds since Pm 1/M, for all m > 2, by definition.
8

---

The remainder of the proof will center on the fact that, if is chosen to make the total variation distance between Pa and pix sufficiently small, then it impossible to distinguish between data drawn from pa or from PA for random A (i.e., from mmxx); since the conditional mean of Y|X differs by (c)) between P and PA. this means that our confidence interval for pp will need have width at least (()). For any Pa. since C. satisfies distribution-frre coverage, we have
(Xn+1) E Cx 2 a. (rr. XP,)'xxxx {
We can also calculate, for each m 2 2 and each Xm that lies in the support of Px,
MP, (z) (0.5 + am ame) Bp x M + (0.5 am Bpp xIx==
11x-= M
= 0.5 [R [Rpix-= M + + x-x MM) tame (Eryxx. M Byg Brgix- M) = tmm
-i--
where we write ((x) (BPrix.. [M] EP xix-o (1). In particular, if Xn+1 Xi, then uP, (Xn+1) E Ca(Xn+)) implies (ur(Xx+1) t e ( (X + 0. Therefore,
x(P.)xxxx (Up((Nnt)) t (X Cn (Xn+1) 00
P 2 x { (P.. (Xn+1) E C (X - {xu+1 E 2 since Pxx EX <
<1 7 Since this bound holds for all a, and since Pmix is mixture of
distributions ( then
P {(up(Xn+1) + +C( + #0} 29-
By our total variation bound (6. therefore,
+ PxxxXx + C (C # #0} 27 (M,(Px)
2
(7)
Now fix some co E 0.5). We calculate
Leb (Cu(Xn+1)) = / (IECC(XXnn)) dt 2 1 / + f0} de (XA(()+))
120
(I
+ =0} dt
1=0
J ((Up(Xntt) (x(= n (Xn4a) # 0) -(Xx+1))
200 I 1 (00((Xnt1) 2 oo and (up(Xn+)) + A (Xx (X # #0} de,
where the last step holds since A(Xn+1) 2 2x7((x+11 by Lemma P ((oB(Xn+1) 2 opo) 2 1 3 by definition of of have
Applying 7 and since
EpaxPx
Leb (Cn(Xnti)) 20 | 7-
(M, -
2 ) de
2
20 coly -a 33) 3 3,M,((x)
1/2
(0-a-m) M, MM, (Px)
Finally, choosing co min
,0.5 yields the desired lower bound.
2n
Acknowledgments and Disclosure of Funding
R.F.B. was partially supported by the National Science Foundation via grants DMS- 1654076 and DMS-2023109, and by the Office of Naval Research via grant N00014-20-1-2377 The authors thank John Lafferty for helpful discussions that inspired this work.

---

References
Jayadev Acharya, Clément L. Canonne, and Gautam Kamath. A chasm between identity and equivalence testing with conditional queries. arXiv preprint arXiv:4411.7346, 2014.
Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath. Optimal testing for properties of distributions. arXiv preprint arXiv: 1500055500..0 2015.
Rina Foygel Barber. Is distribution-free inference possible for binary regression? Electronic Journal of Statistics, 14(2):3487-3524 2020.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-507 2021.
Clément L Canonne, Dana Ron, and Rocco A Servedio. Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3):540-616, 2015.
Clément Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape restrictions of discrete distributions. Theory of Computing Systems, 62(1):4-62, 2018.
Siu-On Chan, Hlas Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms,, pages 1193-1203. SIAM, 2014.
Ilias Diakonikolas and Daniel M Kane. new approach for testing properties of discrete distributions. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685-694. IEEE, 2016.
Ilias Diakonikolas, Themis Goulcakis, John Peebles, and Eric Price. Samplc-optimal identity testing with high probability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-LecibizzZZeniin
fuer Informatik, 2018.
Richard M Dudley, Rimas Norvaiša, and Rimas Norvaiša. Concrete functional calculus. Springer, 2011.
Evarist Giné and Richard Nickl. Mathematical foundations of infinite-dimensionn statistical models, volume 40. Cambridge University Press, 2016.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-free binary classification: prediction sets, confidence intervals and calibration. arXiv preprint arXiv:2006.10564, 2020.
László Györfi, Michael Kohler, Adam Krzyžak, and Harro Walk. distribution-free theory of nonparametric regression, volume 1. Springer, 2002.
Byol Kim, Chen Xu, and Rina Foygel Barber. Predictive inference is free with the jackknife+-after- bootstrap. arXiv preprint arXiv:2002.09025, 2020.
Jing Lei and Larry Wasserman. Distribution-free prediction bands for non non- parametric regression. Journal of the Royal Statistical Society: Series B: Statistical Methodology, pages 71-96, 2014.
Jing Lei, Max G Sell, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-frre predictive inference for regression. Journal of the American Statistical Association, 113(523): 1014-1111, 2018.
Dhruv Medarametla and Emmanuel Candès. Distribation-free conditional median inference. arXiv preprint arXiv:2 2021.
Sahand N Negahban, Pradeep Ravikumar, Martin J Wainwright, and Bin Yu. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical science, 27(4):538-55) 557, 2012.
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pages 345-356. Springer, 2002.
10

---

Gregory Valiant and Paul Valiant. Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts. In Proceedings of the forty-third anmual ACM symposium on Theory of computing, pages 685-694, 201 la.
Gregory Valiant and Paul Valiant. The power of linear estimators. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 403 412-411. IEEE, 201
Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing, SIAM Journal on Computing, 46(())429-455, 2017.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning random world. Springer Science & Business Media, 2005.
Vladimir Vovk, Ilia Nouretdinov, Valery Manokhin, and Alexander Gammerman. Cross- cross-conformal predictive distributions, In Conformal and Probabilistic Prediction and Applications, pages 37-51. PMLR, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Several limitations are described in the Discussion section.
(c) Did you discuss any potential negative societal impacts your work? [N/A] This is mentioned somewhat in the limitations described in the Discussion, but is mostly not applicable for our work our results are theoretical and can therefore be viewed as descriptive (i.e., describing properties of existing problem), rather than creating a new tool or methodology, so there is no apparent potential for societal impacts as might arise from
tool method.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All assumptions stated explicitly.
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are split between the appendix and the supplementary materials.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]

---

5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "hX12bSN44Id", "reviewer": "Reviewer_uYq5", "summary": "The paper studies distribution-free prediction regions in regression problems, more precisely, it analyses confidence interval constructions, based on an i.i.d. data sample, for the true conditional expectation function (of the output given an input) at a new random input point, generated from the same distribution as the training inputs. Based on the concept of \"effective sample size\" it provides a lower bound for the expected length of this confidence interval (Theorem 1). The authors discuss some special cases, then provide an algorithm for discrete input spaces which, for certain \"well-behaving\" distributions (with \"small\" effective sample size), achieves a confidence interval length that matches the rate of the previous lower bound.", "questions": "", "limitations": "", "rating": 5, "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": "The paper studies an interesting problem, i.e., distribution-free prediction regions, and tries to provide a positive result: a construction for vanishing-length prediction intervals. As the paper also discusses, such a construction is not possible without restricting the allowed distributions. The authors overcome this difficulty by restricting their attention to discrete input spaces and distributions for which the effective sample size is smaller than the square of the sample size. An over bound that can be applied even to continuous input spaces is also a valid and interesting result. The literature review part of the paper is average, it only discusses some better known results. Thought the assumptions needed for the results can be obtained from various parts of the paper, but it would have been much better to clearly highlight the assumption (e.g., by naming them, like A1, A2), starting from the one about an i.i.d. sample. The fact that the algorithm is limited to certain types of discrete distributions decreases the significance of the result (prediction regions are more interesting in the  continuous case). Finally, the paper does not contain any numerical experiments, though, it would have been interesting to see how the suggested method behaves in practice. Therefore, the results of the paper are promising (Theorem 1 and the algorithm achieving a matching upper bound), but they do not seem significant enough, and the quality of the presentation should also be improved (assumption, experiments, etc.).\n\n--- --- ---\n\nPost rebuttal comments: thank you for your answers. While it is certainly true that the definition of \"effective support size\" is well-defined for any distribution, it provides infinity for nonatomic ones. Therefore, the concept is not very useful to study continuous distributions. It is understandable that this paper has a theoretical focus, but the lack of numerical experiments also shows that the paper would require some extra work. Nevertheless, having read the other reviews, I think that the direction is promising and the ideas might be useful for researchers of this field, even in their current form. Hence, I have raised my rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are not adequately emphasized. Even the title suggests that the result is applicable for continuous distributions, but it is only partially true. Theorem 1 indeed applies to that case, as well, but in this respect it does not provide significantly better bounds than previous works. The real novelty of Theorem 1 is only for the discrete case, moreover, the results about the given algorithm (Theorem 3) only applies to the discrete case. Taking these into account, the title of the paper is misleading. The fact that the paper does not contain empirical evaluations is also a limitation.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "LORFiC7j3am", "reviewer": "Reviewer_Rqsq", "summary": "This paper is concerned with the problem of distribution-free conditional mean inference.\nSpecifically, assuming an iid sample of size n from a distribution P of (X,Y) in R^d*[0,1], the aim is to construct a confidence interval at point x for the conditional mean of Y given X=x.\nUnlike what is sometimes considered in predictive inference, the goal is to construct a confidence interval containing the conditional mean, rather than a predictive interval containing the response (the latter would necessarily contain the \"noise\" and thus be of non-vanishing width).\nThe confidence interval should be valid distribution-free: for every distribution P on R^d*[0,1], the interval should contain the conditional mean at a random test point X, with probability 1-alpha over the draw of both the sample and the test point (drawn from the same distribution).\nIn addition to being universally valid, the interval/region should be of small/vanishing measure for distributions for which this is possible.\n\nThe main results are the following.\n\nFirst, if the distribution of X is continuous, then no vanishing confidence intervals is possible. A general lower bound quantifying this is provided (Theorem 1), scaling as M^{1/4}/n^{1/2}, where M is a suitable notion of support size of the distribution of X. This implies in particular that, if n^2 << M and the distribution is noisy, then no non-trivial inference is feasible.\n\nSecond, a construction is provided, which takes as input an assumed value (or guess) of the support of X and conditional mean function, and outputs a confidence region. It is shown in Theorem 2 that the confidence interval is always valid, even if the guessed support of X and regression function are wrong. Then, it is shown in Theorem 3 that, if the assumed support of X and regression are correct, and if the distribution of X is not too far from uniform, then the confidence region is of average length at most M^{1/4}/n^{1/2}.", "questions": "", "limitations": "", "rating": 7, "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": "The problem of distribution-free conditional mean inference considered in this paper is a simple but (in my opinion) interesting one. The paper is also well-written.\n\nAt the same time, I find the main positive result (Theorem 3), where the 'solution' to this problem is provided, somewhat disappointing. Indeed, for the procedure to yield small confidence regions, the procedure requires that both the support and the regression function are known (up to a small error for the regression, which appears in the bound). This takes away the core of the estimation problem, and in principle there is no need for such a strong a priori knowledge, as both the most frequent points and the value of the regression function at those points can be estimated from the sample.\n\nInstead, the following simple procedure should be optimally adaptive in this setting. Given the test point X, find the points i such that X_i = X, and, using a suitable concentration inequality for means of bounded variables (such as Bernstein), form a confidence interval for the conditional mean based on the mean of the associated Y_i's. With a little bit of care in the conditioning (as the number N of points s.t. X_i = X is random), this yields a distribution-free valid inference procedure. In addition, this procedure should be essentially optimal among distribution-free valid ones.\n\nThe performance of this method, namely the average length of the confidence intervals (even if those were built with Hoeffding's inequality), should be at most: letting X the test point and N(X) the number of i's st X_i=X, and p(x) = P(X=x) for x in R^d,\n\nE [ (N(X) + 1)^{-1/2} ]\n= sum_x p(x) E (N(x) + 1)^{-1/2}\n< c sum_{x st p(x) > 1/n} p(x) 1/[ p(x) n ]^{-1/2} + P (x : p(x) < 1/n)\n< c n^{-1/2} sum_{x st p(x) > 1/n} p(x)^{1/2} + P (x : p(x) < 1/n),\n\nwhich should be optimal for this problem in terms of dependence on P_X (improvements are possible in terms of the conditional variance of Y given X based on Bernstein).\n\nWhile this may be quite simple, I would certainly recommend acceptance for a clean and well-written paper doing this, together with a matching lower bound. In fact, this is what I assumed (reading the abstract and introduction) this submission was doing, and I was therefore leaning for a strong accept before I got to Theorem 3, but it now seems like a somewhat borderline case.\nIn any case, due to the above restrictions, the positive results of Sec 3 seem less interesting or satisfying than the lower bound of Sec 2, so I would suggest dropping Section 3, and possibly replacing it with the rest of the proof of the lower bound from the Supplementary Material.\nPerhaps the lower bound alone could warrant acceptance, depending on the other reviewers' and the AE's opinion?\n\nBelow are additional comments:\n\n- In Theorem 1, the lower bound depends on (the quantile of) the conditional variance of the response given the output, and on the number of points.\nThis lower bound could perhaps be complemented in the noiseless case (the response is a function of covariates), in the regime n^2 < M, showing that no nontrivial inference (vanishing confidence region) can be obtained in this case.\nThis is due to the fact that, with large probability, the \"test\" point will not be in the sample, and since the distribution is unknown, the function value at this point could be arbitrary at this point, thus any 'valid' confidence region will need to have at least constant measure.\nIn addition, it might perhaps be possible to state the lower bound in terms of the complexity measure given above (with the sum of the p(x)^{1/2} and the total mass of low-probability points).\n\n- Line 183: \"to capture gamma\". It seems that \"to capture a fraction 1-gamma...\" (or something equivalent) is meant.\n\n==\nUpdate in light of the authors' reply:\nThank you very much for clarifying the point of view taken in this paper, where estimation is not considered as part of the inference task, but rather decoupled from it.\n\nI indeed assumed that building an estimator (with small error) should be part of the procedure, as it is needed to obtain good confidence intervals (since the error of the \"guess\" for the regression function appears in the length of the confidence region). While I stand with this principle, I also understand the perspective adopted here, and agree that from this perspective, the upper-bound construction is non-vacuous. I am therefore now in favor of acceptance, and will increase my score accordingly.\n\nIncidentally, both my reservation about the upper bound, and my suggestion of the lower bound (first two points) are related to the fact that (unlike in your approach) I considered estimation of the regression function as part of the task. Indeed, in the regime sqrt(M) < n < M, it is not possible to estimate the regression function without additional structural assumptions (one cannot say anything about the regression function at x if x is not in the sample), so the error term in the bound will account for this effect. Admittedly, if for some reason one had a good estimator/guess (for some specific distribution), then indeed inference would be possible in this regime. So from one perspective, inference is impossible is the M>n regime (since even estimation is impossible), but from another, it is possible (a good estimator--even if it does not exist uniformly over this class--could be converted to a confidence band).\n\nOverall, I appreciate that the point of view adopted here, while not fully satisfying in some respects, can also be defended from a certain perspective. In this spirit, I believe that the paper could significantly benefit from some additional explanation in the main text, for instance in the spirit of your reply. Indeed, as written, the algorithm assumes a (seemingly data-dependent?) guess for the true regression function and support. Adding some explanation (alluding to a sample-splitting approach, where a first part of the sample would be used to build an estimator) could be helpful. Perhaps more importantly, I would recommend adding some caveats, to give a more comprehensive picture: e.g., obtaining small confidence regions requires a good estimator, which does not exist in general for M>n (but can exist in special cases).\n\nOne could still argue that analysis of the estimation aspect should also be part of a thorough treatment of the question, but this would involve a major revision and is perhaps best left out of this version.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "JUohQjGgwty", "reviewer": "Reviewer_dAue", "summary": "The paper investigates instance-dependent confidence intervals (CIs) for regression problems where the (marginal) distribution over covariates P_X has an atomic support. In particular, the main contribution of the paper is a lower bound on the measure of a CI in terms of an \"effective dimension\" of P_X which is roughly understood as a cardinality of the smallest subset of the support that captures most of the mass. Thanks to the instance-dependent analysis, the paper discovers two interesting regimes, namely when the effective dimension >> n^2, CI is non-vanishing asymptotically; on the other hand, when effective dimension << n^2, one can have a vanishing CI. The bound also organically recovers the fact (recently shown in other works) that CI is non-vanishing asymptotically when P_X is non-atomic. Finally, the paper matches the lower bound by proposing an algorithm for computing CI given an estimator, which matches a lower bound up to an additive excess risk of an estimator.", "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 very clearly written and does a good job positioning itself in the previous literature. The nice feature of this work is that it fills the gap between the continuous supports (where CIs are-vanishing) and finite supports in an instance-dependent way. The proposed algorithm (albeit, for a completely theoretical purpose) is simple enough to be used by practitioners. On that note, I found that the paper perhaps could say a bit more about other methods for computing confidence intervals (even in they are tailored for other setting); how would their upper bounds compare to the one obtained in Theorem 3?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "HdWbdvc_6q0", "reviewer": "Reviewer_tn9d", "summary": "This paper studies the construction of model-free confidence intervals for the conditional mean (regression function) of some outcome given a set of observed explanatory variables; i.e., the problem of estimating nonparametric regression functions. This problem is known to be very hard in general---it admits no non-trivial solution---but this paper makes interesting advances that are relevant for the special cases in which the distribution of the explanatory variables is mostly comprised of point masses (think of a discrete distribution, for example). In particular, a new lower bound is derived for the length of any model-free confidence interval with marginal coverage for the regression function, and a concrete algorithm based on data splitting that can achieve this bound is developed.", "questions": "", "limitations": "", "rating": 8, "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": "This work studies an interesting and novel variation of a well-known problem with broad relevance, and it develops an original solution for it. Overall, the paper is very well written and contains elegant mathematical results. These theoretical results intuitively make sense and their proofs appear to be technically correct.\nIt must be noted that this is a purely theoretical paper; it contains no numerical experiments, no comparisons to alternative approaches, and no applications to real data. In fact not much effort at all is spent in justifying the practical relevance of this work, which is not completely self evident to me. \n\nMajor comments.\n - A possible limitation is the dubious practical relevance of this work because the proposed algorithm will only really be useful in cases where the explanatory variables can only take a small number of possible values compared to the sample size. In particular, this rules out all high-dimensional applications and all low-dimensional applications with continuous-valued variables. What concrete applications of interest to the machine learning community are left then? See also the following section on \"Limitations And Societal Impact\".\n- What happens if the distribution of X is discrete but the dimensions d increase? I expect the upper bound should become trivial, as this problem seems very hard in high dimensions, and the algorithm relies on observing several identical values of X, which we know is extremely unlikely to occur in high dimensions. Perhaps a simple analytical example of this would be informative at the end of Section 3.\n\nMinor comments:\n - I find the title to be not very informative, and perhaps even a little confusing. In my opinion is does not convey clearly the idea the this work is about the construction of model-free confidence intervals for the conditional mean (model-free inference is typically predictive) and it does not suggest that it focuses on discrete explanatory variables (instead, I first thought the paper would be about classification).\n - If this work has any concrete practical relevance it should be emphasized, perhaps by providing some examples of how it could be useful, and some comparisons of its performance against that of existing alternatives (possibly parametric ones, if non-parametric alternatives do not exist). If no meaningful applications come to mind, perhaps this limitation should be disclosed more clearly.\n - Typo on line 99\n - Are there any missing relevant references for Proposition 1? My impression is that this result (or perhaps a small variation of it) is already known, but there are no references in Section 2.3. Indeed the proof of Proposition 1 says the argument is \"standard\", but again there are no references.\n - Is the hypothesized support set In Section 3 ordered? That is, is the definition of M-hat on line 183 allowed to re-order the x(1), ..., x(m)? It seems like this could greatly affect the value of M-hat, and line 177 (and common sense) suggests the set must indeed be ordered. However, sets are generally understood to be unordered, so the notation is a bit confusing.\n - Perhaps it could be explicitly emphasized that M-hat can become infinite large if the distribution of X is not sufficiently discrete, making the upper bound trivial. \n - On line 183, it should read 1-gamma instead of gamma.\n - In (5), perhaps one could recall that the denominator (alpha-delta-gamma) must be positive, as gamma may be large.\n - ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The main limitation of this work is its lack of practical demonstrations, applications, and its dubious practical relevance. These are not necessarily major flaws, as the theoretical content is sufficiently novel and non-trivial to justify acceptance, in my opinion. However, my impression is that this theoretical effort is ultimately motivated by its potential practical implications for machine learning and statistics practitioners, but such practical aspects are completely omitted. ", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "6A1ImNn5kCh", "reviewer": "Reviewer_WAr3", "summary": "In this paper the authors provide theoretical results on the type of problems that can be accurately learned (from a confidence interval standpoint) depending on the properties of the data distribution.\nThis departs from the usual convention of assuming as little as possible on the distribution, by adding a fairly minimal hypothesis that still provides strong results in the form of a lower bound (and upper bound) on the size of the attainable confidence intervals.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "As this is an entirely theoretical paper, the breadth of the possible remarks is limited given the format of NeurIPS.\n\nIt is a well-written paper and as far as I can tell the proofs and results are correct and use standard techniques. I am however given the time constraint not able to confidently say everything is correct.\n\nThe three theorems themselves are novel and interesting and provide valuable insights on what type of distribution can be predicted with high confidence.\n\nI think this paper, even if limited in impact to the general ML community, provides valuable insights and is of high quality. The proofs in themselves are of interest to other researchers working on similar problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The consensus of the reviewing committee is that the nice theoretical contributions of this paper are sufficient for a Neurips publication. There are some concerns about the importance of these results in applications and the authors are encouraged to address this concern in their revision. 
Decision: Accept (Poster)