Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies a family of nonparametric two-sample, independence, and goodness-of-fit tests based on incomplete kernel-based U-statistics, for which it proves validity (Proposition 1) as well as guarantees on power, assuming the true densities lie in a Sobolev space and are sufficiently well separated in $L_2$ distance. The power guarantees are initially proven for a statistic depending on the true smoothness of the Sobolev space (Theorem 1), but Theorem 2 extends this to an estimate that is adaptive to unknown smoothness. Theorem 3 shows that, compared to existing results for independence testing, a tighter bound, with better dependence on the type-1 error probability, can be obtained. Finally, some experiments demonstrate how the performance of the proposed estimators varies with hyperparameters and how this compares with some other linear-time nonparametric tests.
strengths_and_weaknesses: Strengths: This paper provides much more compelling theoretical results (minimax optimality, especially for an adaptive estimator (Theorem 2)) than most related work on two-sample testing, which usually only shows consistency. It’s also nice that a unified but rigorous discussion is given for the closely related problems of two-sample, independence, and goodness-of-fit testing.

Weaknesses: The paper has a lot of notation that is very similar or overloaded, but not explained or disambiguated near where it is used. For example, $L$ is defined just before Line 177 as the design size of the incomplete U-statistic, but is also used as a kernel (in Eq. (12)) and for $L^p$ spaces (in Eq. (17)). This made it a bit hard for me to follow the paper’s notation. I think it would help if the paper was a bit more explicit (even redundant) with explaining its notation near where it is used (e.g., reiterating “where $L$ is the design size” after Theorem 1). The paper also is not particularly clear about its distinctions from prior work (see questions below, although I was able to piece this together from various parts of the paper and by reading some of the references).
questions: 1. Lemma 1: The variance bound for random design includes a $\frac{1}{|\cal{D}_r|} + \frac{1}{N^2}$ term. Since $|\cal{D}_r| \leq N^2$, isn’t the second term redundant (i.e., can’t it be absorbed into the constant $C$)?
3. Line 144-146, “The motivation for defining the estimators… of order 2 (rather than of higher order) derives from the reasoning of Kim et al. (2022, Section 6)...”: I didn’t quite understand this sentence. I skimmed Section 6 of Kim et al. (2022), and, while they do indeed study U-statistics of order 2, the motivation for order 2 (rather than of higher order) wasn’t obvious to me. Could the authors clarify?
2. I found the motivation for Theorem 3 (lines 241-256) a bit hard to understand. Am I understanding correctly that the improved (logarithmic rather than polynomial) dependence on $1/\alpha$ has been previously shown for two-sample testing but not for independence testing. Later on (Lines 262-263), the paper says “As discussed by Kim et al. (2022, Section 8.3), their proposed sample-splitting method can also be used to obtain the correct dependency on $\alpha$.” So what exactly is the new contribution of Theorem 3?
4. Figure 1: The first row of plots includes a green curve that isn’t included in the legend. What is this? Also, the paper discusses results for some methods (e.g., OST PSI) for which I didn’t see any results in Figure 1. Where are these results reported?
5. Could the authors elaborate on advantages of the proposed tests over previous tests that have been shown to be minimax optimal (e.g., the Gaussian-kernel-based tests of Li and Yuan (2019))?
limitations: The paper would definitely benefit from further discussion of the limitations of its present results and suggestions for future work. However, given space limitations, I don't think further discussion of this is strictly necessary for acceptance.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: POST REBUTTAL:

Score increased to 7.

------ -------
In this work, the authors propose faster than quadratic tests for the two-sample, independence, and goodness-of-fit problems, using the Maximum Mean Discrepancy (MMD), Hilbert Schmidt Independence Criterion (HSIC), and
Kernel Stein Discrepancy (KSD), respectively. They are based on incomplete U statistics that can interpolate between linear time, and quadratic time costs (the latter cost is incurred by typical tests which are complete U-statistics). 

strengths_and_weaknesses: The authors provide a tradeoff between the computational cost used and the power achieved in Theorem 1---while achieving the minimax rates over Sobolev balls when using the quadratic runtime variant. The authors then use this result to also achieve appropriate power results for kernel selection (up to logarithmic inflation in the number of kernels). Notably, this result is adaptive and does not require the knowledge of the smoothness parameter of the difference between the null and the alternative density.

The authors also provide several experiments which demonstrate the advantages of the proposed methods.  

The writing of the paper is pretty clear and worth appreciating!
questions: 
1. The work in Huggins and Mackey (e.g., the L1 IMQ and Cauchy RFF random feature Stein discrepancies) were all linear and not quadratic time as the authors mention in l 53. Given the focus on linear time tests in this work, I  believe that these tests should be treated as a useful baseline for goodness-of-fit comparison experiments. In particular, Huggins and Mackey's experiments showed that their tests typically outperformed the FSSD test (which is one of the key linear time baselines in the current work).

2. In the separation rate, the dependence on alpha is logarithmic but that on beta is polynomial (1/x)--is the latter unavoidable? I can see from the proof that it is because of the nature of concentration inequalities used in the two contexts (namely Rademacher chaos concentration, and Markov's inequality)--but are the arguments known to be tight? Does there exist a setting where such dependence is necessarily needed?

3. Is the tradeoff in Theorem 1 tight? I can see it's tight when L = N^2 but is it tight for smaller values of L? Some discussion on this would be very useful.


4. Do you not need any requirements on p for Proposition 1? And does only the difference p-q need to lie in the Sobolev ball for Thm 1(ii)?


5. Does the choice of design D not matter? Does it have to be an iid subsample? Can it be adaptive? (My guess is all the arguments go through relying on iidness of data points in D).

Minor comment:
- It would be easier to process the results if the assumptions on densities are stated in an assumption environment, and then referenced in the theorem results. 
limitations: See questions.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Post rebuttal: after the authors response and reading the other reviews, I updated my score to 6 (from initially 4) see also my comment below.


-------- original review ------

The paper considers a general framework for kernel-based hypothesis testing, where the test statistic is given by a U-statistic. The framework covers Two-sample testing, Independence Testing, and Goodness-of-fit testing.
The paper shows that using an incomplete U-statistic estimate allows to trade-off computational resources for statistical significance, which follows from general theory of incomplete U-statistics.
Furthermore, it adopts recent advances to aggregate such tests over multiple kernels and provides insights into the minimax separation rates over Sobolev balls.
Lastly, the paper provides simple experiments on toy data, illustrating their findings and comparing to some other approaches to tackle the respective testing problems.
strengths_and_weaknesses: *Strengths*:
- the work applies to three different testing scenarios and illustrates their close connections.
- Although the use of incomplete U-statistics is not completely new for kernel-based tests (see e.g. Yamada et al ICLR 2019) the provided non-asymptotic tests are relevant and nicely illustrate the trade-off between computational resources and statistical significance.
- The tests provably control type-I error also at finite data, while some of the existing methods, like OST, do not.
- The theoretical insights are concisely stated and the prior results properly attributed. Arguably, though the provided results are rather simple consequences and combinations of prior results.
- The provided Code is clean and it is easy to reproduce the experiments. The code was submitted after the deadline, which might be a violation of the rules!

*Weaknesses*:
- Overall, I think the practical relevance is quite limited:
a) The experiments are limited to very simple toy data sets. While they illustrate the effect of using incomplete U-statistics, the effect of the aggregation procedure is not illustrated at all.
b) Only very few (4!) kernels are aggregated over. IMO this does not suffice to illustrate the benefits of the aggregation procedure.
c) Overall there should be more guidance for practitioners. How many kernels should one choose in practice?
- The authors consider ‘linear-time’ tests (eq. 10), which I think is misleading. By their theoretical results Theorem 1 ii) and considering $L=c N$, the uniform separation rate is not guaranteed to converge to zero. I thus also think that the gray box on page 7 is actually wrong. IMO it should be changed to the following: let $L=N^{1+a}$. Then for $a=1$ one recovers the minimax rate. For $a> 0$ the rate still converges to zero, but slower. For $a\leq 0$ there is no guarantee. **Overall the provided theory does not provide guarantees for linear-time tests**.
- For the two-sample problem, the provided tests cannot handle imbalanced samples in a meaningful way. The provided approach simply truncates data ($N=min(m,n)$ in line 131).
- I think the presentation of the initial statistics (1) and (3) is suboptimal. For unexperienced readers it seems that these statistics scale like N^4. So I think it would be better to directly introduce the statistics such that they correspond to the complete U-statistics of (7) and (8). Alternatively, it should be explained why this statistics scale quadratically (no need to tell me in the rebuttal).
- The claim that the “aggregation procedure is known to lead to state-of-the-art powerful tests” (l. 26f) seems a bit biased.
- Prior work (Sutherland (ICLR 2017), Liu (ICML 2020)) showed that continuously optimizing a kernel is quite advantageous and harnesses the beenfits of gradient-based optimization. The present work only allows to combine finitely many (prespecified) kernels. 
- The aggregation scheme is a direct adaption from prior work (the authors are transparent about this).
questions: - Are the tests really 'linear-time'? (see comment in limitations)
- l. 152-156: why do you discuss the random design when in the end you are using the deterministic one?
- How should one choose the number of bandwidths ($l$) in practice?

Minor Comments:
- l. 147: define what a degenerate kernel is.
- Type in Equation before line 500: should be $x_{i_1}$,...
limitations: The work is theoretical and no direct negative societal impact is to be expected.

The theoretical results discuss minimax optimal rates, which leaves the impression that nothing can go wrong. But in practice there remain some parameters that users have to choose, for example how many bandwidths to include in the aggregation. For the experiments the authors only use 4 bandwidths, which in my opinion hardly suffices to illustrate the benefits of this aggregation. On the other hand, it is not clear what happens if too many bandwidths are included.
review_title: null

Meta-review: metareview: The paper discusses fast computation methods for kernel-based statistical tests: MMD, HSIC, and KSD.  The paper uses incomplete U statistics in constructing the methods, shows decent theoretical results including the rate analysis, and confirms favorable numerical results.  The paper has significant theoretical contributions to the topic, and also demonstrates the practical usefulness of the methods.  After the revision, all the reviewers agree to accept this paper to NeurIPS. 

confidence: Certain
Decision: Accept