Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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
$$
\mathbb P_{P^{n+1}} \big( \mu_P(X_{n+1}) \in \hat C_n(X_{n+1}) \big) \geq 1-\alpha.
$$

Here, $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$.

This 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.

The 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.
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.

**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.

**Quality.**  I suppose here is a good place to put most of my questions.

* 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?

* 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?

* 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?

* 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?

* How important is the i.i.d. assumption (vs. just exchangeability)?

* 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$.

* 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.

**Clarity.**  The paper was a pleasure to read.

I guess, as a few points of constructive criticism:

* 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.

* 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.

**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.
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_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 
Second, 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.)
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. 

However, 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.

Lines 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. 

While 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: 

- 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)? 

- 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. 

- 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)

- 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.

Other major comments: 

Line 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). 

Lines 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. 

Minor comments: 

Line 23: the min() goes into the next line 

Steps 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. 

Line 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.

Line 212: The parameter \eta sort of comes out of nowhere and is a bit surprising while reading. 

Line 240: “may enables us” -> “may enable us”

Line 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. 

Line 267: The start of the proof of Theorem 1 is difficult to find without appropriate markers

Lines 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. 

Line 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.

Line 303: I stumbled for some time on the first inequality; it may be useful to other readers to add one step

References: Arxiv versions have been cited for some published papers

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.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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)$.
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.

Moreover, 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.

Below are my detailed comments.

(1) I believe nonatomic or atomic distribution should be defined at the beginning of this paper, rather than delayed to page 4.

(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?

(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. 

(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?

(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?
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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).

Different 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.
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).

It 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.

The 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.

Questions and comments:

-   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.)
-   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?)
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.

According 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_title: null

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)