A Kernel Distribution Closeness Testing

Authors: Zhijian Zhou, Liuhua Peng, Xunye Tian, Feng Liu
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: hypothesis testing, Maximum Mean Discrepancy, distribution closeness testing, two samples testing

Abstract:
The \emph{distribution closeness testing} (DCT) assesses whether the distance between an unknown distribution pair is at least $\epsilon$-far; in practice, the $\epsilon$ can be defined as the distance between a reference (known) distribution pair. However, existing DCT methods are mainly measure discrepancies between a distribution pair defined on discrete one-dimensional spaces (e.g., total variation on a discrete one-dimensional space), which limits the DCT to be used on complex data (e.g., images). To make DCT applicable on complex data, a natural idea is to introduce the \emph{maximum mean discrepancy} (MMD), a powerful measurement to see the difference between a pair of two complex distributions, to DCT scenarios. Nonetheless, in this paper, we find that MMD value is less informative \textcolor{blue}{when assessing the closeness levels for multiple distribution pairs with the same kernel, i.e., MMD value can be the same for many pairs of distributions that have different norms in the same \emph{reproducing kernel Hilbert space} (RKHS). To mitigate the issue, we propose a new kernel DCT with the \emph{norm-adaptive MMD} (NAMMD) by scaling MMD with the norms of distributions, effective for kernels $\kappa(\x,\x')=\Psi(\x-\x')\leq K$ with a positive-definite $\Psi(\cdot)$ and $\Psi(\bm{0})=K$.} Theoretically, we prove that our NAMMD test achieves higher test power compared to the MMD test, along with asymptotic distribution analysis. We also present upper bounds on the sample complexity of our NAMMD test and prove that Type-I error is controlled.  We finally conduct experiments to validate the effectiveness of our NAMMD test.

Decision: reject
Reviewer scores: 3, 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730526727462

thread_type:
official_review

<thread_object>
creator: reviewer_8gf1

<content>
summary:
This paper proposes an improved Maximum Mean Discrepancy (MMD) method, namely norm-adaptive maximum mean discrepancy (NAMMD), for testing distribution similarity. By incorporating hypothesis testing, this method introduces a practical approach for distribution closeness testing in real-world scenarios.

strengths:
Rigorous theoretical analysis provides reliability for the paper.
A comprehensive background description makes it easy for readers to understand the problem the paper aims to address.

weaknesses:
The author does not explain why the definition of NAMMD is formatted as Equation (1). Although the author proves the effectiveness of NAMMD from the perspectives of complexity, hypotheses testing power, and closeness testing power in sections 4.1, 4.2, and 4.3, the fundamental motivation for designing NAMMD is not clearly described.

questions:
As the author stated, MMD has an inherent issue in closeness testing: "the same MMD value may reflect different levels of closeness between distributions, which makes it less informative." Why doesn't the author redesign a kernel-based closeness testing method? Such approach seems to be able to circumvent the inherent problems of MMD and further address the closeness testing of high-dimensional data.

Why the definition of NAMMD is formatted as Equation (1) and sufficient to achieve the desired goal? This point lacks explanation. After defining NAMMD, the authors do not provide a corresponding justification.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730666051256

thread_type:
official_review

<thread_object>
creator: reviewer_u8wh

<content>
summary:
This paper proposed the norm-adaptive MMD as a testing statistic for distribution closeness testing. Compared with the MMD statistic, it scales MMD with the norm of distributions in RKHS. Theoretical analysis and numerical study demonstrate the superior performance of this framework.

strengths:
1. The paper is well-written, with explicit technical assumptions and technical proofs included. 
2. The numerical study is solid in justifying the good performance of this framework.  
3. Based on the theoretical analysis and numerical study, I am convinced that NAMMD is a reasonable framework.

weaknesses:
1. The threshold plays a key role in hypothesis testing. Under the null hypothesis test, the authors utilize the permutation test to estimate the threshold, which is commonly used in literature. Under the case where $NAMMD(P,Q)=\epsilon$, the authors estimate it based on the variance of asymptotic distribution, which further approximates it using empirical variance estimator $\sigma_{X,Y}$. Can the authors provide more theoretical analysis regarding this estiamtor (such as bias, variance, etc?) to justify the soundness of this approximation?
2. Can the authors elaborate more on how to modify NAMMD in the fusing statistics approach?

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1730694299276

thread_type:
official_review

<thread_object>
creator: reviewer_tqlo

<content>
summary:
The paper develops a new distribution closeness testing method, called norm adaptive MMD.

MMD can be used to measure the discrepancy between two distributions. The statistical properties of MMD-based estimators are well-known, and these can be used to create closeness testing methods. 

The naive MMD-based method, however, is not very informative, because, the closeness measured by MMD varies with the norms of the distributions. This implies that pairs of distributions with different variances can have the same MMD value, even though these pairs of distributions visually can be very different. To overcome this issue, the authors propose to scale the MMD values with the norms of the distributions. This new method is called Norm-Adaptive MMD (NAMMD).

strengths:
* The paper is well-written and easy to follow.
* The new method is simple and the paper provides new theoretical results for the proposed NAMMD estimator.
* The paper provides experiments on five datasets, and demonstrates that it can work better than MMD and Canonne's tests.

weaknesses:
The paper claims that standard closeness measures don't work well on complex, high-dimensional datasets, e.g. images. 
The provided numerical experiments show that this distribution closeness works better than other hypothesis tests on benchmark datasets, but it doesn't demonstrate how this improved test can make a difference in some important real-world applications, e.g. on high-dimensional images.

questions:
Would it be possible to show how the proposed distribution closeness test can make a difference in some important real-world applications?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717448525

thread_type:
official_review

<thread_object>
creator: reviewer_txyq

<content>
summary:
The authors study distribution closeness testing (DCT) using the maximum mean discrepancy (MMD). 
They find that the MMD can be the same for distributions with different norms in a reproducing kernel Hilbert space (RKHS). 
To address this issue, they propose a novel kernel DCT with a norm-adaptive MMD (NAMMD), which scales the MMD along with the norms of the distributions in the RKHS. 
Theoretical results for the NAMMD test are presented, which demonstrate that the proposed DCT achieves higher test power compared to the standard MMD test. Furthermore, they derive upper bounds on the sample complexity of the NAMMD test. Through empirical analysis, they demonstrate that their kernel DCT can effectively test the closeness of two distributions using both synthetic and real-world data.

#### A brief disclaime:
Please note that my review reflects a limited level of expertise in the specific area for this study. I would appreciate it if this could be taken into account when considering my assessment.

strengths:
* An important issue of existing DCT using the MMD has been identified, specifically the MMD can be the same for distributions with different norms in a reproducing kernel Hilbert space.
* Rigorous theoretical results are provided.
* Sufficient experiment results are included.

weaknesses:
#### Major Weaknesses:
* The issue identified by this study may reflect a different perspective on a known issue of the existing MMD DCT related to kernel selection (see quesions below).

#### Minor Weaknesses:
Lines 475-476:
Does “$\|z_0, z_1\| \le \|z_0, z_2\| \le \cdots \le \|z_0, z_9\|$” mean “$\|z_0 - z_1\| \le \|z_0 - z_2\| \le \cdots \le \|z_0 - z_9\|$”?

questions:
The selection of kernels and the configuration of kernel hyperparameters may be related to the issue identified in this study. 
Some research has addressed issues related to kernel selection and its hyperparameter configuration ([1], [2] and [3]).
I have questions regarding both determination of kernel hyperparameters and kernel selection. 
These considerations could be beneficial for clarifying the challenges and advancing your method.

#### Questions Regarding Kernel Parameter determination.
In lines 106-107, it is possible to adjust the magnitude of the norm by modifying the length-scale hyperparameter $\gamma$ of the Gaussian kernels. Specifically, using a smaller value of $\gamma$ in Figure 1b than in Figure 1a will yield norms of the same magnitude. 

1. In your numerical experiments, did you observe any significant changes in test results by manually adjusting kernel hyperparameters, such as those of the Gaussian kernels?
2. For existing MMD methods, can the selection of kernel parameters help mitigate the issues identified in this study? If so, what are the strengths and weaknesses of your approach compared to other existing MMD DCT methods that adjust kernel parameters ([1], [2] and [3])?


#### Questions Regarding Kernel Selection.
3. Does the issue observed in this study, i.e., the phenomenon where the MMD can be the same for distributions with different norms in a reproducing kernel Hilbert space (RKHS), also occur for the MMD DCT when using the following two types of kernels?

   - Unbounded kernels: For instance, kernels defined by polynomials or matrix products are unbounded but (could be) available within your theoretical framework when using observational data from bounded variables.

    - Kernels with a positive limit at infinity: kernels satisfying $\lim_{\\| \mathbf{x}-\mathbf{x}' \\|_{\infty} \rightarrow \infty} \kappa(\mathbf{x}, \mathbf{x}') = c > 0$.  An example might be a kernel defined as $\kappa (\mathbf{x}, \mathbf{x}') = \exp \left( - \frac{ \\|\mathbf{x} - \mathbf{x}'\\|^2 }{2\gamma} \right)$
    when $\\| \mathbf{x} - \mathbf{x}' \\|\_{\infty} < K$, and otherwise $\kappa(\mathbf{x}, \mathbf{x}') =c$ with positive constats $K$ and $c$.


###### Background for Questions 3.
In lines 084–102 and Figure 1, a kernel has been used such that 
$\lim_{\\|\mathbf{x}-\mathbf{x}'\\|_{\infty} \rightarrow \infty} \kappa(\mathbf{x}, \mathbf{x}') = 0$. 
This phenomenon could arise when a kernel fails to effectively measure similarity between distant data points. I am concerned that this issue might result from choosing a kernel that cannot capture similarity for data points beyond a certain distance.

---

[1] Biggs, F., Schrab, A., & Gretton, A. (2024). MMD-FUSE: Learning and combining kernels for two-sample testing without data splitting. Advances in Neural Information Processing Systems, 36.

[2] Schrab, A., Kim, I., Albert, M., Laurent, B., Guedj, B., & Gretton, A. (2023). MMD aggregated two-sample test. Journal of Machine Learning Research, 24(194), 1-81.

[3] Schrab, A., Kim, I., Guedj, B., & Gretton, A. (2022). Efficient Aggregated Kernel Tests using Incomplete $ U $-statistics. Advances in Neural Information Processing Systems, 35, 18793-18807.

---
### *The following comment was added to my initial review on December 17, 2024*


Dear Authors,

Thank you for your submission and the effort you have invested in this work. I appreciate the depth of your research and the importance of the problem you are addressing.

I would like to sincerely apologize for the delay in identifying and communicating the following issue. After the review period, I reported a potentially critical error in the manuscript to the Area Chair. Under the guidance of the Area Chair, I have now updated my official review to reflect this concern. I deeply regret the delay in providing this feedback and appreciate your understanding.



---

Main Comment:  

The concern pertains to the proofs regarding the test power of the proposed method. Specifically, it appears that the test statistic under the null hypothesis was used to compute the test power, whereas the test statistic under the alternative hypothesis should have been employed. This discrepancy may impact the conclusions regarding the advantage of the proposed method, NAMMD, over MMD.

In particular, the following test statistic seems to have been used in the calculation of the test power:

$$
r_N = \frac{r_M }{4K - \\| (\mu_P + \mu_Q)/\sqrt{2} \\|^2\_{\mathcal{H}\_{\kappa}}}. \tag{E1}
$$

According to lines 1172–1174, this test statistic (Equation (E1)) assumes that $ \mu_P = \mu_Q = (\mu_P + \mu_Q)/2 $, as discussed in lines 848–849. Thus, it appears to be derived under the null hypothesis.

However, since the test power is defined as the probability of rejecting the null hypothesis under the alternative hypothesis, the appropriate test statistic should instead be:

$$
r_N = \frac{r_M}{4K - \\| \mu_P \\|^2\_{\mathcal{H}\_{\kappa}} - \\| \mu_Q \\|^2\_{\mathcal{H}\_{\kappa}}}. \tag{E2}
$$

The proof of Theorem 10 appears to rely on Equation (E1). Specifically, the calculations in lines 1221–1225 employ Equation (E1) rather than Equation (E2). Furthermore, when Equation (E2) is used, the test powers $ p_M $ and $ p_N $ for MMD and NAMMD, respectively, appear identical under the alternative hypothesis (lines 1211–1218).

This raises a concern that the test powers of both MMD and NAMMD may indeed be identical, which could imply that the proposed method does not offer a significant theoretical advantage over MMD.

---

Additional Comment:  

While this issue may be critical to the theoretical justification of your method, I acknowledge that the numerical experiments in your paper demonstrate the effectiveness of the proposed approach. Therefore, it remains unclear why a discrepancy arises between the theoretical analysis and the numerical results.

If your method does indeed exhibit superior performance in the numerical experiments, I encourage you to investigate this phenomenon more deeply. For example, it may be beneficial to analyze whether a specific distribution, such as the t-distribution, emerges in the proposed approach. Additionally, since both the MMD and the NAMMD exhibit different convergence orders under the null and alternative hypotheses, it is essential to evaluate the tail behavior of their asymptotic distributions under the alternative hypothesis. More specifically, carefully revisiting the two equations presented in lines 1211–1218 could help clarify the observed differences.

Identifying the root cause of this discrepancy might be challenging, but I believe such an analysis will not only strengthen the validity of your results but also contribute to further advancing your proposed method.

---
**Update on Scores**:  *(Added to my additional feedback on January 6, 2025)* 

Based on the identified issue, I have updated the following scores to better reflect the paper's current state:  

- **Soundness**: Changed from "4: excellent" to "1: poor" due to the critical error in the proof.  
- **Rating**: Changed from "8: accept, good paper" to "3: reject, not good enough" as the identified issue significantly impacts the validity of the paper's main contributions.  

---

Once again, I apologize for the delay in raising this concern, and I greatly appreciate your understanding. Please feel free to clarify or address this issue in your response.

Best regards,  
Reviewer TXYq
</content>
</thread_object>

</thread>
<thread>
creation date:
1732785366480

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revision Details According to Reviews

comment:
We sincerely thank the reviewers for their insightful comments, which have greatly contributed to improving our work. We have carefully revised our paper based on the discussions and feedback provided.

>Based on the discussions with **Reviewer TXYq**, we have adopted a more cautious tone in the paper to avoid potential overclaims, with revisions as follows.
- We emphasize in the **abstract, introduction, and other relevant parts** that this paper's analysis applies to **kernels with form** $\kappa(x,x')=\Psi(x-x')\leq K$ for a positive-definite $\Psi(\cdot)$ and $\Psi(0)=K$, which includes the Gaussian, Laplace, Mahalanobis, and Deep kernels (some frequently used kernels in kernel-based hypothesis testing).
- We emphasize in the **abstract, introduction, and other relevant parts** that the issue identified in the paper applies to assessing the closeness levels for multiple distribution pairs using **the same kernel**.
- We update **Figure 1 caption** to indicate that it represents **an empirical example** with Gaussian kernel, but extendable to other kernels with above form.
- We add **a paragraph in the introduction** to include the current **kernel selection methods** for TST and discuss the global kernel selection for DCT, where identifying the optimal global kernel remains an future work. This is due to the fact that deriving a test power estimator for DCT with multiple distribution pairs and selecting a optimal global  kernel based on this estimator remains an open question and poses a significant challenge. 
- We also add **a paragraph in relevant work** about **background of kernel selection methods** for TST with MMD and further discuss kernel selection for NAMMD in DCT.
- We add content immediately after **Theorem 10(original Theorem 9)** to discuss the improved test power of NAMMD compared to MMD under **the identical optimal kernel** for **two-sample testing**.
- We add content immediately after **Theorem 12(original Theorem 11)** to discuss the improved test power of NAMMD compared to MMD under **respective optimal kernels** for **distribution closeness testing**.
- We add further details regarding the above two points in **Appendix B.10**.
- We add experiments comparing NAMMD and MMD with their respectively and empirically selected kernels in distribution closeness testing. The experiments results is given in Table 5 in **Appendix D.6**.
- We add additional details on **kernel selection** in experiments.
- We present the kernel selection for distribution closeness testing **as a future work in conclusion**.
- We add a **Limitation Statement** in **Appendix C.4** regarding the applicability of our findings to other kernels, where the norms of distributions may increase in accordance with increases in the data variance, including the discussions on unbounded kernels and kernels with a positive limit at infinity. 

>Based on the discussions with **Reviewer TqLo**, we present three case studies (with details on pages 9 and 10) demonstrating the application of our NAMMD test on complex, high-dimensional datasets as follows.
- Testing whether the pre-trained ResNet50 performs similarly for **original ImageNet and its variants (ImageNet-SK, ImageNet-R, Imagenet-V2, ImageNet-A)**. The ground-truth similarities are measured by the accuracy margin (the difference in model accuracy between the ImageNet and its variant) with ground-truth labels. We demonstrate that our NAMMD distance (do not need ground-truth labels) effectively reflects the closeness relationships indicated by the accuracy margin, and the NAMMD test successfully identifies these relationship, as shown in **Figure 3**.
- Testing whether the pre-trained ResNet50 performs similarly for each class of **the original ImageNet and ImageNetV2**. Similar to the first case, but considering the limited sample size, the sample sizes for each class of ImageNet and ImageNetV2 are 50 and 10, respectively. The ground-truth similarities are measured by the confidence margin (as the accuracy margin may be dispersed and fail to reliably capture differences in model performance) with ground-truth labels. We also demonstrate that our NAMMD distance effectively reflects the closeness relationships indicated by the confidence margin, and the NAMMD test successfully identifies these relationships, as shown in **Figure 4**.
- Testing whether the trained ResNet18 performs similarly for **original CIFAR10 and CIFAR10 after adversarial perturbation**. As expected, a larger perturbation generally result in poor model performance on the perturbed CIFAR10 dataset. We demonstrate that our NAMMD distance effectively reflects the level of adversarial perturbation, and the NAMMD test successfully assesses different adversarial perturbation levels, as shown in **Figure 5**.
- We present detailed formalizations of accuracy and confidence margins in **Appendix D.5**.
- We revise the **last paragraph of introduction** to include the above-mentioned three case studies.
</content>
</thread_object>

</thread>
<thread>
creation date:
1739532114152

thread_type:
public_comment

<thread_object>
creator: ~feng_liu2

<content>
title:
Post-decision statement: Factual error in Reviewer TXYq's after-dicussion comments (Part I: Testing threshold in two-sample testing)

comment:
Dear Reviewer TXYq,

Thank you for reading our paper and for your further reviews. Unfortunately, **the issue was raised 20 days after the rebuttal period**, and we cannot reply through the OpenReview system after the author rebuttal deadline. Although we have reached out to ICLR program chairs via email, we were still unable to resolve this matter.

We address your concern below and hope that future readers will find our clarification helpful. Although the paper has already been rejected (based on meta-review, the decision is made **mainly based on your new concern**, and **the score changes from 8866 to 8863**), we appreciate the opportunity to provide further insights and contribute to the ongoing discussion with you.

>[Q1] In particular, the following test statistic seems to have been used in the calculation of the test power:
$$
r_N = \frac{r_M}{4K-||(\mu_P+\mu_Q)/\sqrt{2}||^2}\ .
$$
According to lines 1172–1174, this test statistic (Equation (E1)) assumes that $\mu_P=\mu_Q=(\mu_P+\mu_Q)/2$, as discussed in lines 848–849. Thus, it appears to be derived under the null hypothesis. However, since the test power is defined as the probability of rejecting the null hypothesis under the alternative hypothesis, the appropriate test statistic should instead be:
$$
r_N = \frac{r_M}{4K-||\mu_P||^2+||\mu_Q||^2}\ .
$$

[A1] We believe there is a **key misunderstanding about the testing thresholds $r_M$ and $r_N$.** These thresholds should be determined based on **the null distribution** [1-4] (the distribution of the test statistics under the null hypothesis, i.e., $H_0: P = Q$ for Theorem 10 ). **In contrast,**, in your additional comments, we found that you might think the **testing thresholds** should be from **the alternative distribution** (the distribution of test statistics under the alternative hypothesis, i.e., $H_1:P\neq Q$), **which is incorrect**.

To clarify this point, we first introduce the background of hypothesis testing. Hypothesis testing evaluates whether there is enough evidence to reject a null hypothesis $H_0$ in favor of an alternative hypothesis $H_1$. The process involves defining a **test statistic $T$** and comparing it to a **testing threshold $r$** to determine whether to reject the null hypothesis, where
1. Test Statistic $T$: The test statistic $T$ is a numerical value calculated from the sample data that reflects how much the data deviates from what is expected under the null hypothesis.
2. Testing Threshold $r$:  The testing threshold is determined based on the significance level $\alpha$, which represents the probability of rejecting $H_0$ **when it is true**. Hence, this threshold is often derived from the $(1-\alpha$)-quantile of the (null) distribution of the test statistic **under null hypothesis $H_0$**.

Hence, the test power (i.e., **the probability of correctly rejecting the null hypothesis when the alternative hypothesis is true**) is given by

$$
\Pr [T\geq r]\ ,
$$

which represents the probability that the **test statistic $T$ (calculated under alternative hypothesis where two samples are from different distributions)** exceeds the testing threshold $r$ (calculated under the **null hypothesis**).
</content>
</thread_object>

</thread>
<thread>
creation date:
1743001638188

thread_type:
official_comment

<thread_object>
creator: reviewer_txyq

<content>
title:
Statement from Reviewer TXYq (Post-Decision Clarification on March 26, 2025)

comment:
After careful reconsideration and thorough discussions with the authors following the decision, I now confirm that all of my previously raised concerns regarding the proof of Theorem 10 have been fully addressed. My earlier comment reflected a misunderstanding on my part about the role of the test statistic under the alternative hypothesis scenario. This issue has been clarified entirely by the authors, and I no longer have any reservations concerning this work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper investigates the problem of distribution closeness testing (DCT) and proposes a novel kernel-based DCT method called norm-adaptive MMD (NAMMD), which extends the well-known MMD by accounting for distributions with relatively different norms.
Both theoretical and empirical results are provided to demonstrate the effectiveness of NAMMD.

While the authors did an excellent job during the rebuttal phase and successfully convinced the reviewers of the significance of their contribution, a **critical issue** was raised during the (further) discussion phase among reviewers. 
Reviewer TXYq identified a **technical flaw in the proof of Theorem 10**, specifically pointing out that the authors appear to focus on the null distribution rather than  $H_1$  in their proof of test power (please refer to Reviewer TXYq’s updated review for details). 
This flaw is significant, casting doubt on the theoretical validity of the proposed NAMMD. 
From an empirical perspective, its advantages remain evident, as demonstrated by the authors' numerical results.

However, given the importance of the identified flaw, I recommend rejecting the paper.