We propose novel statistics which maximise the power of a two-sample test based on the Maximum Mean Discrepancy (MMD), by adapting over the set of kernels used in defining it. For finite sets, this reduces to combining (normalised) MMD values under each of these kernels via a weighted soft maximum. Exponential concentration bounds are proved for our proposed statistics under the null and alternative. We further show how these kernels can be chosen in a data-dependent but permutation-independent way, in a well-calibrated test, avoiding data splitting. This technique applies more broadly to general permutation-based MMD testing, and includes the use of deep kernels with features learnt using unsupervised models such as auto-encoders. We highlight the applicability of our MMD-FUSE test on both synthetic low-dimensional and real-world high-dimensional data, and compare its performance in terms of power against current state-of-the-art kernel tests.
Paper
Similar papers
Peer review
Summary
[Update: After intensive discussion with the authors, I changed my score from 6 to 7. I further increase the score for "Contribution" from 2 to 3.] The paper introduces two new test statistics for permutation-based two-sample tests that are related to the MMD -- called FUSE_N and FUSE_1. These are motivated by selecting/combining good kernels for an MMD-based two sample test *without splitting* the data. The authors theoretically show that FUSE_1 corresponds to a (regularized) supremum of the MMD over the possible kernel combinations. FUSE_N, which empirically performs much stronger, is derived from FUSE_1 but where the kernels are weighted by their normalized (squared) MMD estimates instead of simply by their (squared) MMD estimates. There is no theoretical justification for using FUSE_N. The authors provide a theoretical power analysis of the proposed tests. Furthermore they run experiments that show their test has competitive power against a recent SOTA MMDAgg, while having a constant speed-up. The code is provided in a well-structured repository, such that it can be easily reproduced or the community can build on it. The paper also gives some general insights into what test selection strategies are generally possible when using a permutation test. Whilst this might not be very new in itself, having a clear presentation of the general thoughts in one place, might be very useful for scientist entering the field.
Strengths
- The delivered experiments are done very thoroughly and structured and the code is provided in a high quality. - The paper is very well written and clarifies important (although not really new) aspects of permutation-based tests in an accessible way. - The proposed test convinces in terms of power and runtime -- (although I am not 100% convinced by the speed-up over MMDAgg yet). - Originality and significance: Two-sample testing is an ongoing research area and improvements and new ideas are published at NeurIPS and similar conferences regularly. The community seems nevertheless relatively small. The test statistic seems new, although its motivation is not really clear.
Weaknesses
- The motivation for the proposed test statistic is not clear enough for me. FUSE_1 has somewhat a motivation (Sec. 4.1.) but: - it does not perform well and also the motivation does not arise from test power considerations. - It is well-known that selecting the kernel by maximizing the MMD is not a theoretically justified strategy (not scale invariant for example). - Sutherland et al (2017) give a criterion for optimizing the kernel in terms of asymptotic power, which results in optimizing a Signal-to-noise ratio. The normalized statistic FUSE_N seems to go in this direction, but there is no motivation for the normalization given. - Generally I am not really understanding the starting point for this paper. What motivated you to do this work and what where you trying to solve? In particular what is the similarity/difference to MMDAgg? - The test statistic has a parameter $\lambda$. For the theoretical results, $\lambda$ depends on the sample size. However, in the experiments (as far as I understood) $\lambda=1$ irrespectively of the sample size. How was this value determined and where is it discussed? And what is the recommended way to do this in practice?
Questions
Please also see my points in the weakness section. ### Questions I would like to discuss / understand: - What is the motivation for FUSE_N (except that it works well on your experiments)? - In Section A.4. you discuss the time-complexity relative to MMDAgg: - The difference is a factor of 2, so I do not think that the $\mathcal{O}$ notation is adequate here. - I also experienced that computing the kernel matrix is quite costly, compared to the permutations. But this only needs to be done once in both methods. Could it be that this difference is only visible because you used a very large number of permutations (20,000)? - l. 143 "without incurring Bonferrony-type multiple testing penalties": I understand that your method does not have such a penalty, but what exactly is it that leads to it? - What's the "N" or "1" in the naming of FUSE_ standing for? ### Questions / Remarks that do not require a response: - l.57 "Our unsupervised feature extraction method is extemely powerful": I do not see any support for this statement. I agree that it is very general, but whether it works well, I do not see evidence in the paper. - l.108f: Note that Kübler et al (AutoML Two-Sample Test) show in App. B.1 that the asymptotically optimal kernel for a fixed problem is indeed 1-dimensional. - l. 116: I do not think that permuting the samples is exactly the same as sampling from 1/2 (p+q). In the permutation there are always exactly half the samples still from p and half from q. Whilst drawing from 1/2(p+q) can by chance (and most likely will) result unbalanced.
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.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
nothing specific
Summary
This paper looks into the problem of permutation based kernel two-sample testing. The paper is motivated by two main challenges: 1. The first one being the fact that selecting kernel hyper-parameters through standard data splitting often reduces the statistical power due to using less data than we actually have. 2. The second challenge being that if we don't select a data specific hyperparameter for the test, a poor kernel choice will also lead to a decrease in statistical power. To tackle these problems, the authors proposed the MMD-FUSE method that can select kernels adapted to the data without data splitting. They first restate a result from Hemerik and Goeman Theorem 2 to justify/emphasise that any permutation invariant representation/function of the data can be used a statistic that have controlled type 1 error rate. In addition justifying the adequacy of median heuristics. The second contribution is that they proposed to combine multiple MMD via a set of kernels, and as such optimise the test power.
Strengths
The problem is well motivated as the trade off between data splitting to learn optimal kernel v.s. not splitting the data but selecting some heuristic kernel has been a long standing problem in the community. This authors explained their arguments very clearly. In addition, not only did they justify their method by showcasing the optimal MMD separation rate (Typo in line 290 btw), I appreciate they included a discussion with computationally faster sub-optimal tests to highlight between the trade off of test power and computational efficiency.
Weaknesses
The authors have discussed the weakness in their conclusion section so I don't think I have much to add. There is some recent work on not using permutation test at all to do two sample test, such as the work of Shekhar et al. 2022. I understand it is not necessary to compare the two types of approach but might be also good to mention non-permutation based approach as a side note to complete your already-detailed background section on testing? --- Shekhar et al. 2022 "A Permutation-free Kernel Two-Sample Test" arXiv:2211.14908
Questions
Although you have this prior over a set of kernels which this set could potentially be infinite, in practice you would sample from this prior to compute the test statistic right? How would your approach compare to standard Bongerroni correction technique or its extension weighted bonferroni correction? Would be interesting to hear about your comments on this.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
4 excellent
Presentation
4 excellent
Contribution
4 excellent
Limitations
No.
Summary
The paper studies the question of choice of critical values for the MMD test. The authors introduce a new MMD-based test that allows data-driven critical values based on permutation test, without the need to train a new kernel for every permutation. The main advantage of this new method is that it does not require sample splitting and the whole sample can be utilized for the computation of the test value. pros: - Experiments show improvements in some cases compared to sample-splitting methods. - The authors provide plenty of theoretical results in the appendix, including concentration results for the test both under null and alternative. cons: - The analysis is very conservative. At no point we can state that the distribution of the permuted test conditional on the observed data approximates that of the original test. Theorem 1 in particular is an upper bound, so there is no guarantees that the type I error of the test will be close to the desired level alpha. It is not clear how crude this upper bound is. I suggest this limitation should be emphasised in the text below. - I think theoretical analysis can be simplified. For example, proof of Theorem 6 does not have to reproduce Vershynin and Rudelson's proof, it is sufficient to integrate their bound. Also, it is not clear to me why it is necessary to include a proof of Bounded Differences Inequality in the appendix. Instead, one can refer to Lugosi et al Concentration Inequalities, Theorem 6.7. - There is no dependence of prior on the data in the experiments, please correct me if I'm wrong. other comments: line 174 m+ m -> n + m line 222 inconsistent notation MMD_k or MMD(.; k) line 829, display below: not sure why t appeared in second line and why it disappeared in the third line line 747 FUSE depends on lambda, what depends on t then? line 872 sup_y -> sup_rho? line 873 what is N? Serious concerns: - Section E.3 proof of Theorem 2 (which in my understanding one of the main theoretical contributions of the paper). Could the authors please elaborate on what happens below line 926 in detail? The sup over rho disappears in line 2. The "object" S_rho appears to be random, depending on the observed data Z, and it appears in the final bound thanks to the Markov inequality. - I can't find proof of Theorem 3 in the appendix with Ctrl + F To my best understanding if there are mistakes above section E.3 they should be fixable. ### My rating is conditional on whether the authors can fix these two serious concerns. Otherwise, the paper must be rejected.
Strengths
-
Weaknesses
-
Questions
-
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.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
-
Summary
This paper proposes a new statistic that can incorporate with the permutation test where we can learn features of data in an unsupervised way. From the perspective of testing, this paper contributes a new idea and paves a new way to perform two-sample testing without data splitting. If we can safely use all data to find a proper kernel, the test power will increase for sure. Theorems and proofs also verify the proposed methods.
Strengths
1. This paper focuses on an important problem: two-sample testing, which will be very important when generators are like humans nowadays. 2. The selected research direction, testing without data splitting, is very important. As demonstrated in summary, a proper kernel selection in this direction can directly boost the test power. 3. Experiments include simple data and complex data (Galaxy MNIST and CIFAR), verifying the effectiveness of the proposed statistics.
Weaknesses
1. The presentation can be improved a lot. The major issue is the lack of motivation for many choices. For example, what is the motivation to consider a mean kernel? what is the motivation to have this kind of design: log( E( exp( ) ) )? Can we consider more possibilities? The finding of this paper is exciting, however, it looks like a rush version. A revised version with a better presentation is required during the rebuttal. 2. Section 3 is a little bit long. The authors can consider introducing the theorem in the preliminary (as it is not proposed in this paper). Or the authors can remove the permutation test from Section 2. You can also consider merging Sections 2 and 3, making demonstrations more compact. 3. After removing the necessary parts in Sections 2 and 3, more experimental results can be put into the main body. For example, CIFAR results look very promising and should be moved into the main body. 4. In line 115, there is a notation typo. 5. Marks are recommended in Figure 1.
Questions
Please address the points in Weakness. The presentation can be improved to make this paper even better.
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.
Confidence
5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.
Soundness
4 excellent
Presentation
2 fair
Contribution
4 excellent
Limitations
N/A
Thank you for the answers. Could you please write here the modified lines 926 - 935 as a comment? It would help a lot to verify this. - Th 6 V&R. If you insist on having smaller constants that's fine, but I assume the constants are not important for your proof, and in case you actually have improvements for the constants, it should be a matter for a separate paper dedicated for the constants of H-W inequality. - Bounded Diff. Ineq. Lugosi; I understand that you version of bouded differences is stronger than classical form, but the version from the book is even stronger.
> Thank you for the answers. Could you please write here the modified lines 926 - 935 as a comment? It would help a lot to verify this. To summarise, only the definition of $S_\rho$, and lines 926-929 change. Running through the proof on line 926 gives the same result on 928, with the altered definition of $S_\rho$. However, we give a full proof (without align since Markdown won't handle it) below for understanding: For any $\rho$, we (re)-define $$ S_{\rho} = MMD^2(p, q; K_{\rho}) - \frac{KL(\rho, \pi)}{\lambda} - \frac{C \kappa (1 + \log \alpha^{-1})}{n} $$ [...] The Type II error under the full permutation set can be bounded as $$ \Pr_{p \times q}\left( \widehat{\operatorname{FUSE}}(Z) \le \text{quantile}_{1-\alpha_B, \mathcal{G}} \widehat{\operatorname{FUSE}}(\sigma Z) \right) $$ $$ \le \Pr_{p \times q}\left( \widehat{\operatorname{FUSE}}(Z) \le \frac{C_2 \kappa (1 + \log \alpha^{-1})}{n} \right)$$ since by Theorem 5 with $\lambda = cn / \kappa$, $$ \text{quantile}_{1-\alpha_B, \mathcal{G}} \widehat{\operatorname{FUSE}}(\sigma Z) \le \frac{C_2 \kappa (1 + \log \alpha^{-1})}{n}. $$ Now $$ \Pr_{p \times q}\left( \widehat{\operatorname{FUSE}}(Z) \le \frac{C_2 \kappa (1 + \log \alpha^{-1})}{n} \right)$$ $$ = \Pr \left(MMD^2(p, q; K_{\rho}) - \frac{1}{\lambda}KL(\rho, \pi) - \widehat{\operatorname{FUSE}}(Z) \ge S_{\rho} \right)$$ simply by rearranging terms and introducing the definition of $S_\rho$. The next steps are by $\sup f(\rho') \ge f(\rho)$, Chebyshev's, and Theorem 14: $$ \Pr \left(MMD^2(p, q; K_{\rho}) - \frac{1}{\lambda}KL(\rho, \pi) - \widehat{\operatorname{FUSE}}(Z) \ge S_{\rho} \right)$$ $$ = \Pr \left(MMD^2(p, q; K_{\rho}) - \frac{1}{\lambda}KL(\rho, \pi) - \sup_{\rho'} \left( \widehat{MMD}^2(Z; K_{\rho'}) - \frac{1}{\lambda}KL(\rho', \pi) \right) \ge S_{\rho} \right) $$ $$\le \Pr \left(MMD^2(p, q; K_{\rho}) - \widehat{MMD}^2(Z; K_\rho) \ge S_{\rho} \right) $$ $$\le \frac{1}{S_{\rho}^2} \mathbb{V} \left[\widehat{MMD}^2(Z; K_{\rho}) \right] $$ $$\le \frac{C_1}{S_{\rho}^2} \left( \frac{4\kappa MMD^{2}}{n} + \frac{\kappa^2}{n^2} \right). $$ This term is upper bounded by $\beta / 2$ if we set $$ S_{\rho}^2 > \frac{2C_1}{\beta}\left( \frac{4\kappa MMD^{2}}{n} + \frac{\kappa^2}{n^2} \right). $$ [Thus, the type II error rate will be controlled if l.924 is true] [with this new definition of $S_\rho$, the proof continues in exactly the same way, skipping line 929 which we used at the start] --- > Th 6 V&R. If you insist on having smaller constants that's fine, but I assume the constants are not important for your proof, and in case you actually have improvements for the constants, it should be a matter for a separate paper dedicated for the constants of H-W inequality. To be clear, V+R do not give numerical constants at all (only their existence is proved), which we need for our statements of Theorem 5. We do not intend to claim this as a contribution, the proof is only included so that we are not stating the numerical constants without justification. We provide the numerical constants in Theorem 5 even though they are not strictly necessary, as we hope they could be useful when adapting FUSE statistics to other settings. In particular, the constants help understand for which values of $\lambda$ the bounds of Theorem 5 hold, and also allows to understand the relation between the two RHS terms which can be matched by tuning $\lambda$. --- > Bounded Diff. Ineq. Lugosi; I understand that you version of bounded differences is stronger than classical form, but the version from the book is even stronger. We agree that Lugosi et al. is stronger than the classical form of bounded differences, however, we do not believe that it can straight-forwardly be used to prove Theorem 9, which is *not* a concentration bound. Theorem 9 instead relates the expectation $\mathbb{E} \widehat{\operatorname{FUSE}}_1$ to $\operatorname{FUSE}_1$ (l. 845), an expression involving the true MMD. There is no in high probability statement here, these quantities are deterministic, and require Theorems 11+12 to prove, rather than any concentration result. It *might* be possible to use Lugosi et al.'s result to prove concentration for $\widehat{\operatorname{FUSE}}_1$ around its mean instead, a slightly different but still interesting result that we can also show by combining Theorems 9 + 10. However, setting $f(Z) = \widehat{\operatorname{FUSE}}_1(Z)$ in their result, we still need a bound for $$ \sum_i (f(Z) - f(Z_i)^2 = \sum_i (\log \frac{E \exp(\lambda \widehat{MMD}^2(Z))}{E \exp(\lambda \widehat{MMD}^2(Z_i))})^2.$$ It is not obvious to us that a bound will follow that is any better than $O(1)$ in the sample size, while we need $O(1/n)$ to match our theorems. We would argue that even if it turns out this is possible, it is simpler just to work using Theorems 11+12, which have short and simple proofs; however, we are happy to discuss further if you have an idea how this could be done.
Thank you for corrections, that version seems to be correct. Thanks. > We will clarify this in the final version. FUSE depends on and the same appears on the RHS of the equation l.745. For the bound on -FUSE of l.746, FUSE depends on but the RHS holds for any in the range specified on l.747, in particular the parameter can be optimised to match the orders of the two terms on the RHS which is not possible for the bound on l.745. Sorry for coming back to this, but it just does not compute in my head why the lower bound depends on some $t$ instead of $\lambda$. You could as well optimise it wr.t. $t$ right away. Furthermore, in the proof of lower bound of Theorem 5 you write > l 834 for any function ... and $s > 0$ Then you set > Combining this with the above results and $t = -s$ In the conditions of the Theorem $t > 0$ and that means $s < 0$. Furthermore, you claim that the bound in the display above l830 holds for $|t| < ... $. Are you sure it holds for any negative $t$? Could you please double check the signs in the first inequality. My concern is that, although I am not very much familiar with PAC-Bayesian bounds, I thought that they don't usually guarantee any lower tails. Correct me if I'm wrong.
Thank you for engaging in the discussion. We agree that the current "Lower Bound" section (l.834 - l.837) of the proof of Theorem 5 is slightly confusing, even without the contradicting statements about $s$. We present a clearer reasoning below, which we hope address your concerns, and will also update the final version of the paper accordingly. > You could as well optimise it w.r.t. $t$ right away. We agree that this is probably simpler and have added an optimisation step below (see final lines of this comment). > In the conditions of the Theorem $t>0$ [...] > Furthermore, you claim that the bound in the display above l830 holds for $|t|<\dots$ . Are you sure it holds for any negative $t$? > Could you please double check the signs in the first inequality. The reasoning l.829-830 indeed holds for any $|t|< (4\sqrt{2} \sup_k \bar{U}_k)^{-1}$ (by Theorem 7). The upper bound of Theorem 5 corresponds to the result l.829-830 with $t = \lambda > 0$, divided through by $\lambda$. We note that although the signs in the first inequality of l.829-830 are correct, there is a typo and that the leading term $1/t$ should not appear. The rest of ll.829-830 is correct. > My concern is that, although I am not very much familiar with PAC-Bayesian bounds, I thought that they don't usually guarantee any lower tails. PAC-Bayesian bounds are often not simple and symmetric two-sided bounds on $|X - EX|$, but these do exist (e.g. Alquer, Ridgway, Chopin, 2016, On the properties of variational approximations of Gibbs posteriors). More typical is what we see here, that the upper and lower tails take somewhat different forms, e.g. the famous “small-kl” PAC-Bayes bound (Langford & Seeger, 2003; Maurer, 2004) is two-sided but asymmetric, so the upper and lower tails have slightly different rates. The literature is certainly more interested in the upper bounds, but the proof techniques apply similarly. **Revised "Lower Bound" section (l.834 - l.837)** For the lower tails, we note that for any function $f(Z, k)$ and $\lambda > 0, s > 0$, $$ \frac{1}{\lambda}\log E_{k \sim \pi(\langle Z \rangle)} \exp(\lambda f(Z, k)) $$ $$ \ge E_{k \sim \pi(\langle Z \rangle)}[f(Z, k)] $$ $$ = -\frac{1}{s} E_{k \sim \pi(\langle Z \rangle)} [\log (\exp \left( -s f(Z, k) \right))] $$ $$ \geq -\frac{1}{s} \log E_{k \sim \pi(\langle Z \rangle)} [\exp \left( -s f(Z, k) \right)] $$ where both inequalities are by Jensen's inequality, which gives $$ -\frac{1}{\lambda}\log E_{k \sim \pi(\langle Z \rangle)} \exp(\lambda f(Z, k)) \leq \frac{1}{s} \log E_{k \sim \pi(\langle Z \rangle)} [\exp \left( -s f(Z, k) \right)]. $$ for $s > 0$. Using this result with the appropriate function $f$ for $\widehat{\mathrm{FUSE}}^1$ and $\widehat{\mathrm{FUSE}}^N$, together with the bound l.829 and l.831 (over the defined ranges) applied to the log-expectation term with $ t=-s $ (which is negative and satisfies the condition $ |t|< (4\sqrt{2} \sup_k \bar{U}^k)^{-1}$), we find that $$ -\widehat{\mathrm{FUSE}}^1(Z) \le_{1-\delta} \frac{4\kappa^2 s}{n(n-1)} + \frac{\log\frac{1}{\delta}}{s}, $$ $$ -\widehat{\mathrm{FUSE}}^N(Z) \le_{1-\delta} \frac{16 s}{n(n-1)} + \frac{\log\frac{1}{\delta}}{s}. $$ Unlike the upper bounds, where rates depend on setting $\lambda \asymp n$, we can freely choose $s$ here within the specified range to optimise the lower bounds. A simple further bound on these follows by setting $s$ to its extremal values, giving: $$ -\widehat{\mathrm{FUSE}}^1(Z) \le_{1-\delta} \frac{\sqrt{2} \kappa (\frac{1}{4} + 8\log\frac{1}{\delta})}{\sqrt{n(n-1)}}, $$ $$ -\widehat{\mathrm{FUSE}}^N(Z) \le_{1-\delta} \frac{\sqrt{2} ( \frac{1}{2} + 16\log\frac{1}{\delta})}{\sqrt{n(n-1)}}. $$
Once again, your lower bounded the moment generating function for negative $\lambda$, while it is required to be upper-bounded. Just a quick common sense test: a lower bound for $f(Z)$ is an upper bound for $-f(Z)$. For an upper bound on $-f(Z)$ you need to have an upper bound on $ E \exp( - \lambda f(Z))$ for $\lambda > 0$. I only see a lower bound on $ E \exp( - \lambda f(Z))$ in your answer above. I really doubt the Jensen trick alone can give you required bound.
Apologies, we are having difficulty understanding your question - which exact step of our proof do you have trouble with? We have written it out in greater detail below so that if you have any specific issue it will be easier to see. $\lambda$ is a **fixed non-negative parameter** of FUSE rather than a dummy variable so we are not sure where we set it negative. We wonder if there is confusion about the term $f(Z)$: we are not writing $f(Z) = FUSE_1$, we are writing $f(Z) = MMD(Z)$. With first the setting $f(Z) = FUSE_1$ it is true we would need to upper bound $E \exp(-s f(Z))$ for positive $s$, but we are considering the second. This makes our proof somewhat different in formulation from usual concentration proofs. ### Highly detailed proof For $FUSE_1$ with parameter $\lambda > 0$, we have $$ -FUSE_1 = -\frac{1}{\lambda}\log E_{k \sim \pi(\langle Z \rangle)} \exp(\lambda MMD(Z, k)) $$ Now apply Jensen with $E\exp(X) \ge \exp(EX)$ to the above, noting that the inequality is reversed due to the negative sign and $\lambda > 0$, and that the log and exp terms cancel: $$ -\frac{1}{\lambda}\log E_{k \sim \pi(\langle Z \rangle)} \exp(\lambda MMD(Z, k)) \le - E_{k \sim \pi(\langle Z \rangle)} MMD(Z, k).$$ Next introduce the dummy variable $s > 0$ and see that $$ - E_{k \sim \pi(\langle Z \rangle)} MMD(Z, k) = \frac{1}{s} \times (- s E_{k \sim \pi(\langle Z \rangle)} MMD(Z, k)) = \frac{1}{s} \log \circ \exp (- s E_{k \sim \pi(\langle Z \rangle)} MMD(Z, k)). $$ Since $\frac{1}{s} \log$ is positively monotonic, we can apply Jensen again to $\exp(E X) \le E \exp(X)$ and find $$ \frac{1}{s} \log \circ \exp (- s E_{k \sim \pi(\langle Z \rangle)} MMD(Z, k)) \le \frac{1}{s} \log E_{k \sim \pi(\langle Z \rangle)} [\exp \left( -s MMD(Z, k) \right)].$$ Finally, we apply the bound from l.829, to find $$ -FUSE_1 \le \frac{1}{s} \log E_{k \sim \pi(\langle Z \rangle)} [\exp \left( -s MMD(Z, k) \right)] \le_{1-\delta} \frac{4\kappa^2 s}{n(n-1)} + \frac{\log\frac{1}{\delta}}{s} $$ Which gives the overall result. Note that this final inequality is a $1-\delta$ high probability statement arising from the use of Markov’s inequality in l.829 first inequality. This is essentially a more detailed form of the proof while using $f(Z, k) = MMD(Z, k)$. The result for $FUSE_N$ follows by instead setting $f(Z, k)$ to the normalised MMD.
I see, thank you for clarifications. I would suggest to show the bound for optimal t in Theorem 5 in the final version, I think it looks more clear. Congratulations on your paper!
Thank you for your time and attention to detail in our proofs, we really appreciate the feedback and suggestions that will make the proofs more easily understandable for the readers!
Thanks for the rebuttal
After reading the rebuttal, I have no further questions. Thank you.
Glad to hear all your questions have been answered. Thank you again for the very supportive comments!
Thanks for the rebuttal
Thank you for the detailed rebuttal. In particular regarding the motivation of MMD_N. I want to strongly encourage you to bring this motivation at least in parts to the main paper. Thanks also for providing the time comparison, that is indeed good to know, I somewhat thought the kernel compuation was the bottleneck. I have further **Question** left regarding MMDAgg: - My take from your experiments and analysis is that your method powerwise performs similarly to MMDAgg, but is twice as fast. This is nice but not groundbreaking I would argue. - But you say that when considering more and more kernels then your method has an advantage, because of the multiple corrections in MMDAgg. I don't quite see this from the theory. Is it possible to provide an experiment that showcases this? Overall it would be nice to have some setting where you show that MMDAgg has some power-problems. [sorry for being a bit late]
Thank you for engaging in the rebuttal. We will definitely be incorporating the additional motivation arguments in the final version of the paper. Let us bring some clarifications regarding the following sentences from our "Additional Motivation for our proposed statistics and work" rebuttal related to the theoretical power of MMD-FUSE and of tests based on multiple testing in the regime with an increasing number of kernels/sub-tests. > This can be beneficial in the case where the number of kernels considered increases (is large). In that setting, the multiple testing approach MMDAgg combines more and more kernels, the level needs to be corrected differently depending on the number of kernels, and it is not theoretically guaranteed how the power of MMDAgg behaves in that setting (i.e. it could maybe go to zero). When performing multiple testing, in order to correctly control the type I error at level $\alpha$, the level of the $T$ sub-tests need to be corrected. The simplest method for that is the Bonferroni correction which guarantees that the overall test has level $\alpha$ if the $T$ sub-tests are each run with level $\alpha/T$. Loosely speaking, if the number of sub-tests $T$ becomes very large, every sub-test needs to be run with very small level which means that the sub-tests are very conservative (less likely to reject), so the overall test has low power. In fact, for the Bonferroni correction, it can be theoretically proved that the power goes to zero in the limit of $T$ tending to infinity. This is because the tests reject if the statistic (e.g. MMD) is strictly greater than the $(1- \alpha/T)$-quantile, but in the limit this becomes the $1$-quantile which is essentially the maximum, so the sub-tests would never reject. Instead of relying on a Bonferroni correction, the authors of MMDAgg propose using $u/T$ where $u$ is chosen to be the largest value (using data) such that the overall test has estimated level $\alpha$. It is clear that $u$ is larger than $\alpha$, hence their method is more powerful than performing a Bonferroni correction. However, the authors do not theoretically study the behaviour of the MMDAgg test in the limit where the number of sub-tests $T$ (each with a different kernel) tends to infinity. The power of the test in that setting could, as in the Bonferroni case, simply go to zero. As we mentioned in the rebuttal (see quote below), our theoretical study not only covers the case where the number of kernels (analogous to $T$ above) increases to infinity, but FUSE is actually well-defined in the limit where the average becomes a distribution over kernels, which is clearly not the case of any test relying on multiple testing. This is a real advantage of our proposed method compared to others such as MMDAgg. > We do not suffer from such issues with FUSE as even when increasing the number of kernels we still have only one statistic and quantile. The FUSE statistic is even defined in the limit of an infinite number of kernels (continuous/uncountable collection of kernels) by considering distributions on the space of kernels, which is clearly not the case for MMDAgg (only defined for discrete collection of kernels). Moreover, while the MMDAgg approach is only useful for hypothesis testing, having a quantity like FUSE combining multiple kernel-based measures of distance with exponential concentration bounds could be of interest in a wide range of applications. As mentioned above, the *theoretical* power of MMDAgg has not been studied by the authors in the setting of increasing $T$, and it is unclear what the limiting behaviour would be. However, we do point out that the authors consider this setting *empirically* and observe in their experiments (MMDAgg Section 5.7) that MMDAgg retains power when combining kernels with multiple bandwidths. For this reason, it is challenging to provide an "experiment that showcases" the power advantage when considering "more and more kernels". We argue that our experiment distinguishing between CIFAR-10 and CIFAR-10.1 in Appendix A.5 provides a setting where MMD-FUSE achieves significantly higher power than MMDAgg while being twice as fast. We also emphasise that, unlike our proposed MMD-FUSE test, the MMDAgg test has not been proven to achieve the optimal MMD separation rate, and MMD-FUSE also has the advantage of being a single statistic.
Reply
Thank you for the additional clarification. Let me rephrase my understanding regarding MMD Fuse vs MMDAgg: - The authors of the present paper show beneficial behavior for the case of considering many kernels. - For MMDAgg this limiting behavior is neither theoretically nor empirically well-studied. The author do also not provide experiments on this. Ergo: - MMDFuse has a more complete theory than MMDAgg - Whether it performs better when considering many kernels **is not known** > We argue that our experiment distinguishing between CIFAR-10 and CIFAR-10.1 in Appendix A.5 provides a setting where MMD-FUSE achieves significantly higher power than MMDAgg while being twice as fast. Sure, on this setting MMDFuse is better. But on other settings MMDAgg is better by similar margins (example Figure 1 bottom right). So no general winner. Also this setting does also not address the question of using more kernels. --- In conclusion my judgement remains the same, because the shown improvements over MMDAgg are mainly a factor 2 in runtime.: 6: Weak Accept: Technically solid, **moderate-to-high impact** paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
As requested, we have run an additional experiment increasing the number of kernels for MMD-FUSE and for MMDAgg from 10 to 1000 kernels. We consider the problem of distinguishing between a uniform distribution and a perturbed uniform distribution, having 500 samples from each. For both tests, both Gaussian and Laplace kernels are used with 5 to 500 bandwidths each (the bandwidths correspond to a finer discretisation of the collection l.669). We have updated the anonymised repository (the link can be found l.655) with the reproducible code for this experiment in extra_experiment.ipynb, further details about the experiment can be found there. The power results averaged over 200 repetitions are the following (we are not able to attach a plot in OpenReview sorry): - number of kernels : [10, 50, 100, 200, 400, 600, 800, 1000] - power of MMD-FUSE: [0.94, 0.905, 0.9, 0.91999996, 0.91999996, 0.93, 0.93, 0.91499996] - power of MMDAgg: [0.745, 0.72999996, 0.74, 0.73499995, 0.715, 0.71999997, 0.73499995, 0.74] First, we observe that MMD-FUSE achieves significantly higher power than MMDAgg in this setting. Second, we observe that both MMD-FUSE and MMDAgg retain their power when increasing the number of bandwidths. As previously mentioned, this matches the observations of the authors of MMDAgg presented in their Section 5.7, the intuition behind it being that a discretisation of 10 bandwidths is enough to capture all the information in this problem and that a finer discretisation does not help. > The authors of the present paper show beneficial behaviour for the case of considering many kernels. Yes, thank you for recognising this. > For MMDAgg this limiting behaviour is neither theoretically nor empirically well-studied. The point we are making is that MMD-FUSE is theoretically well-defined even in the limit while the limiting behaviour of MMDAgg has not been theoretically studied by the authors (though they have studied it empirically in their Section 5.7). > The author do also not provide experiments on this. We have now provided the results and reproducible code for the requested experiment. > MMDFuse has a more complete theory than MMDAgg We are happy to hear you are satisfied with the theoretical completeness of our paper. > Whether it performs better when considering many kernels is not known We do not observe power deterioration when considering many more kernels. — We appreciate your engagement during this discussion period and hope we have addressed your concerns in our replies and with the additional experiment. If so, we ask if you would consider increasing your score.
Thanks for the experiments
Thank you very much for the additional experiments (I was actually not aware that you were planning to add those). I think adding these in would nicely show that neither MMDAgg nor MMDFuse (empirically) suffer a power loss from fine-graining the kernels. Of course it becomes unnecessarily expensive. For MMDFuse you provide theoretical results that this holds true, whilst for MMDAgg this is not known to be guaranteed. Overall I will increase my score from 6 to 7. I think the authors have sharpened their comparison to MMDAgg with the additional experiments. This should be helpful to readers to clearly see the merits.
My concerns are addressed well.
Thanks for addressing my concerns. It is necessary to revise the paper to increase its readability for future readers.
We are happy to hear your concerns have been addressed. Thank you for the feedback provided, we believe that incorporating it in the final version will greatly improve the readability of the paper.
Decision
Accept (spotlight)