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@uchis hatesteechhcaaae 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 jrp. 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 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 - aa -B)1 min
where the expected value is taken over data points (X,, Y2) id Po i I...., +.
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-aaa 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, Barber (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 ..... (.......mmmm)) 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(xx) 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 "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.
in Theorem D spseccifial
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 err, = 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}. 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- ((
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 [X= > 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 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-= x|--2 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 -PPajxx {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)) = / J (I 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 (xp(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: (50X055500..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.09023, 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) 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 or 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": "hHLwvdTdKIx", "reviewer": "Reviewer_UaZ8", "summary": "This paper extends the lower bound results of Barber [2020] and Gupta et al. [2021] to a larger class of distributions over (X, Y). The earlier results applied for distributions P having P_X (or P_{f(X)} as in Gupta et al.'s result) nonatomic. This paper addresses the case where P_X may contain atoms, but is close to being nonatomic in the sense that some or all of these atoms have very small mass. The somewhat vague idea regarding what it means for a distribution to be close to nonatomic is characterized in this work. \nSecond, a new oracle based upper bound algorithm is proposed which seems to be based on a different idea compared to the previously proposed algorithm. (It is unclear to me if the guarantees are improved compared to previous algorithms.)", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "I think that the theory developed by this work so far is elegant. I found the paper easy to follow. The question that they consider I believe is significant, and the proposed solutions make sense. I read the proofs that are contained in the main paper (for the lower bound result), and they use some nontrivial techniques. \n\nHowever, I strongly believe that the work is incomplete on many fronts (more details below). While I have no doubt the authors will complete it adequately at some point, the paper is not currently in good shape to be accepted to Neurips. I have summarized some unanswered questions which I had, which indicate why (in my opinion) the paper is incomplete. I hope these questions provide the authors with meaningful feedback.\n\nLines 138-139: Given the close connections between Theorem 1 and Barber [2020, Theorem 2], it is unsatisfying that \\sigma_{P,\\beta} is not related to L_\\alpha(\\Pi_P) from Barber’s work. Can the former be seen as an approximate to the latter? Is one of them always worse than the other? I request the authors to address these and related questions. \n\nWhile the lower bound and the algorithm proposed is quite general and in a novel setting, the main upper bound analysis (Theorem 3) is in a highly restricted setting where previous results also apply; more details are in the next point. Could the authors provide an end-to-end upper bound analysis (including the guessing part) in a setting where previous results do not apply or are weak? Some open questions which the authors do not address (I believe) are summarized below: \n\n- What is the relationship between Theorem 3 and Barber [2020, Corollary 1]? What is the relationship to Gupta et al. [2020, Theorem 4] (this latter result is a direct comparison since it essentially induces a finite and known support onto P_X, which is exactly the setup of Thm 3)? In particular, suppose instead of starting with a proposed mean function, I constructed a CI around the sample mean (as against around the mean estimate \\mu). (***; this point referenced below again) From what I can understand it should be possible to show a DF CI guarantee for such a CI; is that true? How would the length such a CI compare to the CI defined in (5)? \n\n- Step 1: A natural algorithm is to suggest a stream is to look at the histogram of the first split of the data. What is the 'generalization' behavior of this stream in terms of estimating M_\\gamma well? Basically, what about an eq. (2) style result but for the other direction; that is, the estimate \\hat{M_\\gamma} is not too larger than M_\\gamma. \n\n- How does Theorem 3 change if the support is not finite/known? For instance, if less than \\gamma fraction of the support is nonatomic? (also related to next question)\n\n- Step 2 of algorithm and err_\\mu assumption of Thm 3: Is there some prior literature (in non distribution-free setting), where err_\\mu can be bounded? Without knowing this, it appears that (***) can circumvent this altogether and we can directly construct a CI around the empirical mean which should work? Since Thm 3 is for fixed support, I am not sure if step 2 is perhaps helpful in the distribution-free setting when the support is not actually fixed or known.\n\nOther major comments: \n\nLine 99 and Thm 1: If the authors wish to allow M_\\gamma to take the value \\infty, then I believe that the proof of Theorem 1 needs to be made formally valid for this case. Else, Thm 1 should have as an 'assumption'  that M_\\gamma is not \\infty. Specifically, lines 268-273 in the proof do not parse if M_\\gamma is \\infty (to the best of my mathematical knowledge, these statements are not formal, although I agree with the conclusions). \n\nLines 199-201: In my opinion, these lines should not be a brief remark in parentheses. At the least, they should be in their own paragraph, and preferably, it would be helpful if the authors could elaborate further. (Personally, I felt that they are best placed near the beginning of Sec 3 where the concept of the ‘initial guesses’ is described.) My understanding is that for the theory, sample splitting is required, while in practice it may not be required. If the authors could expand on this, that would be useful. \n\nMinor comments: \n\nLine 23: the min() goes into the next line \n\nSteps 1 –– 3: I noticed that step 1 only cares about the n_b values, and the remaining analysis is conditional on n_b. Due to this, I believe if step 1 fails w.p. p, and step 3 fails w.p. q, then the overall failure probability I think is at most p + (1-p)q < p + q. Just an observation; not sure if it is useful or worth exploring. \n\nLine 190: “testing discrete distributions” should be “testing properties of discrete distributions”? It eventually became clear to me that \\mu(x) is to be thought of as the null hypothesis for the mean and we are ‘testing’ if \\mu_P(x) = \\mu(x). If you add 1-2 lines to this end, that could improve readability.\n\nLine 212: The parameter \\eta sort of comes out of nowhere and is a bit surprising while reading. \n\nLine 240: “may enables us” -> “may enable us”\n\nLine 246: “The proof is simple, and follows a standard argument”: In my opinion, simplicity is subjective in this context, and the argument is not standard. Thus, I suggest that this qualification be removed. \n\nLine 267: The start of the proof of Theorem 1 is difficult to find without appropriate markers\n\nLines 287-288: “impossible to distinguish”: Are P^n and P_mix “impossible” to distinguish from each other (a test to distinguish them will have trivial power), or do you mean that a test to distinguish them will have low (but non-trivial power)? If the latter, then I think ‘impossible’ is not the right characterization. \n\nLine 301: The TV bound that that you use, sup_E |P(E) - Q(E)| \\leq TV(P, Q), should be stated explicitly since it may not be obvious to some readers.\n\nLine 303: I stumbled for some time on the first inequality; it may be useful to other readers to add one step\n\nReferences: Arxiv versions have been cited for some published papers\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The discussion section briefly alludes to a limitation related to the ones I discussed above. Specifically, on line 225 the authors say: \"the specific construction used for these matching bounds may not be optimal\". This is somewhat of a strawman since not constructing optimal CIs in in distribution-free setting is in itself totally fine and expected. However the bigger concern or limitation is the lack of a clear discussion on how the authors' algorithms improve on previously proposed CIs.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "GgQR_3SRvh", "reviewer": "Reviewer_idBd", "summary": "Suppose a regression problem and we have a training set $(X_i, Y_i)$ ($1\\leq i\\leq n$). Then, given a new instance $X_{i+1}$ ($Y_{n+1}$ is unknown), the method in the paper provides a confidence interval of $Y_{n+1}$ using the training set in a distribution-free way (i.e., we do not assume specific distribution on $X_i$'s).\n\nDifferent from conventional methods, the proposed method can be applied for nonatomic (pointwise distribution must be zero) distributions. Even in such a case, the proposed method can compute the confidence interval, although the size of the interval cannot be vanished.", "questions": "", "limitations": "", "rating": 5, "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": "It is interesting that the size of the confidence interval can be characterized with the *effective support size*, which can be infinite for continuous distributions. Even if it is infinite, the lower bound of the size of the confidence interval is finite (but not zero).\n\nIt is also interesting that, even for the distribution of infinite effective support size, the algorithm of Section 3 estimates a finite effective support size $\\hat{M_\\gamma}$ (since it uses only a hypothesized support set) and therefore can derive a finite-size confidence interval.\n\nThe reviewer felt the paper being insufficient since, although the theory is interesting, it is difficult to imagine how good the method works for real datasets. For example of Section 2.1, if it specifies not only the distribution $P_X$ but also $\\sigma^2_{P,\\beta}$, then it becomes easier to imagine how the proposed method works. In addition, it is desirable to have experiments for some datasets.\n\nQuestions and comments:\n\n-   In the algorithm of Section 3, it seems not so obvious that we always estimate a finite effective support size $\\hat{M_\\gamma}$ in the algorithm even if the true distribution has an infinite effective support size $M_\\gamma = \\infty$. So, it seems better to show how $\\hat{M_\\gamma}$ behaves if $M_\\gamma = \\infty$ in reality. For example, it would be better to provide how the proposed confidence interval is good (narrow) depending on $M_\\gamma$ (distribution = discrete, continuously uniform, gaussian, etc.)\n-   In (2), what if $P_X$ is a continuous distribution and therefore $M_\\gamma(P_X)$ is infinite? (Or, should not we interpret that $P_X$ is the true distribution?)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper discusses a distribution-free confidence interval of the outcome variable in regression problems, and proposed a method that can discuss both discrete and continuous distributions. This can be a strong tool to identify not only the correctness of the regression but also the uncertainty of it, in case we cannot know hardly anything about the true distribution.\n\nAccording to Section 1.1, the size of the confidence interval by the proposed method mainly depends on the relationship between the number of instances $n$ the effective support size $M_\\gamma$: if $M_\\gamma \\gg n^2$ (including the case of continuous distribution and therefore $M_\\gamma = \\infty$), then the confidence interval becomes broad (bad) and cannot be vanished.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "9h2rv4BmdX4", "reviewer": "Reviewer_teiB", "summary": "The authors conducted a theoretical analysis on the complexity of performing distribution-free inference on regression functions $b (x) := \\mathbb{E}[Y | X = x]$. In particular, the authors explicitly consider the dependence of the sample complexity on the $X$-distribution. The authors established both lower and upper bounds and also proposed a method of building a distribution-free honest confidence band for $b (x)$.", "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": "This is an important step forward in terms of theoretical understanding of the problem of honest adaptive inference for regression functions. As far as I know, previous works have not considered the \"effective support size\" as a parameter for the sample complexity of adaptive inference of functions.\n\nMoreover, the result in this paper is interesting. In one extreme, when the effective support size is $O (1)$, then estimating $\\mathbb{E}[Y | X = x]$ is essentially estimating the mean of $Y$ which gives us the usual parametric root-n rate. But in the other extreme, when the effective support size is $o (n^2)$, the confidence interval for each $x$ is still shrinking to 0, which is quite counterintuitive and indeed surprising to me (I would've guessed $o (n)$ is the phase transition point but Theorem 1-3 suggests otherwise). But regarding the second extreme case, I would like to see if the authors could provide a more intuitive explanation to convince me (please see comments (2)-(4) below), which I believe would help improve the reach of this paper in the general audience.\n\nBelow are my detailed comments.\n\n(1) I believe nonatomic or atomic distribution should be defined at the beginning of this paper, rather than delayed to page 4.\n\n(2) Can the authors provide a more intuitive explanation on the counterintuitive phenomenon that even when the support size is larger than the sample size, one can still make the confidence interval length shrink to zero?\n\n(3) Related to (2), it would be useful if the authors could provide more comments whether or not their results implicitly depend on the dimension $d$. One intuitive explanation I tried to come up with myself is when $d$ is finite, the locations without enough sample might be saved by the data nearby when the dimension is bounded. I am not quite certain. \n\n(4) Also related to (2), is it possible to get any meaningful bound on the variance of Lebesgue measure of the confidence sets? I understand most works focus on the expected Lebesgue measure but it might be interesting to also understand its randomness. But would it be that the variability of the size of the confidence interval is not small when the effective support size is greater than the sample size?\n\n(5) A related practical question is the following: as I mentioned, even if the feature $X$ is continuous, one may argue that in the computer at best one can only represent these numbers at a certain decimal accuracy, so essentially every data science question is about discrete or atomic distributions. Based on the result of this paper and other related papers that the authors cited, is it reasonable to simply discretize the distribution (assuming one-dimensional feature $X$) into bins and then make inference on the $\\mathbb{E}[Y | X \\in \\text{some bin}]$? If so, is there any reasonable strategy on how to perform such discretization?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1gyXcybLUX_", "reviewer": "Reviewer_6nGY", "summary": "Given samples $(X_1, Y_1), \\ldots, (X_n, Y_n)$ along with a test point $(X_{n+1}, Y_{n+1})$ drawn i.i.d. from some unknown underlying distribution $P$ (here, we assume the features $X \\in \\mathbb{R}^d$, and the label $Y \\in \\mathbb [0,1]$), the paper considers the problem of forming a confidence set for the conditional mean (e.g., the regression function), i.e., forming $\\hat C_n : \\mathbb{R}^d \\rightrightarrows \\mathbb [0,1]$ such that\n$$\n\\mathbb P_{P^{n+1}} \\big( \\mu_P(X_{n+1}) \\in \\hat C_n(X_{n+1}) \\big) \\geq 1-\\alpha.\n$$\n\nHere, $P^{n+1}$ denotes the $(n+1)$-fold product measure over the samples and test point, $P_X$ denotes the marginal law of the features, $\\mu_P(X) = \\mathbb E(Y \\mid X)$ stands for the conditional mean, and $\\alpha \\in (0,1)$ is a miscoverage level.  Note that $P$ here is arbitrary, meaning we want the above guarantee to hold no matter the distribution $P$.\n\nThis is a bit different from prior work, which has mainly focused on predictive inference, i.e., forming a confidence set for the (unseen) *response* $Y_{n+1}$.  Still, some very recent prior work has shown that distribution-free inference in the sense described above (as well as predictive inference) yields confidence sets whose size (in some appropriate sense) does not go down to zero as $n$ grows, so long as $P_X$ is non-atomic, i.e., inference is \"impossible\".  This paper asks the same question re: size when $P_X$ is allowed to have atoms.\n\nThe authors show that, for any confidence set achieving the above guarantee, and any distribution on $\\mathbb{R}^d \\times \\mathbb R$, the expected (w.r.t. draws of the data) Lebesgue measure of $\\hat C_n(X_{n+1})$ is lower bounded by a quantity scaling like $M_\\gamma(P_X)^{1/4} \\cdot n^{-1/2}$, where the object $M_\\gamma(P_X)$ quantifies the \"effective support size\" of $P_X$, i.e., inference is possible.  The authors construct an algorithm attaining the lower bound, i.e., the bound is seen to be tight.", "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": "I enjoyed reading the paper, and think it should be accepted modulo a (probably small) technical question + some other conceptual questions I have; I break these down below according to the categories suggested by the NeurIPS reviewer guidelines.\n\n**Originality.**  The paper looks at distribution-free inference for the conditional mean, which is much less studied (in the distribution-free setting, anyways) than predictive inference.  So, that is new.  The proofs seem to combine techniques that can be found in Barber (2020) and Barber et al. (2019), plus a little bit of innovation, but that's all completely fine.\n\n**Quality.**  I suppose here is a good place to put most of my questions.\n\n* First of all, the technical question.  This may be completely minor, but why are you going from a \"$\\notin$\" symbol to a \"$\\in$\" one on line 298?\n\n* For the more conceptual questions, why did you pick the measure of \"concentration\" (I'm using that word somewhat loosely here) $M_\\gamma(P_X)$ that you did?  I.e., why not / are there others (e.g., controlled Orlicz norm, smoothness, entropy, ... ??) that might also make the proof work out, and possibly lead to slightly different conclusions?\n\n* So, what kind of conditions on the conditional law of $Y \\mid X$ might be sensible to make here, to circumvent Theorem 1?  From looking at the proof, it's not totally clear, but maybe some kind of shape constraint?  Also, if I just agree to give up on coverage in certain parts of the input space, that would be fine / potentially get me around Theorem 1, right?\n\n* I assume the restriction of $Y \\in [0,1]$ can be weakened to something like $Y \\in [0,C]$, for some (finite) constant $C > 0$, at the expense of slightly more annoying proofs ... right?\n\n* How important is the i.i.d. assumption (vs. just exchangeability)?\n\n* What if $\\hat C_n$ is random?  I assume nothing really changes once you take the probability/expectation over any randomness inherent to $\\hat C_n$.\n\n* I might suggest running a few simulations as a check on the construction in Section 3, but I guess that's not really the point of the paper.\n\n**Clarity.**  The paper was a pleasure to read.\n\nI guess, as a few points of constructive criticism:\n\n* I might change from using the capital \"$A$\"s around line 285 to (something like) lower case \"$a$\"s, to be consistent with the notation introduced earlier.\n\n* I might put the intuition behind the proof conveyed in lines 292-295 into the main body of the paper somewhere, as that part is really the key.\n\n**Significance.**  The paper gives a (tight) impossibility result for distribution-free inference about the conditional mean, suggesting for the field that new assumptions may need to be made, and/or new inferential targets may need to be sought.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some discussion in the paper was given re: weaknesses, and I suggested a few improvements that might be made in my review above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: There is a consensus among Reviewers and Area Chair that the problem is interesting and worth pursuing further.

There are in two issues that make the paper borderline and not quite suitable for publication in its current form:

1. An end-to-end analysis to illustrate Theorem 3 is missing, for instance in a reasonable setting where by sample splitting,
estimating the support and building a candidate $\mu(x)$ satisfying the required assumptions of Theorem 3 is possible with the first half of the data,
and using the second half to implement the proposed $\hat C_n$.

2. The assumption involving $err_\mu$ in Theorem 3 is strong, as it requires a given precision almost surely over $P_X$.
The authors propose in the rolling discussion to rewrite Theorem 3 and replace this strong assumption by an L2 type estimation bound,
however there is no current mechanism to see a revised version of the paper, with rewritten Theorem, before making a decision.

These issues and reviewers' concerns suggest that the paper will be better served by being revised and clarified, taking into account these concerns and implementing the fixes proposed by the authors in the rolling discussion. Finally let me mention that there was significant enthusiasm among some reviewers in the reviews and in the discussions regarding the result, and I encourage the authors to pursue publication of the results after a revision in another conference/journal.
Decision: Accept (Poster)