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 proposes a variant of the kernel-MMD statistic, called cross-MMD, based on the ideas of sample splitting and studentization, and showed that it has a standard normal limiting null distribution. Using this key result, they introduced a permutation-free (and hence computationally efficient) MMD test with 100 times faster and a sacrifice in performance that is better than the factor sq(2) (expected due to splitting). 
strengths_and_weaknesses: Strengths
-Well written paper. Nice and simple theory. No "wordy" sentences, No blurry experiments or non-understandable mathematical expressions. No overselling. Well done. 

Weaknesses
- Focus on performance and time consumption but (MMD-related weakness) no information concerning interpretability in terms of Variable influence and how mmd can be used as an alternative to traditional approaches (multiple testing etc).
- The splitting scheme is always problematic in cases with low sample sizes (and the time gain is negligible) and studentization more risky. 
- I see a contribution only in cases where extremely big datasets occur. 

questions: Considering the current presentation of the results It is not clear if always sqrt(2) factor is always guaranteed. Please correct me if I misunderstood. For example In cases of Figure 3 for samplesizes of 50 to 100 is it true? Please try to discuss if there are cases where the test's performance is not sufficient (therefore the test is not recommended).
limitations: Authors are discussing sufficiently both limitations and perspectives. The weaknesses that I mentioned could also become part of this discussion.
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: This paper proposes a novel two-sample test based on the MMD test. This test has a closed-form of null distribution (a normal distribution), and the intuition for the resulting null distribution is that the proposed test can be thought of as performing a student's t-test.  
strengths_and_weaknesses: Strength: It is creative to split the dataset into two pairs to studentize the original MMD test, therefore resulting to a traceable null distribution.  
Weakness: Comparison with other permutation two-sample test which also has closed-form of the null distribution is missing. One example is the Friedman-Rafsky (FR) test[Friedman, 1979]. In fact, both the FR test and the proposed test have the same null distribution, I think the FR test would be a good baseline would be good to compare with. Besides, the price of deriving such an ''exact'' null distribution test is to decrease the power. Is that possible to have a sample complexity analysis regarding the Type II error of the proposed MMD variant compared with the original MMD test? 
Friedman, Jerome H., and Lawrence C. Rafsky. "Multivariate generalizations of the Wald-Wolfowitz and Smirnov two-sample tests." The Annals of Statistics (1979): 697-717.

questions: Please see above.
limitations: Please see above.
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: The paper proposes and investigates an alternative estimator for maximum mean  discrepancy (MMD), a popular kernel-based two sample test. The benefit of the estimator is that it has a standard normal distribution under the null hypothesis of equal distributions. Thus, there is no need to perform costly permutation tests in order to get a p-value from the surrogate null distribution. The theoretical results go beyond this to include cases where the kernel is sample size dependent, as well as showing a mini-max optimality against local alternative hypotheses where the distributions are close in terms of a probability metric. 
strengths_and_weaknesses: Strengths:
The paper is an original and important contribution that is well-written, having a comprehensive introduction and discussion of related work, goes into technical details with what appears to be rigorous theory. The paper is rather complete with key implications for future work on other distance or kernel based tests including tests of dependence. 

Weaknesses: 
The application and implication to some real scenarios is not completely discussed. In real cases where the data is collected (or will be collected) the sample sizes are fixed (or wouldn't want to be larger). In these cases, is the computational savings going to be meaningful? 
questions: Could cross-MMD be used to choose from amongst different kernel sizes and then use MMD for the test? 


Suggestion: Equation (9) it could be made clear to the reader what $z_\alpha$ is.
limitations: Requiring larger sample sizes for computational ease may not be warranted in situations where data collection is costly.
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: The paper proposes a variant of the quadratic time MMD test, whose null distribution is a standard normal, and whose statistic is computed based on splitting the available samples (e.g. in half).
This, while reducing the test-power, allows for easy test threshold estimation, and in particular avoid the permutation-based approach of the original quadratic time MMD test.
The authors formally derive this null distribution, and proove a number of properties of the resulting test, including consistency against fixed local alternatives, and finally a minimax rate-optimal power against local alternatives (Gaussian kernel only).
A number of experiments show that the theory translates into practice.


EDIT after rebuttal. The authors have provided an excellent and careful reply to all of my concerns. I have increased my score and think this is a great paper which should be accepted.
strengths_and_weaknesses: A great paper that tackles a worthwhile problem in a creative manner, and is thoroughly executed, in particular theory wise.
I am not sure about the practical impact of the paper though, because hundredfold computational improvements stated by the authors are somewhat academic, and do not hold true against careful implementations. In practice, I suspect the different to be much smaller, which then raises the question whether the loss in test power can really be justified.
The paper in my opinion also misses an important baseline test.


Originality:
The idea of building an MMD test with a normal null distribution has been around since the original MMD test has been first described.
Back then, however, the test statistic was linear time which meant the test wasn't as powerful.
It is great that the authors found a way to achieve a standard normal null using a quadratic time test, and I consider this very original work.

Quality: 
The paper is executed on a very high technical level, all claims have substantial proofs.
I in particular appreciate the generalization of Theorem 6 to the case where the kernel is allowed to change. Great work.
The minimax optimality is great too, though only established for Gaussian kernels (this should be stated in the abstract, where it appears that this is a general results)

Experimentally, I think one baseline that is clearly missing is the linear time test with learned features, described in https://arxiv.org/pdf/1605.06796.pdf. The paper reports experiments where a linear time test performs *better* than the standard quadratic time MMD. So this is highly relevant for this paper as well. In fact, I think the paper should not be published without these baselines.

On a side note, the authors do not experimentally demonstrate that their test has a well calibrated type 1 error for a given threshold, which I think would be a nice addition.

Another side note, the authors could run a standard goodness of fit test on the results in Fig 2, to test for normality.

Clarity: 
Clearly written throughout.

Significance: 
From a theoretical and methodological perspective, this work is significant, as it improves the ever growing set of tools around MMD tests.

However, I am not so sure about practical impact, and this is my main critique of the paper.
1. The authors argue that the permutation computations requires for the original test are prohibitive. In practice however, these are trivially parallelizable and not time critical. The idea behind the quadratic time MMD has always been "the best possible test for a given set of samples". Making that faster is useful, but not at the cost of sacrificing power, as in practice maximum power is usually what is wanted.
2. A more severe point is that the authors argue that the permutation test is in fact hundreds of times slower than their proposed test. This is only true asymptotically. In practice, permutation tests can be implemented in an extremely efficient manner by precomputing the kernel matrix, and then using memory sequential read operations to compute the permutations. As also mentioned above, this can be easily parallelized. E.g. https://arxiv.org/abs/1611.04488 reported that a naive python implementation (using precomputed kernel matrices) can be made >10x faster using these simple strategies, and before parallelization, plus another 5-10x using multithreaded implementations. In summary, with a little implementation effort, the computational gain (in wallclock time, with efficient implementations and parallel hardware), will surely not be hundredfold.

questions: See my points on the computational claims above.
I strongly suggest to add the linear time test baseline mentioned above.
limitations:
review_title: null

Meta-review: metareview: The paper proposes a variant of MMD test, which is asymptotically normal.  The proposed method is computed easily with data-splitting and studentization.  The paper provides a solid theoretical study about the consistency and minimax optimal rate for local alternatives.  The experimental results also show favorable results.  
The proposed simple method for obtaining the asymptotic normality is a significant advance in the topic of MMD, which is a popular statistic for comparing two distributions but suffers from the complicated asymptotics in the previous variants.  The theoretical study is solid.  We believe the work is worth being presented in NeurIPS.  
confidence: Certain
Decision: Accept