Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: The authors put forward a set of high-level conditions that are sufficient for bootstrap consistency of nonlinear statistics and for constructing bootstrap confidence intervals that are approximately asymptotically correct. They illustrate their framework with two examples: a) a two-sample test to test whether two distributions are identical, and b) a procedure to construct confidence intervals for the risk of smooth stacked ensemble estimators.
main_review: This paper is well-written and clearly structured. Obviously, the authors have put a lot effort in this paper. However, I am always wary of papers that aim to develop a very general theory. Often, the level of generality of such papers leads to weak implications. Sometimes such papers also impose (hidden) assumptions, that limit the range of applicability of the supposedly general results.

1) I believe that it is long clear that stability conditions such as Assumption 1 are part of the sufficient conditions for bootstrap consistency/ consistency of bootstrapped CIs. The difficulty lies in verifying these conditions for specific statistics and in deriving anti-concentration inequalities for specific statistics that are statistically meaningful. The examples provided in the supplementary materials (such as the square or p's power of the sample average) are not meaningful statistics. The two applications in the main text are essentially smoothed versions of a maximum/ supremum statistic and, therefore, it is easy to find equivalent maximum-statistics which could be analyzed via the approach developed Chetverikov, Chernozhukov and Kato in their sequence of papers from 2014-2020. What statistics other than statistics related to the maximum satisfy the stability properties? 

2) I credit the authors with pointing out that anti-concentration inequalities are not needed if one is willing to settle for a weaker notion of CIs.

3) In the main text of the paper the authors write that their work relies on (or extends?) Chatterjee's (2006) generalized Lindeberg principle. I know that Chatterjee's results only apply to random vectors with i.i.d. or exchangeable entries. I therefore wonder how the authors modify Chatterjee's arguments to allow for arbitrary correlation between the entries of the random vectors. The proof of Theorem 1 appears to be incomplete as it references a Theorem 19 which is not in supplementary materials. Is the missing Theorem 19 is a version of Chatterjee's results for "triangular arrays of i.i.d. processes"? I could not locate an analogue of either Theorem 1.1 or 1.2 of Chatterjee (2006) in the supplementary materials.

4) I've never seen the notion of bootstrap consistency that the authors use (lines 113 - 118). It is weaker than convergence in Wasserstein distance and it does not seem to imply consistency in Levy-Prokhorov distance. Does it imply consistency in Kolmogorov distance? Since the authors' metric does not seem to metrize weak convergence I do not think that the bootstrap consistency result in Proposition 2 is particularly useful. It doesn't seem to imply that we can compute p-values needed for hypothesis tests.

5) The second main result of the paper (Theorem 2) holds only for nonlinear statistics which are also Lipschitz continuous with respect to the $\ell_\\infty$-norm (Assumption $H_3$). One can easily infer from the statement of the theorem that the larger the Lipschitz constant, the larger the proposed CI. This is problematic since the Lipschitz constant might grow with the dimension. Here are some not fully rigorous calculations to illustrate this point: For simplicity assume that X_i's are i.i.d. vectors with i.i.d. entries. Take $g(X_1, \\ldots X_n) = \\|n^{-1}\\sum_i X_i\\|_2$. Then $g$ is Lipschtiz continuous w.r.t. to $\\ell_\\infty$-norm and has Lipschitz constant $d_n^{1/2}$. Hence, by Theorem 2, as the sample size $n$ (and the dimension $d_n$) grow the diameter of the CI for $\\mathbb{E}\\|n^{-1}\\sum_i X_i\\|_2$ grows roughly at a rate of $d_n^{1/2}$ (b/c $t_\{g,n\}$ has to grow to cancel out the Lipschitz constant otherwise the tail bound on the maximum of the Gaussian random variable $N^n$ doesn't hold). Intuitively, this CI is too wide since we know the variance of $\\|n^{-1/2}\\sum_i X_i\\|_2$ is roughly constant (b/c $n^{-1/2}\\sum_i X_i$ is approximately Gaussian and the variance of the Euclidean norm of a centered Gaussian vector with identity covariance is dimension free).
limitations_and_societal_impact: Somewhat. The authors provide several examples and counter-examples in the supplementary.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper discusses very general conditions on estimators under which the empirical bootstrap is asymptotically consistent. Explicit applications to two difficult inference problems, including two-sample tests using kernels with (approximate) kernel selection and on estimating the risk of ensemble learners.
main_review: The conditions discussed in the paper under which consistency can be achieved are impressively general, and it is clearly advantageous to consider general conditions rather than specific problems as is common. The paper is well written, and for the most part clear, although there are places in which the notation becomes slightly challenging (see later).

I do not have any significant reservations about the paper, and my main comments are editorial suggestions:
- I recommend being explicit in the abstract that the examples covered are slightly modified; especially in the case of the kernel two-sample test, where a softmax variant is substantially different from a discrete selection, which is what (at least I) expected.
- I would recommend mentioning earlier on that the adjustment for the "centering" can actually be easily handled in practice. As I read through the first part of Section 3 I was bugged by the persistent presence of the centered processes, and it was only patently clear how this is handled when I got to line 214. This only bears mentioning earlier; it is not necessary that the details be given, but the ubiquity of the basic CLT as being the way around it will make less expert readers feel more at ease.
- Am I missing something in the final statement in Theorem 2? Should it not be P(E[g_n(Y^n)] \not \in [interval]) \leq \beta?
- The notation in Section 4 is challenging, since now the second subscript refers to the identity of the process and not the index of the component in the corresponding observation. While when the permutation test starts to be discussed, if I understand correctly, this becomes a little clearer since then the two processes (samples) are just stacked next to one another as one array of higher dimensional processes, but I think it is worth mentioning earlier on. Otherwise, the expression above line 224 is confusing if you interpret X_{1,1}^n as the first element of the first observation in X^n, and not as the entire first observation in (X^n_{i,1}).

To conclude, I have some minor comments/queries/typos, etc.
- The word "each" in line 17 seems out of place
- line 77: space between [14] and .
- line 83: Recommend either "A series of works has strengthened..." or "A series of work has strengthened..."
- lines 84 and 86: should not the dimension, p, explicitly depend on n as previously?
- line 86: "...conditions THAT log(..."
- line 94: "...specific STATISTIC or..."
- Although not ambiguous, the metric d_{\mathcal{F}} is defined between probability measures, but is evaluated on random variables.
- line 124: "same mean AS X^{n}_1
- Aren't lines 126-127 just repeating what lies above in line 123?
- In Proposition 1, recommend "Let \epsilon > 0 be constant, then..."
- line 164: missing subscript n in g(0X^n_{2:n})
- Although not ambiguous, I don't think the L_{p} spaces of RVs are not explicitly defined; only the norm is.
- this is purely cosmetic, but in the statement of assumption H_3, the parentheses in g(Y^n + x/sqrt{n}) would look better if larger
- line 224: should not "opposite" better be replaced with "converse"?
- What does (a) above equality mean? Should this be d?
-  What is the metric d_W?
- The font in Proposition 2 is inconsistent
- Why is sometimes max()/min() and other times join/meet used?
limitations_and_societal_impact: Limitations are not explicitly discussed. There is no apparent potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors derive general stability conditions under which the empirical bootstrap estimator is consistent and quantify the speed of convergence. These results are illustrated for two-sample kernel tests after kernel selection and the empirical risk of stacked estimators. These two applications are relevant due to the recent interest in kernel tests with learnt deep kernels and the popularity of ensemble models in practice.
main_review: The paper is highly technical and theoretical, and it still reads quite well. Although I am not very familiar with the statistical approaches and therefore not qualified to comment on its soundness, I am convinced that its originality and contribution is definitely very strong.
As mentioned above, the application of the general theorem to kernel tests with learnt kernels and model ensembles is very relevant to current machine learning challenges. While I am keen to see numerical results corroborating the theoretical ones, they are not a must for this paper, rather for a follow-up.
Finally, I would have appreciate a concluding section highlighting the limitations of the current approach and a recommendation on where to focus future research.

Other comments:
- Please use a spell-checker to review the paper as there are few typos here and there.
- Lines 82-84: p, p_n and n are used before being defined.
- The two equations after lines 123 and 127 are identical: should they?
- Page 4, please define C^{\alpha, n} and C^{\alpha, n}_\epsilon
- Page 8, Proposition 2: why is the result obtain using the L1-norm instead of just d_F \to 0 in probability, as d_F is a real number anyway?
limitations_and_societal_impact: Limitations have not been fully explained (or maybe I missed them).
This contribution does not have potential negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: ---------------------
---------------------
**Update after discussion with authors and other reviewers**

Thank you to the authors and other reviewers for engaging so much in the discussion period. I think the discussion has made clear that the  authors could significantly strengthen the paper by drawing connections between their proofs and others in the literature. I also think there should also be a discussion on the limitations of the example in Section 4, as the authors are not analyzing a standard kernel test (although, as they note, they are analyzing a statistic that is highly related to a common kernel test). I think this makes the results of Section 4 a little weaker. This, combined with XTTq's points about the relation to the existing literature, have led me to decrease my score somewhat. I'm still in favor of an accept because while the paper could be improved by restructuring, I think it still presents practically useful theory as-is. If the paper is accepted, I think the authors should at the very least include some discussion surrounding their discussions with XTTq.

---------------------
---------------------


This is a theoretical paper which aims to extend the reach of consistency results for the classical bootstrap. The authors prove some general theory about the bootstrap and then show that this theory can be specialized to prove consistency of the bootstrap for two sample kernel hypothesis tests and stacked ensemble estimators. To my knowledge, these results are novel in that previous bootstrap theory does not apply to them, and these results seem useful to the machine learning community. Besides solid results, I think this paper has a few nice strengths:

1.	The paper is well written
2.	The literature review is, to my knowledge, very thorough (which is not easy to do for a topic with as much background as the bootstrap).
3.	The authors are careful to call out the flaws of their theory throughout the paper.
4.	The authors try to explore the necessity of their assumptions with the use of counterexamples

A downside is that all of this takes a *lot* of room – the appendix is 45 pages of additional results, examples, counterexamples, and proofs. I’ve tried to go through this as carefully as possible, but I have not been able to carefully check all the proofs. Overall, I think this is a solid paper, and my criticisms listed below are not major.

main_review: I have three larger comments that I think could improve the paper, listed as (A), (B) (C) below:

(A) I think it would be good to include some more discussion about what kinds of models in machine learning the paper does / does not extend the reach of bootstrap consistency proofs to. The authors give some generic theory and then show it applies to two specific examples (kernel hypothesis testing and stacked ensembled estimators). Is there some underlying theme between the proofs for these two examples? Can the authors conjecture about what kinds of other examples their proof techniques might work well for? Conversely, it seems that the authors do not cover *all* problems of interest in machine learning. My understanding is that for simple models like Poisson regression with covariates growing unbounded with n (that is, a GLM with unbounded link function with unbounded derivatives), existing common proof techniques for the consistency of the bootstrap (like linearization) are not known to apply. And it seems like the authors’ Assumption 1 would be violated in this case as well, so their theory will not apply to this case either. I don’t mean this as a criticism -- the authors definitely don’t try to sell their work as applying to everything. But it would be good to call out what’s still missing for the sake of future research.

(B) The authors put a lot of discussion up front about their use of particular proof techniques backing their new results (“Chaterjee’s generalized Lindenberg approach and a smart path interpolation technique”). This sounds interesting, and I was hoping to learn more in the main text! I wonder if the authors could summarize how these techniques fuel their results in the main text. 

(C) I wonder if section 5, which is about bootstrapping ensembled estimators, could be reworked to include more discussion and fewer mathematical details, e.g. by making Prop 3 an informal statement and pointing to the appendix for a formal statement.  I say this because I think there are a few points in Section 5 that could use expanding on:
1. The authors analyze the bootstrapping properties of what seems like a non-standard ensemble estimator. In particular, they consider the ensemble of estimators indexed by 1,…,p, where the ith estimator is fit on datapoints x_1, …, x_i. This seems like a very particular estimator. To be fair, the authors do note “[this specific ensemble] allows us to show that the distribution of the ensemble’s risk can be estimated with the bootstrap”. But it would be great to understand what properties of this estimator are required for the authors’ analysis vs required for the bootstrap to converge (i.e. did the authors choose a somewhat non-standard ensemble because the bootstrap doesn’t converge otherwise or because their analysis won’t go through otherwise?). 
2. What is \beta_n doing here? Is it a hyperparameter again? It seems like \beta_n is required to go to infinity, which in turn seems like it causes the ensembled estimator \hat\Theta_n to collapse to the best-performing \hat\theta^k_n. Is this correct? If so, why is this collapse a desirable thing?
3. Are the base estimators (the \hat\theta^k_n) not required to satisfy Assumption 1? This seemed like a pretty important part of previous theory, so how is it that we are stacking Assumption 1-violating estimators to get a bootstrap-consistent estimator?
4. Relatedly, it would be nice to have a conclusion at the very end summarizing the main results of the paper.

-------- Scattered smaller comments:
Line 263: what is d_n’? 

Line 156: Notation for Lindenberg path interpolation is defined, but I don’t think this was used in the main text.

Line 167: Influence functions are mentioned here but not defined.

The title of Appendix N is “Further proofs from section 3”, but not all of the results discussed here seem to be from Section 3 (e.g. there is no Example 2 in Section 3) 

limitations_and_societal_impact: The authors do not discuss societal impact in this paper, but, given its subject, I think that is appropriate.
review_title: null

Meta-review: There has been a tremendous amount of discussion about this paper. Several points of criticism have been raised by Reviewer XTTq, mostly concerning the used stability condition, consistency in high dimensions and the generality of the specific kernel used and the examples in sections 4/5. On the other hand, all other reviewers had a much more positive impression of this paper, which is reflected in their high scores that they were willing to defend in the discussion. In my opinion the author rebuttal was very convincing and successfully addressed most major points of criticism in a detailed, transparent and meaningful way. So I recommend acceptance of this paper.   
Decision: Accept (Poster)