R-divergence for Estimating Model-oriented Distribution Discrepancy

Summary

A new divergence metric, called R-divergence, is proposed in the paper. This metric states that two distributions are identical if the optimal hypothesis on the mixture distribution has the same expected risk on each individual distribution. If two distributions are the same, then the optimal hypothesis on the mixture distribution is the same as the one for the individual distributions. This means that the expected risk is similar for each individual distribution. However, if the distributions are different, then the optimal hypothesis on the mixture distribution would behave differently for the individual distributions. This would result in different expected risks for the individual distributions. The main difference between the proposed R-divergence and the existing H-divergence is that R-divergence calculates the minimum hypothesis and the empirical risk on different datasets. This prevents R-divergence from the overfitting issue that H-divergence suffers from. The paper also utilizes R-divergence to learn with noisy labels, whereby R-divergence is utilized per batch to estimate the clean and noisy samples, and then the network is retrained with minimizing the cross entropy over the clean batch while maximizing it over the corrupted samples. The paper conducts two-sample tests over different datasets and architecture and achieves superior numbers than H-divergence.

Strengths

1. The paper is very well written and is easy to follow. The difference with H-divergence is well highlighted too in the paper. 2. The paper achieves strong results over the baseline divergence metrics over different datasets and with different model architectures. 3. I find the comparison between ViT and CNN architectures particularly interesting, whereby ViT architectures achieve worse test power than CNN ones, indicating that they are learning shape-biased features which makes it hard to discriminate between CIFAR-10 and corrupted CIFAR-10. 4. Using R-divergence to improve the performance of models under corrupted labels is a nice example of how these divergence metrics could be useful.

Weaknesses

1. The comparison with CIFAR-10 and corrupted CIFAR-10 is conducted with only one type of corruption when H-divergence considers a variety of corruptions. Can the authors do more detailed experimentation with different corruptions as done in H-divergence. 2. Can the authors also try to do some experiments with ImageNet and its corrupted variants to more justify their proposed method. Since the experiment needs to be done with a limited number of samples, this experiments shouldn't be too computationally difficult.

Questions

I have already mentioned the questions in the weakness section.

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

None

Summary

This work proposes R-divergence as a measure of discrepancy between two distribution. The R-divergence is the difference between the empirical risks computed on two datasets using a hypothesis trained on a mixture of both datasets. The authors use the R-divergence and the permutation test to identify if two datasets are from different distributions and evaluate this method on a number of benchmarks.

Strengths

The proposed R-divergence is surprisingly simple to compute: it is the difference in the empirical losses on two datasets. The method uses a trained model to define a discrepancy measure between distributions which could also include classifiers or generative models. The authors show that R-divergence can successfully separate data from different distributions and performs favorably when compared to other methods.

Weaknesses

**Why is R-divergence a good measure of discrepancy?** Methods like the H-divergence [1] are rooted in principled definitions of a *probability divergence* and it satisfies properties like the triangle inequality. On the other hand R-divergence seems to be more of a heuristic and it is unclear why it is a good measure of discrepancy between two probability distributions. The authors argue that it achieves SoTA results on some benchmarks when paired with the permutation test but that does not necessarily qualify it to be a good definition of a divergence. **Problems with the definition**: The definition seems to be reliant on the choice of the loss function and the hypothesis class. If we consider a very rich hypothesis class, we can find a hypothesis with 0 loss; this can only happen if the loss is 0 for both the distributions. Hence, the R-divergence between any two distributions will be 0 as long as we select a very rich hypothesis class. This can be problematic since the discrepancy can change based on the loss function or hypothesis class. I worry that many results in the paper heavily depend on such choices. For example, the result on MNIST makes use of a 2-layer fully-connected network (Line 239) and I wonder if the same results will continue to hold if we consider a deep convolutional network. **Limited insight from theory**: The main theoretical result is that the empirical R-divergence converges to the true R-divergence in the limit of infinite samples. This follows from the uniform convergence of the empirical losses to the true losses . However it is unclear why they converge quickly as claimed in the introduction (Line 73). The theory also offers no insight into why the R-divergence is better than other measures of discrepancy. **Simple failure case of R-divergence**: Consider two distributions $$p_1(x, y) = \frac{1}{2}\left( \delta_{(-1, -1)} + \delta_{(1, 1)} \right) \qquad \text{and} \qquad \frac{1}{2}\left( \delta_{(-100, -1)} + \delta_{(100, 1)} \right),$$ defined on $\mathbb{R} \times$ { $-1, 1$}. The two distributions (defined on point masses) can be perfectly separated by a linear hypothesis at 0. Hence, their R-divergence is 0 if we use a linear hypothesis class, even if the two distributions are clearly different. **Understanding when R-divergence can fail**: The R-divergence requires that the losses evaluated on the two distributions are different which is a heuristic that can only work in certain scenarios. This can occur if there is input or label noise in one of the distributions (like in Table 4, Figure 2). I worry that the authors have over-engineered to a specific set of benchmarks while ignoring many other important scenarios. For example one could consider one distribution to be classes 0,1 from MINST and the other distribution to be classes 2,3. Can R-divergence separate the two distributions using a permutation test? Since all samples achieve a similar loss, I would expect the R-divergence to be close to 0. [1] Zhao, Shengjia, et al. "Comparing distributions by measuring differences that affect decision making." International Conference on Learning Representations. 2021.

Questions

Many of my questions have been included in a previous section but are summarized again below: 1. Why is R-divergence a good measure of discrepancy? 2. Do the results on MNIST hold if we consider a deep convolutional network? 3. Can we separate out two distributions where one contains classes 0,1 and the other contains classes 2,3 from MNIST (or CIFAR10)? 4. Do these results rely on the datasets having different scales for the losses and is this common across many datasets?

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

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

The authors can expand upon some of the limitations of their method. For example, the authors can include a discussion about how R-divergence depends on the choice of the loss function or the hypothesis class.

Summary

This paper proposes R-divergence to measure the distributional discrepancy of two datasets. The general idea is to learn a minimum hypothesis on the mixed data and then define R-divergence as the difference of the empirical risk of the learned hypothesis between two datasets. The proposed divergence leverages the merits of both H-divergence and L-divergence. Sufficient experiments are performed to demonstrate the superior performance. The case study on learning with label noise is also interesting.

Strengths

1. The method is very easy to follow. Authors also provide valid theoretical analysis (although some results rely heavily on previous literature). 2. Sufficient experiments in different learning scenarios (e.g., multiple domains, spurious correlations, and noise labels) are performed. 3. The case study on learning with label noises is interesting. However, a suitable comparison with state-of-the-art methods in this category can enhance the quality of this section.

Weaknesses

1. It seems to me that R-divergence simply combines the merits of L-divergence and the recently proposed H-divergence. The original L-divergence is intractable since it requires evaluation of all hypotheses in the hypothesis space. By contrast, R-divergence just learns a minimum hypothesis on the mixed data. However, the general idea of defining divergence as the difference of risks on the mixed data and individual datasets is investigated in the H-divergence. 2. Since R-divergence is model-oriented. How to select hypothesis space and loss functions in practice? 3. The divergence or distance of distributions is an intrinsic property of two datasets. I can understand that a learning model-based approach provides a new solution. However, the examples in second paragraph of Introduction are hard to convince me why it is more meaningful to measuring divergence by considering a specific model; or why we really need a model-oriented discrepancy measure.

Questions

Please see weaknesses points 2 and 3. Additionally, according to Table 1, it seems R-div is much better than others in case of limited samples. Can you give more analysis on the reason?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

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

3 good

Contribution

2 fair

Limitations

Authors did not discuss potential limitations or potential negative societal impacts. It would be better if authors can discuss How to select hypothesis space and loss functions in practice?

Summary

A new distance for comparing two samples of two distributuions p and q is proposed that is based on learning a model on the mixtre distribution of p and q. More precisely, the distance is the difference between errors of the learned model evaluated on the individual distributions. Theoretical statements on the estimation quality are given together with empirical evaluations.

Strengths

- Simple method. - Empirical results are very good. - I could not detect any errors while checking the proofs.

Weaknesses

- Theoretical upper bound on estimation quality depends on L-divergence between distributions. That is, if $\mathcal{D}_L(p||q)$ is large, the estimate of the porposed distance might have a very low quality even if the sample size goes to infinity. - Citations are sometimes confusing, which makes the main argumentation hard to follow. For example, I cannot find a discussion of an "overfitting problem of H-divergence" in [50], as it is noted in the introduction. I also cannot find the reference [63] in [50], although [63] is given as reference of the H-divergence in the paper under review. - Theoretical notation/assumptions could be extended, e.g.: What is $\mathcal{A}$? Does it need to have specific properties so that Theorem 1 is satisfied? What are the properties of the input/output spaces so that the thoerems hold? How do you exactly specify a learning model $\mathcal{T}$?

Questions

- Do the authors have an idea about the convergence of the empirical estimator towards the true distance for increasing sample size, in the case when the L-distance is large? E.g. is there a lower bound on the left-hand side of Corollary 4.4? - What is the effect of regularization of the trained neural networks (e.g., weight decay) on the porposed distance in the experiments? - Concerning the main motivation of improving overfitting, is there an empirical evaluation comparing the "amount of overfitting" (however this is measured) of H-divergence and L-divergence?

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

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

- What is a possible effect in the test error, when the upper bounds in the theoretical statements are large, as e.g. in the case of large L-divergence?

Thank you for the response!

I thank the authors for their detailed response and appreciate the time and effort. I appreciate that the authors have presented new experiments on MNIST. I still have some questions and concerns and hope that the authors can clarify potential misunderstandings if any. **Q1: The name of R-divergence** Divergences (https://en.wikipedia.org/wiki/Divergence_(statistics)) such as KL-divergence or H-divergence, satisfy the triangle inequality and positivity. Neither of these two properties are satisfied by R-divergence which was my concern in Q1. I understand that I am being pedantic here but it would be helpful to clarify that R-divergence isn't a "divergence" from a more precise mathematical standpoint. edit: The abstract seems to indicate that R-divergence is a new definition for a divergence, but it seems like the main merit of the paper is to combine R-divergence with the permutation test to identify if samples are from the same/different distribution. I believe this clarification would be helpful. **Q3: R-divergence can work in any scenario, as shown in Theorem 4.1, as it can adapt to any hypothesis spaces, loss functions, and target functions.** Could the authors clarify by what they mean by "work"? Theorem 4.1 proves that the empirical estimator converges in the asymptotic limit. But I don't understand why the value of the R-divergence is useful (to distinguish distributions or learn with noisy labels) in all scenarios. **Q2: R-divergence is model-oriented for a specific learning model rather than hypothesis/loss function driven. It indicates that it is reasonable to obtain different results for different hypothesis spaces.** I fully appreciate the point made by the authors and don't think I am misunderstanding this. The R-divergence is expected to change if we consider a different architecture (hypothesis class) or loss functions and this property can be desirable. I would like to clarify if the experiments that evaluate the test power of R-div depend on the choice of architecture (hypothesis space) and the loss? If this is case, can we expect R-divergence to be unable to distinguish different distributions (test power of 0.0) in some scenarios? I don't see this as a drawback of the method but it would be helpful to discuss limitations. **Q2: For both scenarios, R-divergence can quickly converge to a measurement representing the difference between two distributions as the sample size goes to infinity.** Proposition 4.3 doesn't talk about the rate of convergence and it would be incorrect to say that R-divergence converges **quickly**. **Q3: A perfect hypothesis from a rich class could obtain zero empirical risks on both datasets. In this case, this hypothesis for its learning task is not sensitive to the two distributions** I don't follow this argument. We can achieve zero empirical risk on the dataset $\hat p \cup \hat q$ but this does not imply that the hypothesis is not sensitive to $\hat q$. **Q3: The following experiment results show that R-divergence can easily separate samples with different classes from MNIST.** Thanks for running this experiment! I find it very interesting that cross-entropy losses differ between the classes even on MNIST. Different classes seem to have different average losses which makes the permutation test work well in practice. I find the experiments compelling and have increased my score. I'd be be willing to increase it further if the authors could address some of the above questions.

Thank you for your answer

I appreciate the answers of the reviewers. My suggestion remains to accept the paper.

Thank you for the raised score！

Thank you for taking the time to read our rebuttal. If you could kindly elaborate on specific points that you believe require additional attention or revision, we would be more than happy to address these in the revised manuscript.

Thanks for the response

Dear authors, Thanks for your efforts to clarify the concerns raised by the reviewer. Although the reviewer has not responded yet, I'd like to assure you that your response will be incorporated into the reviewers' discussion and my final recommendation. Best wishes, AC