R-divergence for Estimating Model-oriented Distribution Discrepancy
Authors: Zhilin Zhao
Longbing Cao
Venue: NeurIPS 2023 poster (2023)
Keywords: non-IID
Distribution Discrepancy
Data Divergence
Two-sample Test
TL;DR: R-divergence is proposed to estimate the discrepancy between two probability distributions for specific supervised or unsupervised machine learning models.

Abstract: Real-life data are often non-IID due to complex distributions and interactions, and the sensitivity to the distribution of samples can differ among learning models. Accordingly, a key question for any supervised or unsupervised model is whether the probability distributions of two given datasets can be considered identical. To address this question, we introduce R-divergence, designed to assess model-oriented distribution discrepancies. The core insight is that two distributions are likely identical if their optimal hypothesis yields the same expected risk for each distribution. To estimate the distribution discrepancy between two datasets, R-divergence learns a minimum hypothesis on the mixed data and then gauges the empirical risk difference between them. We evaluate the test power across various unsupervised and supervised tasks and find that R-divergence achieves state-of-the-art performance. To demonstrate the practicality of R-divergence, we employ R-divergence to train robust neural networks on samples with noisy labels.

R-divergence for Estimating Model-oriented Distribution Discrepancy
Zhilin Zhao
Longbing Cao
Data Science Lab, School of Computing & DataX Research Centre Macquarie University, Sydney, NSW 2109, Australia Shaozh17@hotmall com, longbing cao@mq. edu. au
Abstract
Real-life data are often non-llD due to complex distributions and interactions, and the sensitivity to the distribution of samples can differ among learning models. Accordingly, key question for any supervised unsupervised model is whether the probability distributions To address this question, introduce R-divergence, designed to assess model- oriented distribution discrepancies. The core insight is that two distributions are likely identical if their optimal hypothesis yields the same expected risk for each distribution. To estimate the distribution discrepancy between two datasets, R- divergence learns minimum hypothesis on the mixed data and then gauges the empirical risk difference between them. We evaluate the test power across various unsupervised and supervised tasks and find that R-divergence achieves state-of- the-art performance. To demonstrate the practicality of R R-divergence, we employ R- R-divergence train robust neural networks on samples with noisy labels.
two given datasets can be considered identical.
Introduction
Most machine learning methods rely on the basic independent and identically distributed (IID) as- sumption [7]. implying that variables are drawn independently from the same distribution. However, real-life data and machine learning models often deviate from this IID assumption due various com- plexities, such as mixture distributions and interactions (9]. For given supervised or unsupervised task (45), learning model derives an optimal hypothesis from a hypothesis space by optimizing the corresponding expected risk [53]. However, this optimal hypothesis may not be valid if the distributions of training and test samples differ [54], resulting distributional vulnerability [63] In fact, an increasing body of research addresses complex non-III scenarios (8) including open-worf sprldworld problems 66) out-of-din diitrii--itiiitt detection 22 63, domain adaptation [28] and learning with noisy
labels [46]. These scenarios raise a crucial yet challenging question: how to assess the discrepancy
between two probability distributions for specific learning model?
Empirically, the discrepancy between two probability distributions can be assessed by the divergence between their respective datasets. However, the actual underlying distributions are often unknown, with only limited number of samples available for observation. Whether the samples from two datasets come from the same distribution is contingent upon the specific learning model being used. This is because different learning models possess unique hypothesis spaces, loss functions, target functions, and optimization processes, which result in varying sensitivities to distribution discrepancies. For instance, in binary classification [26). samples from two datasets might be treated as positive and negative, respectively, indicating that they stem from different distributions. Conversely, model designed to focus invariant features is more likely to treat all samples if they are drawn from the same distribution. For example, in one-class classification (52). all samples are considered positive, even though they may come from different components of mixture distribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In cases where the samples from each dataset originate from multiple distributions, they can be viewed as drawn from a complex mixture distribution. We can then estimate the discrepancy between these two complex mixture distributions. This suggests that, in practice, it is both meaningful and necessary to evaluate the distribution discrepancy for a specific learning model, addressing the issue of model-oriented distribution discrepancy evaluation.
Estimating the discrepancy between two probability distributions has been a foundational and challenging issue. Various metrics for this task have been proposed, including F-divergence [2].. integral probability metrics (IPM) 2 and H-divergence 62]. F-divergence metries, like Kullback- Leibler (KL) divergence [13] and Jensen Shannon divergence 47], assume that two distributions are identical they possess the same likelihood every point. Importantly, F-divergence is not tied to specific learning model, as it directly measures discrepancy by computing the statistical distance between the two distributions. IPM metrics, including the Wasserstein distance [48], maximum mean discrepancy (MMD) and L--divergence [S] They postulate that any function should yield the same expectation under both distributions if they are indeed identical, and vice versa. In this vein, L-divergence explores the hypothesis space for a given model and regards the largest gap in expected risks between the two distributions as their discrepancy. This necessitates evaluating all hypotheses within the hypothesis space, task which can be computationally demanding. Moreover, hypotheses unrelated to the two distributions could result in inaccurate biased evaluations. On the other hand, --divergence [62] contends that two distributions are distinct if the optimal decision loss is greater when computed on their mixed distribution compared to each individual one. It calculates this optimal decision loss in terms of training loss, meaning it trains a minimal hypothesis and evaluates its empirical risk on the identical dataset. A network with limited training data is susceptible to overfitting (50), which can lead to underestimated discrepancies when using H-divergence, even if the two distributions are significantly different.
[1] assess discrepancy based on function outputs.
To effectively gauge the model-oriented discrepancy between two probability distributions, we intro- duce R-divergence. This novel metric is built on the notion that two distributions are identical if the optimal hypothesis for their mixture distribution yields the same expected risk on each individual distribution. In line with this concept, R-divergence evaluates the discrepancy by employing em- pirical estimator tailored to the given datasets and learning model. Initially, a minimum hypothesis is derived from the mixed data of the two datasets approximate the optimal hypothesis. Subsequently, empirical risks are computed by applying this minimum hypothesis to each of the two individual datasets. Finally, the difference in these empirical risks serves the empirical estimator for the discrepancy between the two probability distributions. The framework of R-divergence is illustrated in Figure I
2 Model-oriented Two-sample Test
We measure the discrepancy between two probability distributions p and q for a specific supervised or unsupervised learning method. Let X and y be the spaces of inputs and labels, respectively. Assume we observe two sets of N IID samples from the two distributions, i.e., P = ] ~ p. and q = [-] ~ q, respectively. We assume the mixture distribution u = (p + 4)/2 and its corresponding mixed data ū = -U
For learning model T, assume H is its hypothesis space and is its T.-Lipschitz bounded loss function, i.c., -( < c. For an input x E X. we suppose || < B and a E A is its corresponding target function for the model. For example, a(x) y E ) for supervised classification and a = x E X' for unsupervised input reconstruction. In general, a loss function can be defined as I(h(z) ax)) for any hypothesis h E H and input æ E X'. h(x)) represents the hypothesis output for x. For example, h(z) produces predicted label by a classifier or the reconstructed input by unsupervised input reconstruction. For the mixture distribution u and its corresponding dataset ū, we define the expected risk e,, (h) and empirical risk En (h) for any h E H. 611:
c (h) Ex (hn_)
Σ I(M))) MER
= 2N
Then, we define the optimal hypothesis hG and the minimum hypothesis Te respectively,
hi E arg min en (h),, Jen arg min (h). heR
(2)
hER

---

Data
= p u
Empirical risk
é
Divergence
R-divergence:
Figure I: R-divergence estimates the distribution discrepancy on datasets ğ and q. ha represents the minimum hypothesis learned on the mixed data ū = U. êp and én represent the empirical risks of the minimum hypothesis data and i7. respectively. R-divergence DR estimates the distribution discrepancy by the empirical risk difference between the two datasets.
A learning model of the task aims to learn the minimum hypothesis h on observed data to approximate the optimal hypothesis h². This aim can be converted the model-oriented two-sample test: For datasets P and and their learning task with hypothesis space H. and loss function can we determine whether their probability distributions are identical (e.g.. p = g) for the specific model? This research question is equivalent to: whether the samples of the two datasets can be treated as sampled from the same distribution for the model?
R-divergence for Distribution Discrepancy
To fulfill the model-oriented two-sample test, develop R-divergence estimate the discrepancy between two probability distributions and for model T. R-divergence regards two distributions identical if the optimal hypothesis their mixture distribution has the same expected risk each individual distribution. Accordingly, with the corresponding datasets 5 and q. R-divergence estimates the optimal hypothesis ht, the mixture distribution by learning the minimum hypothesis he on the mixed dataset ū. Then, R-divergence estimates expected risks (p(h)) and (n()) on the two distributions by evaluating the empirical risks (3(Naa) and (g(aa) on their data samples. R-divergence measures the empirical risk difference between (pa) and (hg to estimate the distribution discrepancy.
Accordingly, for supervised unsupervised model with hypothesis space H. and loss function 1, R-divergence evaluates the discrepancy between distributions p and g by,
DR(Pll9) (h))))))) e, (1t) = (1 - e, (hh))
d(s-)) represents the absolute differencee. Intuitively, if = g, then p q and h;, is the optimal hypothesis for both and 9. Thus, the expected risks on the two distributions are the same, which leads to a zero discrepancy. In contrast, if * q, h" is the optimal hypothesis for u, and it performs and q. Then, the expected risk difference can evaluate the discrepancy between the two distributions for the specific model. Different from F-divergence without considering specific learning models, R-divergence involves the property of the specific model in evaluating the model- oriented distribution discrepancy conditional on the optimal hypothesis. Specifically, R-divergence infers the discrepancy by comparing the distance hetween the learning results on two distributions. The learning result sensitive to the learning model, i.c., its hypothesis space and loss function.
differently
Further, DR (pll4) can be estimated on datasets s and q. R-divergence estimates the discrepancy by searching minimum hypothesis h. the mixed dataset à pu q, and calculates the empirical risks (hw) and (g.h on each individual dataset. Then, DR (p(lg) can be estimated by the empirical risk difference (p(lll)):
( d d(sg(ha). (ha 2g(
(4)
DR (Pllg) can be treated empirical estimator for the distribution discrepancy (x(lg)).

---

Because hi is the minimum hypothesis on the mixed dataset ū, ha will overfit neither p nor q. Specifically, both (h.h and (h.) will not tend towards zero when ğ and are different. This property ensures that the empirical estimator will not equal zero for different given datasets. Further, as â consists of P and q. both (p(hu) and (g(b.) will not tend towards extremely large values, which ensures a stable empirical estimator. general, due to the property that the minimum hypothesis learned on the mixed data is applied to evaluate the empirical risk on each individual dataset, R- divergence can address the overfitting issue in H-divergence [62] The procedure of estimating the model-oriented discrepancy between two probability distributions is summarized in Algorithm (see Appendix[B.]]
R-divergence diverges substantially from L-divergence [31 and H-divergence 662 While R-
divergences and L-divergences apply different hypotheses and scenarios, R-divergences and H-divergences differ in their assumptions on discrepancy evaluation and risk calculation. Notably, R- R-divergence enhances performance by mitigating the overfitting issues seen with H-divergence. H-divergence assumes that two distributions are different if the optimal decision loss is higher on their mixture than on individual distributions. As a result, H-divergence calculates low empirical risks for different datasets, leading to underestimated discrepancies. In contrast, R-divergence tackles this by assuming that two distributions are likely identical if the optimal hypothesis yields the same expected risk on each. Thus, R-divergence focuses on a minimum hypothesis based on mixed data and assesses its empirical risks on the two individual datasets. treats the empirical risk gap as the discrepancy, ensuring both small and large gaps for similar and different datasets, respectively. Technically, R-divergence looks at a minimum hypothesis using mixed data, while L-divergencee explores the entire hypothesis space. Consequently, R-divergence is model-oriented, accounting for their hypothesis space, loss function, target function, and optimization process.
Accordingly, there is no need to select hypothesis spaces and loss functions for R-divergence, as it estimates the discrepancy tailored to a specific learning task. Hence, is reasonable anticipate different results for varying learning tasks. Whether samples from two datasets are drawn from the same distribution dependent on the particular learning model in use, and different models exhibit varying sensitivities to distribution discrepancies. Therefore, the distributions of two given datasets may be deemed identical for some models, yet significantly different for others.
Theoretical Analysis
Here, we present the convergence results of the proposed R-divergence method, i.e., the bound on the difference between the empirical estimator ( and the discrepancy DR(Pllz). We define the L-divergence (35] (pllg) as
(rl()) (lp((ep(h) (h))).
(5)
MEH
Further, we define the Rademacher complexity Ry 11
as
R
17
2N R
(=1)aN
sup Σ
(all(())
(6)
NEW DER
According to the generalization bounds in terms of L-divergence and Rademacher complexity, can bound the difference between DR(Plo ② and DD (R(l)lg).
Theorem 4.1. For any E X, h E H and a E A, assume we have [1(h(z), a(x)) S Then, with probability at least 6, we can derive the following general bound,
In(8/0)
(De(plla) DR(P (DL(p)) 2R) 22 + 12cV
N
Corollary 4.2. Following the conditions of Theorem 4.1 the upper bound of Var [u(ppl))
34c VN + 2 (2Dr + 2R)
2R

---

The detailed proof is given in Section Note that both the convergence and variance of DR (pll depend on the L-divergence, Rademacher complexity, and the number of samples from each dataset. Recall that L-divergence is based on the whole hypothesis space, but R-divergence is based on an optimal hypothesis. The above results reveal the relations between these two measures: a smaller I--divergence between two probability distributions leads to a tighter bound on R-divergence. As the Rademacher complexity measures the hypothesis complexity, we specifically consider the hypothesis complexity of deep neural networks (DNNs). According to Talagrand' contraction lemma [44) and the sample complexity of DNNs 18 591, we can obtain the following bound for DNNs.
Proposition 4.3. Based on the conditions of Theorem 4.1 we assume H is the class of real-valued networks of depth D over the domain X. Let the Frobenius norm of the weight matrices be at most Mı....y MD. the activation function be 1-Lipschitz, positive-hrn honiiivveoooogneouuss and applied element-wise (such the ReLU). Then, with probability at least 1 8, we have,
[Dx(Plla) (P(I) S (Pl()) + ALB(V2Dl22 + 1) Mr + 120V
ln(6/)) N
Accordingly, we can obtain a tighter bound if the L-divergence D2 (pll)) meets certain condition.
Corollary 4.4. Following the conditions of Proposition
4.3 with probability least 1 8, we have
the following conditional bounds if (p(l)) I e (hū,) En (Fa)
+ + 1)II MS
In(16/8)
(Dx(pla) (pl S
+ 220
N
Then, the empirical estimator D& ( converge uniformly to the discrepancy DR (pll4) as the number of samples N increases. Then, based on the result of Proposition 4.3 we can obtain general upper bound of (plg).
Corollary 4.5. Following the conditions of Proposition 4.3 as N + oo, we have,
DR( (Pl())) DR(Plla).
and R-divergence Dr (x(plg) The empirical estimator will converge to the sum of L-divergence Dr
(pll4) (p
as the sample size grows, as indicated in Corollary 4.5 As highlighted by Theorem 4.1 a large L-divergence can influence the convergence of the empirical estimator. However, large L-divergence also useful for determining whether samples from two datasets are drawn from different distri- butions, as it signals significant differences between the two. Therefore, both L-divergence and R d-vvergeence quantify the discrepancy between two given probability distributions within learning model. Specifically, L-divergence measures this discrepancy across the entire hypothesis space, while R-divergence does so in terms of the optimal hypothesis of the mixture distribution. Hence, large I I-divergence implies that the empirical estimator captures significant difference between the two distributions. Conversely, a small L-divergence suggests that the empirical estimator will quickly converge to a minor discrepancy as the sample size increases, evidenced in Corollary 4.4 Thus, the empirical estimator also reflects a minimal distribution discrepancy when samples from both datasets are drawn from the same distribution.
Experiments
We evaluate the discrepancy between two probability distributions w.r.t. R-divergence (R-Div for both unsupervised and supervised learning models. Furthermore, we illustrate how R-Div is applied to learn robust DNNs from data corrupted by noisy labels. We compare R-Div with seven state-of-the-art methods that estimate the discrepancy between two probability distributions. The details of the comparison methods are presented Appendix C
'The source code is publicly available httpps//ggituub.cm/lllllleee-
5

---

5.1 Evaluation Metries
The discrepancy between two probability distributions for a learning model is estimated on their given datasets IID drawn from the distributions, respectively. We decide whether two sets of samples are drawn from the same distribution. A model estimates the discrepancy on their corresponding datasets {1r)] p and 7
{ ~ q. DR( serves as an empirical estimator for the discrepancy (R(pl)) to decide whether p # q if its output value exceeds a predefined threshold.
For an algorithm that decides if p * q. the Type I ermor [14 occurs when it incorrectly decides & q- and the corresponding probability of Type error is named the significant level. In contrast, the Type II error [14] occurs when it incorrectly decides p q. and the corresponding probability of not making this error is called the test power [34. In the experiments, the samples of two given datasets P and 9 are drawn from different distributions, i.e., the ground truth is p + q. Both the significant level and the test power are sensitive to the two probability distributions. Accordingly, to measure the performance of learning algorithm,
calculate its test power when a certain significant level E [0, 1] can be guaranteed. A higher test power indicates better performance when p + q.
The significant level can be guaranteed with permutation test 17 For the given datasets f and T. the permutation test uniformly randomly swaps samples between f and 7 to generate Z dataset pairs ((F ((","")) 1z 1- For P and T. R-Div outputs the empirical estimator (x( Note that if p= 9, swapping samples between p and q cannot change the distribution, which indicates that the permutation test can guarantee a certain significant level. If the samples of p and @ are drawn from different distributions, the test power is if the algorithm can output p + q Otherwise, the test power
O. Specifically, to guarantee the a significant level, the algorithm output p + q if DR (pli) is in the top a-quantile among g = {Dx (8 (p= | We perform the test for K times using different mandomly-selecteo dataset pairs (p. q) and average the output values the test power of the algorithm. If not specified, we set a = 0.05, Z = 100 and K = 100. The procedure of calculating the average test power of R-Div is summarized in Algorithm (see Appendix B.2.
5.2 Unsupervised Learning Tasks
Benchmark Datasets: Following the experimental setups as 41 and 62). we adopt four benchmark datasets, namely Blob, HDGM, HIGGS, and MNIST. We consider learning unsupervised models on these datasets, and the considered hypothesis spaces are for generative models. Specifically, MNIST adopts the variational autoencoders (VAE) (33, while the other low dimensional data adopt kernel density estimation (KDE) (27). For fair comparisons, we follow the same setup as [62] for all methods. Because all the compared methods have hyper-paramese
we evenly split each dataset into a training set and a validation set to tune hyper-parameters and compute the final test power, respectively.
The average test powers for a certain significant level on HDGM 41, Blob (41, MNIST 38 and
HIGGS [ are presented in Figure Figure Table g (see Appendix D.Ip and Table 2 respectively.
Overall, our proposed R-Div achieves the best test power on all datasets. On HDGM, R-Div obtains the best performance for different dimensions and achieves the perfect test power with fewer samples. Specifically, the test power of R-Div decreases gracefully as the dimension increases on HDGM. On Blob with different significant levels. R-Div achieves the same test power as the second- best method with a lower variance. On MNIST, both H-Div and R-Div achieve the perfect test power on all the sample sizes. On HIGGS, R-Div achieves the perfect test power even the dataset with the smallest scale.
The discrepancy as measured by R-Div is distinct for two different distributions, even with a small sample size. This advantage stems from mitigating overfitting of H-Div by learning the minimum hypothesis and evaluating its empirical risks across varying datasets. R-Div learns minimum hypothesis based on the mixed data and yields consistent empirical risks for both datasets when samples are sourced from the same distribution. Conversely, if samples from the two datasets come from different distributions, the empirical risks differ. This is because the training dataset for the minimum hypothesis does not precisely match either of the individual datasets.
To better demonstrate the advantages of R-Div, we measure the amount of overfitting by calculating empirical risks on and q. The results presented in Table Inniicaee that R-Div achieves a notably clearer discrepancy, attributable to the significant differences in empirical risks on p and q. This is because R-Diy mitigates overfitting by optimizing minimum hypothesis on mixed dataset

---

Table 1: The empirical risks on p and q for L-Div, H-Div, and R-Div on MNIST when N = 200.
Methods
Hypothesis
(p(hp)
(g(hgg)
(<p(1p) - cg(hx)]
L-Div
hp = hg E H
713.0658
713.1922
0.1264
hp E arg min (p(h)
H-Div
111.7207
118,9020
7.1813
hy mrgmin (h)
R-Div
hp - hg arg mingew 6 Extt (h)
144.0869
99.6166
44.4703
Table 2: The average test power + standard error the significant level a 0.05 on HIGGS. N represents the number of samples in each given dataset, and boldface values represent the relatively better discrepancy estimation.
1000
2000
3000
5000
8000
10000
Avg.
ME
0.120::0.007
0. 0.16:::0011
0:197::0:012
0.410:t:0041
0.691=:0.691
0.786
0.395
SCF
0.095::0.022
0.130::0.026
0.142:::0025
0.261+0.044
0.467=00.038
0.603:t0.066
0.283
C2STS-S
0.082:1:0005
0.183:1:00332
0.257:1:0.04
0.592:10.037
0.892:1:.029
0.974:10.070
0.497
C2ST.L
0.097.1..014
0.232.10.017
0.399110.058
0.447.10.045
0.878110.020
0.985110.050
MMD-0
0.132::0.050
0.291=:00012
0.376:::00022
0.659400.018
0.923-:00013
100001:0.000
0.564
MMD-D
0.113:+0.013
0.304::0.035
0.403=000000
0.699
0.952:00.024
1.00:::0.000
0.579
H-Div
0.240::0.020
0.380:10.040
0.685::0.015
0.930::0.010
1000:1-0.000
L000:1:0.000
0.847
R-Div
1.000::0.000
1.000::0.000
1.000::0.000
1.000::00000
1.000::0.000
1.000::0.000
1,000
and assessing its empirical risks across diverse datasets. Consequently, R-Div can yield more pronounced discrepancy for two markedly different distributions.
5.3 Supervised Learning Tasks
Multi-domain Datasets: We adopt the PACS dataset 440 consisting of samples from four different domains, including photo (P), art painting (A), cartoon (C), and sketch (S). Following [40] and [57]. we use AlexNet (37) as the backbone. Accordingly, samples from different domains can be treated as samples from different distributions. We consider the combinations of two domains and estimate their discrepancies. The results in Figure [5] (see Appendix (D2) represent that the test power of R-Div significantly improves as the number of samples increases. In addition, R-Div obtains the best performance on different data scales. The results Table 3 show that R-Div achieves the superior test power across all the combinations of two domains. This is because the compared H-Div method suffers from the overfitting issue because it searches for a minimum hypothesis and evaluates its empirical risk the same dataset. This causes empirical risks different datasets to be minimal, even if they are significantly different. R-Div improves the performance of estimating the discrepancy by addressing this overfitting issue. Specifically, given two datasets, R-Div searches minimum hypothesis on their mixed data and evaluates its empirical risks on each individual dataset. R-Div obtains stable empirical risks because the datasets used to search and evaluate the minimum hypothesis are not the same and partially overlap.
Spurious Correlations Datasets: We evaluate the probability distribution discrepancy between MNIST and Colored- MNIST (with spurious correlation) 3 The adopted model for the two datasets is fully-connected and has two hidden layers of 128 ReL.U units, and the parameters are learned using Adam 32.. The results in Table 4 reveal that the proposed R-Div achieves the best performance, which indicates that R-Div hypothesis on the mixed datasets.
explore the spurious correlation features by learning minimum
We assess the probability distribution discrepancy between given dataset and its corrupted variants. Adhering the construction methods outlined by Sun et al. al.(55) and the framework of H-Div we conduct experiments using H-Div and R-Div. We examine partial corruption types across four corruption levels on both CIFARIO (36) and ImageNet [15), employing ResNet18 8 [22 the backbone. Assessing discrepancies in datasets with subtle corruptions is particularly challenging due to the minor variations in their corresponding probability distributions.
Corrupted Datasets:
Therefore, we employ large sample sizes, N 5000 for CIFAR10 and N 1000 for ImageNet,
7

---

Table 3: The average test power + standard error at the significant level a = 0.05 on different domain combinations PACS. A, C and S represent photo, art painting, cartoon, and sketch domains, respectively. The distribution discrepancies for six combinations of two domains are estimated. For example,
C represents the combination of art painting and cartoon domains. Boldface values represent the relatively better discrepancy estimation.
Datasets
A+C
A+P
A+S
C+P
C+S
P+S
Ave.
H-Div
0.846:10.118
0.668--0.064
0.964-00.066
0.448 0.527 0.097
0.482
0.876:#0,090
0.714
R-Div
1.000 0.000
1.000 0.000
1.000 0.000
0.589 0.160
0,980 0.040
0.849
Table 4: The average test power MNIST and Colored-MNIST at the significant level 0.05.
ME
SCF
C2STS-S
C2ST-L
MMD-O
MMD-D
H-Div
R-Div
0.383
0.204
0.189
0.217
0.311
0.631
0,951
1,000
and observe that methods yield test power of 0 when the corruption level is mild. Consistently across different corruption types, R-Div demonstrates superior performance at higher corruption levels and outperforms H-Div across all types and levels of corruption. Moreover, our results on ImageNet substantiate that the proposed R-Div effectively estimates distribution discrepancies in lurge-resolution datasets.
Advanced Network Architectures: For supervised learning tasks, R-Div selects the network ar- chitecture for the specific model. To verify the effect of R-div, perform experiments wide range of architectures. We compare R-diy with H-div because both of them are model-oriented and the other comparison methods have specific network architectures. Specifically, classification task on CIFAR10 10 and Corrupted-CIFAR 10 and adopt four advanced network architec- tures, including ResNet18 (22). SENet (24), ConvNeXt (42), ViT [16.. The results are summarized in T For large-scale datasets (N = 10000), both H-Div and R-Div achieve perfect test power with different network architectures because more samples are applied to estimate the probability distribution discrepancy precisely. However, R-Div has the better test power for more challenging scenarios where the datasets are small (N 1000, 5000). This may be because R-Div addresses the overfitting issue of H-Div by optimizing the minimum hypothesis and evaluating its empirical risk on different datasets. Furthermore, for different network architectures, CNN-based networks achieve better performance than the transformer-bant Kim [49] and Li et al. 39), this may be because multi-head attentions (MHA) are low-pass filters with shape bias, while convolutions are high-pass filters with texture bias. As result, ViT more likely focuses on the invariant shapes between CIFARIO and the corrupted-CITARIO to make the two datasets less discriminative.
consider the
models (VIT). According to the analysis of Park and
5.4 Case Study: Learning with Noisy Labels
R-Div is a useful tool to quantify the discrepancy between two probability distributions. We demon- strate how it can learn robust networks on data with noisy labels by distinguishing samples with noisy labels from clean samples in a batch. Furthermore, we explain how the discrepancy between clean and noisy samples affects the classification generalization ability (58).
5.4.1 Setup
We adopt the benchmark dataset CIFARIO 36). As CIFARIO contains clean samples, following the setup (51), we corrupt its training samples manually, i.e., flipping partial clean labels to noisy labels. Specifically, we consider symmetry flipping (56) and pair flipping [1] For corrupting label, symmetry flipping transfers it to another random label, and pair flipping transfers it to specific label. Following the setup (29], we adopt 0.2 noise rate, i.e., the labels of 20% samples will be flipped. The classification accuracy is evaluated clean test samples.
apply R-Div to train a robust DNN on a corrupted dataset. The training strategy separates clean and noisy samples by maximizing the discrepancy estimated by R-Div. The ground truth labels

---

Table 5: The average test power on a dataset and its corrupted variants at the significant level 0.05.
0.5%
1%
2%
5%
Dataset
Corruption
H-Div/ R-Div
Gauss
0,000 / 0.000
0.195 / 0.219
0.368 / 0.411
0.710 0.748
0.748
CIFARIO (N = 1000)
Snow
0.000 / 0.000
0.096
0.189
0.251 0.277
0.366 0.416
Speckle
0.000 / 0.000
0.275 / 0.340
0.458 / 0.513
0.685 / 0.771
Impulse
0.000 / 0.000
0.127 0.185
0.277 0.326
0.629 0.652
Gauss
0.000 / 0.000
0.680 / 0.722
1.000 1.000
1.000 / 1.000
ImageNet (N = 5000)
Snow
0.000 / 0.000
0.774 / 0,816
0.785
0.836
1.000 1.000
Speckle
0.000 / 0.000
0.586 / 0.624
0.762 0.804
1.000 1.000
Impulse
0.000 / 0.000
0.339 / 0.485
0.545 0.635
1.000 1.000
Table 6: The average test power on advanced network architectures.
ResNet18
SENet
ConvNeXt
ViT
N
H-Div R-Div
1000
0.116 0.252
0.201 / 0.296
0.186 / 0.322
0.119 0.211
5000
0.622 / 0.748
0.478 / 0.790
0.778 / 0.844
0.492 / 0.651
10000
1.000 / 1.000
1.000 / 1.000
1.000 1.000
1.000 1.000
for noisy samples are unreliable. Therefore, these labels can be treated as complementary labels representing the classes that the samples do not belong to. Accordingly, the training strategy optimizes the losses of ground truth and complementary labels for clean and noisy samples, respectively.
We assume that clean and noisy samples satisfy different distributions, i.e., clean and noisy distri- butions. Specifically, we apply R-Div to detect clean and noisy samples from a batch. Accordingly, separate the batch samples B into predicted clean samples B, and predicted noisy samples B,, by maximizing R-Div. The batch and the whole dataset contain IID samples from an unknown mixture distribution about clean and noisy distributions. Both the minimum hypotheses on the batch and the whole dataset can be treated to approximate the optimal hypothesis of the mixture distribution. To prevent learning minimum hypothesis for each given batch, we pretrain network on the whole corrupted dataset rather than a batch and apply this pretrained network (minimum hypothesis) to separate clean and noisy samples in a batch.
Recall that R-Div calculates the empirical risk difference between two datasets under the same minimum hypothesis of their mixed dataset. Hence, maximize the discrepancy of R-Div, we calculate the empirical risk of each sample in the batch by the pretrained network, sort the batch samples according the empirical risks, and treat the samples with low and high empirical risks as predicted clean and noisy samples, respectively. Specifically, we separate noisy and clean samples according the estimated noise rate 7 E 1]. For clean samples with trusted ground truth labels, we optimize a network by minimizing the traditional cross-entropy loss. In contrast, the labels for noisy samples are untrusted. However, their noisy labels indicate the classes they do not belong to. Accordingly, we can treat their untrusted ground truth labels as complementary labels and optimize network by minimizing the negative traditional cross-entropy loss on noisy samples. Thus, we retrain a robust network by optimizing the objective function min CB, (h) - CB, (h) for each batch, where the loss function / the traditional cross-entropy loss. this work, we adopt ResNer18 [22 as the backbone. In the pretraining and retraining processes, the learning rate [60] starts at 0.1 and is divided by 10 after 100 and 1.50 epochs. The batch size is 128, and the number of epochs is 200. The haper-parameter varies from 0.1 to 0.7 with a 0.1 step size.

---

(Symmetric)
C2F (Symmetee))
35 1a0
CIFAR110 (Symmattee)
70
Rersioed (50b)
Sacal
0.1
0.2
0.5
0.4
0.5
0.8
0.7
0.1
0.2
0.3
0..6
1.5
0.8
0.7
0.1
0.
0.3
0.4
95
0.7
(a) Accuracy
(b) Detection
(c) Discrepancy
Figure 2: Results on CIFARIO with symmetry flipping. All values are averaged over five trials. Left: Classification accuracy of pretrained and retrained networks. Middle: Precision and recall rates of detecting clean and noisy samples. Right: Discrepancy between predicted clean and noisy samples.
5.4.2 Experimental Results
We evaluate the classification accuracy on clean test test samples, the precision and recall rates of detecting clean and noisy samples, and the discrepancy between predicted clean and noisy samples. The results are reported in FigureZJand and Figure Appendix D.3). Recall that the noise rate is 0.2. Figure ((a) and Figure ((a) show that the network retrained with R-Div improves the classification performance over the pretrained network when the estimated noise rate y E [0.2, 0.5]. The retrained network achieves the best performance when the estimated noise rate is nearly twice as much the real noise rate. To the best of our knowledge, how to best estimate the noise rate remains an open problem and severely limits the practical application of the existing algorithms. However, requires an approximate estimation which can be twice as much as the real noise rate.
method merely
Further, Figure 2(b) and Figure 6(b) show that there is point of intersection between the precision and recall eurves at 7 = 0.5. The aforementioned results indicate that 7 S 0.5 can lead to improved performance. Accordingly, we know that the detection precision is more essential than its recall rate. Specifically, larger estimated noise rate (7 2 0.5) indicates that more clean samples are incorrectly recognized as noisy samples. In contrast, extremely lower estimated noise rate which is lower than the real one indicates that more noisy samples are incorrectly recognized as clean samples. Both situations mislead the network in learning to classify clean samples.
In addition, Figure 2 and Figure/o(c)ssooo show that larger y leads smaller discrepancy. Because the majority of training samples are clean, most of the clean samples have small test losses. A larger y causes more clean samples to be incorrectly recognized as noisy samples, which decreases the test loss of the set of predicted noisy samples. Thus, the empirical estimator will decrease. Based on the results reported Figure and Figure(o(a) the largest discrepancy cannot lead to improved classification performance because most of the noisy samples are incorrectly recognized as clean samples. In addition, we observe that the retrained network obtains improved classification performance when the estimated discrepancy approximates the mean value 1.5 10- which can be used as a standard to select an estimated noise rate y for retraining robust network.
6 Conclusions
We tackle the crucial question of whether two probability distributions are identically distributed for a specific learning model using a novel and effective metric, R-divergence. Unlike existing divergence measures, R-divergence identifies a minimum hypothesis from a dataset that combines the two given datasets, and then uses this to compute the empirical risk difference between the individual datasets. Theoretical analysis confirms that R-divergence, serving as an empirical estimator, uniformly converges and is bounded by the discrepancies between the two distributions, Empirical evaluations reveal that R-divergence outperforms existing methods across both supervised and unsupervised learning paradigms. Its efficacy in handling learning with noisy labels further underscores its utility in training robust networks. the samples from the two datasets are deemed identically distributed, subsequent question be investigated is whether these samples are also dependent.
10

---

Acknowledgments and Disclosure of Funding
This work was supported part by the Australian Research Council Discovery under Grant D- P190101079 and in part by the Future Fellowship under Grant FT190100734.
References
[1] Claire Adam-Bool nonn-Bourdarios, Glen Cowan, Cécile Germain, Isabelle Guyon, Balázs Kégl, and David Rousseau. How machine learning won the higgs boson challenge. In ESANN, pages 1 1-6, 2016.
[2] Rohit Agrawal and Thibaut Horel. Optimal bounds between f-divergences and integral proba- bility metries. J. Mach. Learn. Res., 22:1-128, 2021.
[3] Martín Arjovsky, Léon Bottou, Ishaan Guirajani, and David Lopez-Paz. Invariant risk mini- mization. CoRR, pages 1-31, 2019.
[4] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, 2002.
[5] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Mach. Learn., 79(1- 2):151-175, 2010.
[6] Abhijit Bendale and Terrance E. Boult. Towards open set deep networks. In CVPR, pages 1563-1572, 2016.
[7] Christopher M Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning. volume 4. Springer, 2006.
[8] Longbing Cao. Beyond i.i.d.: Non-iid thinking, informatics, and learning. IEEE Intell. Syst., 37,4):5-17, 2022.
[9] Longbing Cao. Non-iid learning. IEEE Intell. Syst., 37(4):3-4, 2022.
[10] Xiuyuan Cheng and Alexander Cloninger. Classification logit two-sample testing by neural networks for differentiating near manifold densities. IEEE Trans. Inf. Theory, 68666)66616666. 2022.
[11] Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. In NeurlPS, pages 1981-1989, 2015.
[12] Imre Csiszár,
Eine informationstheorttishhe ungleichung und ihre anwendung auf beweis der ergodizitaet von markoffschen ketten. Magyer Tud. Akad. Mat. Kutato Int. Koezl., 1085-108. 1964.
[13] Imre Csiszár. I-divergence geometry of probability distributions and minimization problems. The annals of probability, pages 146-158, 1975.
[14] Frederik Michel Dekking, Corellis Kraaikamp, Hendrik Paul Lopuhaä, and Ludolf Erwin Meester. Modern Introduction Probability and Statisties: Understanding why and how, volume 488. Springer, 2005.
[15] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. CVPR, pages 248-24 288-255, 2009.
[16] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, pages 1-22, 2021.
[17] Michael D Ernst. Permutation methods: a basis for exact inference. Statistical Science, 19(4):676-685, 2004.
[18] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity. In COLT, volume 75, pages 297-299, 2018
[19] Mehmet Gönen and Ethem Alpaydin. Multiple kernel learning algorithms. J. Mach. Learn. Res., 12:2211 1-2268, 1.

---

[20] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. J. Mach. Learn. Res., 13:723-773, 2012.
[21] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W. Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In NeurlPS, pages 8536-8546, 2018.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
[23] Dan Hendrycks and Kevin Gimpel. baseline for detecting misclassified and out-of-distribution examples in neural networks. In ICLR, pages 1-12, 2017.
[24] Jie Hu, Li Shen, and Gang Sun. Squeeze-and-excineg exciitatin networks. In CVPR, pages 7132-7141, 2018.
[25] Arun Shankar Iyer, J. Saketha Nath, and Sunita Sarawagi. Maximum mean discrepancy for class ratio estimation: Convergence bounds and kernel selection. In ICMI,, volume 32, pages 530-538, 2014.
[26] Hamid Jalalzai, Stéphan Clémençon, and Anne Sabourin. On binary classification in extreme regions. In NeurIPS, pages 3096-3104, 2018.
[27] Heinrich Jiang. Uniform convergence rates for kernel density estimation. In ICML, volume 70, pages 1694-1703, 2017.
[28] Junguang Jiang, Yifei Ji, Ximei Wang, Yufeng Liu, Jianmin Wang, and Mingsheng Long. Regressive domain adaptation for unsupervised keypoint detection. In CVPR, pages 6780-6789, 2021.
[29] Lu Jiang, Zhengyuan Zhou, Thomas Leung, Li-Jia Li, and Li Fei-Fei. Mentornet: Learning data- driven curriculum for very deep neural networks corrupted labels. ICML, pages -309-2318. 2018.
[30] Wittawat Jitkrittum, Zoltán Szabó, Kacper Chwialkowski, and Arthur Gretton. Interpretable distribution features with maximum testing power. In NeurIPS, pages 181-189, 2016.
[31] Daniel Kifer, Shai Ben-Davie and Johannes Gehrke. Detecting change in data streams. In VLDB, pages 180-191, 2004.
[32] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, pages 1-13, 2015.
[33] Diederik Kingma and Max Welling. Auto-encoding variational bayes. In ICLR, pages 1-14, 2014.
[34] Matthias Kirchler, Shahryar Khorasani, Marius Kloft, and Christoph Lippert. Two-sample testing using deep learning. In AISTATS, pages 1387-1398, 2020.
[35] Nikola Konstantinov and Christoph Lampert. Robust learning from untrusted sources. In ICMI., pages 3488-3498, 2019.
[36] Alex Krizhevsky. Learning multiple layers features from tiny images. Technical report, 2009.
[37] Alex Krizhevsky. One weird trick for parallelizing convolutional neural networks. In CoRR. pages 1-7, 2014.
[38] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In Proc. IEEE, volume 86, pages 2278-2324, 1998.
[39] Bo Li, Jingkang Yang. Jiawei Ren, Yezhen Wang, and Ziwei Liu. Sparse fusion mixture-of- experts are domain generalizable learners. In /CLR, pages 1-44, 2023.
[40] Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy M. Hospedales. Deeper, broader and artier domain generalization. In ICCV, pages 5543-5551,
[41] Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J. Sutherland. Learning deep kernels for nor-parametric two-sample tests. In ICML, pages 6316-6326, 2020.
[42] Zhuang Liu, Hanzi Mao, Chao-Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In CVPR, pages 1996611976, 2022.
[43] David Lopez-Paa and Maxime Oquab. Revisiting classifier two-sample tests. In ICLR, pages 1-15, 2017.
12

---

[44] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning. MIT Press, 2018.
[45]
Kevin P. Murphy. Machine learning probabilistic perspective. MIT Press, 2012.
[46]
Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learning with noisy labels. In NeurlPS, pages 1196-1204, 2013.
[47] Frank Nielsen. On the jensen-shannon symmetrization of distances relying on abstract means. Entropy, 21 (5:45,8, 2019.
[48] Felix Otto and Michael Westdickenberg. Eulerian calculus for the contraction in the wasserstein distance. SIAM J. Math. Anal., 1227-12227- 2005.
[49] Namuk Park and Songkuk Kim. How do vision transformers work? In ICLR, pages 1-26, 2022.
[50] Gabriel Pereyra, George Tucker, Jan Chorowski, Lukasz Kaiser, and Geoffrey E. Hinton. Regularizing neural networks by penalizing confident output distributions. In ICLR, pages 1-11, 2017.
[51] Scott E. Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich. Training deep neuralnetworks on noisy labels with bootstrapping. In ICLR, 2015.
[52] Lukas Ruff, Nico Gömitzz, Lucas Deecke, Shoaib Ahmed Siddiqui, Robert A. Vandermeulen, Alexander Binder, Emmanuel Müller, and Marius Kloft. Deep one-class classification. In ICML, pages 4390-4399, 2018.
[53] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning From Theory to Algorithms. Cambridge University Press, 2014.
[54] Masashi Sugiyama, Shinichi Nakajima, Hisashi Kashima, Paul von Bünau, and Motoaki Kawanabe. Direct importance estimation with model selection and its application covariate shift adaptation. In NeurIPS, pages 1433-1440, 2007.
[55] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei A. Efros, and Moritz Hardt. Test-time training with self-supervision for generalization under distribution shifts. In ICMI., pages 9229-9248, 2020.
[56) Brendan van Rooyen, Aditya Krishna Menon, and Robert C. Williamson. Learning with symmetric label noise: The importance of being unhinged. In NeurlPS, pages 10-18, 2015.
[57] Haohan Wang, songwei Ge, Zachary C. Lipton, and Eric P. Xing. Learning robust global representationsbyy penalizing local predictive power. In NeurIPS, 2019.
[58] Jiaheng Wei, Hangyu Liu, Tongliang Liu, Gang Niu, Masashi Sugiyama, and Yang Liu. To smooth or not? when label smoothing meets noisy labels. In ICMI., pages 23589-23614, 2022.
[59] Xiaobo Xia, Tongliang Liu, Nannan Wang, Bo Han, Chen Gong, Gang Niu, and Masashi Sugiyama. Are anchor points really indispensable in label-noise learning? NeurlPS, pages 6835,6846, 2019.
[60] Hongyi Zhang. Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In ICLR, pages 1-13, 2018.
[61] Lijun Zhang, Tianbao Yang, and Rong Jin. Empirical risk minimization for stochastic convex optimization: $o(1/n)S-and So(1/n"2)S-typp of risk bounds. In COLT, volume 65, pages 1954-1979, 2017.
[62] Shengjia Zhao, Abhishek Sinha, Yutong Hc, Aidan Perreault, Jiaming Song, and Stefano Ermon. Comparing distributions by measuring differences that affect decision making. In ICLR, pages 1-20, 2022.
[63] Zhilin Zhao, Longbing Cao, and Kun- Yu Lin. Revealing the distributional vulnerability of discriminators by implicit generators. IEEE Trans. Pattern Anal. Mach. Intell., 45(7))8888-899) 2023.
13

---

A Proofs
Section A.1 presents the lemmas used to prove the main results. Section A.2 presents the main results and their detailed proofs.
A.1 Preliminaries
Lemma A.I (533) Theorem 26.5). With probability of at least 1 - for all E H,
In(4/8)
(h) - Ea((h) < (R) + 4eV
N
Lemma A.2 ([53). Theorem 26.5). With probability of at least 1 - for all E H.
In(8/6)
eu (h.w - ex(()) 2R (7) + /
N
Lemma A.3 (44), Talagrand's contraction lemma). For any L-Lipschitz loss function I(:,), we obtain,
R(I o H 1) S LR(H
where Ryy (ū)
1 o SuPPEE EZeaoHh(zz)
2N
Lemma A.4 (118), Theorem 1). Let H be the class of real-valued networks of depth D over the
domain X. Assume the Frobenius norm of the weight matrices most M1.-..; Ma- Let the activation function be I-Lipschitz, mositie-hhomoeenenn and applied element-wise (such as the ReLU), Then,
D II
EoE(LIJN
sup NEW 1=1
o,H()s)) & SVNB(V2Dm2++ 1) Mr 1=1
A.2 Main Results
Theorem 4.1. For any x X, h E H and E A, assume have ((((x))(<x)) S Then, with probability at least 1 - 8. we can derive the following general bound,
In(8/d)
(D((pl)) Dx(P10) & 2Di(pll) + -2)x(() - (2) + 12c1
N
Proof. We observe that
(DR(ellg) (
(er) (p(h [(((h.) ((()))
(g(h))) (p(hi,) (q(T + +
(7)
(g(h)) - (xhh + ( -c,(hin) + c (p((h))) - (p(him) + ey (p((ra) 2g(tma)
< (b)) - (b())) + (T..) - + (pp((r)) - ex (ww) + (en(Ten)) Eg Ea(Wen))
<2DL(vlla) + (ep((.)) - ep (hw) + (r)) - -
The first two inequalities are owing to the triangle inequality, and the third inequality is due to the definition of L-divergence (5). We complete the proof by applying Lemma A. to bound (h.w) -x.( and e (h... (h... in Eq.
14

---

Corollary 4.2. Following the conditions of Theorem 4.1 the upper bound of Var [
34c 2
+
2t
2R
N
Proof. For convenience, assume C = (PL(p)))) + 22) + 2 Corollary in [62], we have
(7) Following proof of
Var Pu(Pl@)
SE (Du(Plla--Dace (abbll))-D((PP) Du(PlT)
Pr (R(Plll) DR(FlT) 2 vi dt
(RR(Pll)) (F(2)T)
Pr
2sds
0
2sds
Pr
Du(p DR(ella) 2c+ s 2 s)ds
0=0
==0
-N22
SC² 16
(C + s)e 1446 ds
(8)
-N
000
N2a2
c + 16C
144 ds + 16
se 1442 ds
==0
==0
11
C + 16Cc
-1 dt +
2304c 1
f
-e dt
N
J==
1152c
C2 + 96CC
N
34c VN
2
+ CVV21
2T
where the third inequality is due to
Pr Pu(elle) - (R(() 2 C
N22 < Se 1440.
(9)
obtained from the results of Theorem
Proposition 4.3. Based on the conditions of Theorem 4.1 we assume H is the class of real-valued networks of depth D over the domain X. Let the Frobenius norm of the weight matrices be at most and applied element-win wise
My...., MD. the activation function be I-Lipschitz, positive-homogenu (such the ReLU). Then, with probability at least 1 8, have,
(DR(Pllg) - (F (DL()) ALB 2D 2 + II
M; + 120
(n(8/)) N
VN
Proof. We complete the proof by applying Lemma A.3 and Lemma A.4 to bound the Rademacher
complexity of deep neural networks Theorem 4.1
Corollary 4.4. Following the conditions of Proposition 4.3
with probability at least 1 8, we have
the following conditional bounds Dr < (h en (T..)
SLB(V2Dm22 + 1 Mi
ln(6/88
(R(p)))) DR <
220y
V
N
15

---

Proof. Following the proof of Theorem 4.1 we have
(DR(pllg) DR(P
- [,((1))) - -pp(h + - (hw + Es(( - ex (g((h)) Eg(kmN
-
- -max (g((1h)) - sp(h") + +c((h) (h) (Eg(h") + tx((h)) - (s>(h) - cg(h))
(10)
+ (a(( - ( + (g((mn)) (rw)
22 max (D(plll), (e((h)) En(hi) + (Ep(T.)) sp((k) [/g(ke)) EG(hu))
22 cah")) cu (h) (p(hw)) cp (hu) +lc((nw) - (Rmu)
The first two inequalities owing to the triangle inequality, and the third inequality is due the given condition (pl(p) I cu ( cu ( We complete the proof by applying Lemma A.2
to bound E
6u (u(h") Eu ( and Lemma A.I to bound (ép(fe)) ep (hrw)
and |e (hw))) Eg (hw) in
Corollary 4.5. Following the conditions of Proposition 4.3 as N + co, we have, DR < (pll)) + DR(pll)).
Proof. Based on the result on Proposition 4.3 for any E (0, 1), we know that
i=1 M;
[n(8/8) 0,
+2eg
(11)
VN
N
when N oc. We complete the proof by applying the triangle inequality.
B Algorithm Procedure
B.1 Training Procedure of R-Div
Algorithm 1 Estimate model-oriented distribution discrepancy by R-divergence
Input: two datasets P and and learning model T with hypothesis space H. and loss function / Generate the merged dataset: î = p U
Learn the minimum hypothesis on the mixed data:
hy arg min En (h) heW
Evaluate the empirical risks: (ha and (ha) Estimate the R-divergence as the discrepancy:
(x (pp(ha) - (ba(aa)
Output: empirical estimator (
B.2 Calculation Procedure of the Average Test Power
16

---

Algorithm 2 Calculate the average test power of R-divergence
Input: datasets p and ?7. empirical estimator DR(-II-,, a, K. 2 for = to K do for 1 to Z do
if 2 = 1 then
(p'.0") (7,
else
Generate (p", 7-) by uniformly randomly swapping samples between p and q end if
Calculate (R( (T) end for
Obtain
(PR(
(Du(pl@) Φ) is in the top a-quantile among 9)
Tk
end for
Output: average test power Σ
Table 7: Method Comparison.
Methods
Discrepancy
Remasks
Tasg((t) J k(s, t)dp(r))
V En (1y( - My (T)3)
Iokea,, f) expp lir /-/
I.T is drawn from un absolutely contimous distribution.
he (e))i(() f w(rr) sin(a: 1)dp(t))
V 23 (TT) xx))( (x)o (T))
SCF
m=) (t) = I xx=))cof( cos(s c( (e)pp(a) [1b((r))
transform kemel.
C
Iall Exeare (w)(x) null Eo fw(xx)
I: for fhr p. dr. tue
binay classiffer segorate and fir
Samples from (w, 2) (f=(z) 1)
labeled with 1. respectivell.
CISTLL
1Ax 11 Exere (m)x.0) Ee' (1(('11)
/B (Mxx, k(H.v") 2k(2. 2,2 P.U. -
MMD-D
[k(s, is simple kernal.
bku (a. u) = [[1 - c) (dh.. (s)())) + c]Ra(a, v)
2h v]]. 2, P. ~
Ibo is deep network with parameters Midi (x. exp(- wll /72)
MMD-D
(Vikg(..)) exp(- -yll/>3
Eha E arg ongmingere (1))) ih,, crgmin (h)
B-D
dlen (he (h (hg))
mll,, (l) = Easu)((((e) a(x))
(h) = Eawg ((na) Vi0(0, A) = "* or max(0, A)
R-INv
(ep())) (17))
C
Compared Methods
Mean embedding (ME) [1] and smooth characteristic functions (SCF) 30 the state-of-thh-art
methods using differences in Gaussian mean embeddings at a set of optimized points and frequencies, respectively. Classifier two-sample tests, including C2STS-S 43 and C2ST-L [TO] apply the classification accuracy of a binary classifier to distinguish between the two distributions. The binary classifier treats samples from one dataset as positive and the other dataset negative. These two methods assume that the binary classifier cannot distinguish these two kinds of samples if their distributions identical. Differently, C2STS-S and C2ST-L apply the test error and the test error gap to evaluate the discrepancy, respectively. MMD-O 20
measures the maximum mean discrepancy (MMD) with Gaussian Kernel [19. and MMD-D 41 improves the performance of MMD-0 by replacing the Gaussian Kernel with learnable deep kernel. H-Divergence (H-Div) (62 learns optimal hypotheses for the mixture distribution and each individual distribution for the specific model, assuming that the expected risk of training data on the mixture distribution is higher than that on each individual distribution if the two distributions are identical. The equations of these compared methods are presented in Figure 7
17

---

D Additional Experimental Results
D.1
Benchmark Dataset
ME SCF - C2STS-S - C2ST-L MMD-O M H-V R-Div
HDGM
HDGM
Average Test Power
Average Test Power
0.5
0.5
10
15
20
0
2000
4000
6000
8000
10000
Dimension of Samples
Number of Samples
Figure 3: The average test power on HDGM with the significant level a 0.05. Left panel: results with the same sample size (4,000) and different feature dimensions. Right panel: results with the same feature dimensions (10) and different sample sizes.
ME SCF
C2STS-S C2ST-L MMD-O
MMD-D - H-Div R-Div
Blob (o 0.05)
Blob 0.01)
Average Test Power
Average Test Power
0.5
0.5
0
20
40
60
80
100
0
20
40
60
80
100
Number Samples
Number of Samples
Figure 4: The average test power on Blob at the significant levels a 0.05 and 0.01.
Table 8: The average test power + standard enror with the significant level a 0.05 on MNIST. N represents the number of samples each given dataset, and boldface values represent the relatively better discrepancy estimation.
N
200
400
600
800
1000
Avg.
ME
0.414+t0.000
0.921 =o.032
1.000
1.000-1:0.000
1.000=t0.0m
0.867
SCF
0.107-to.018
0.152
0.294
0.317=t0.017
0.346=to.019
0.243
C2STS-S
0.193
0.646=t0.039
1.000
1.000-1:0000
1.000
0.768
C2ST-L
0.234-10.031
0.706-L0.047
0.977 000022
1.000-1..00
1.000-L0.000
0.783
MMD-O
0.188-100000
0.363
0.619-L-0001
0.797
0.894-10.016
0.572
MMD-D
0.555-L0.044
0.996-t0.004
1.000
1.000
0.0000
1.000-L-.000
0.910
H-Div
1.000--0.000
1.000 0.000
1.000-1-0000
1.000
0.000
1.000-t-.o0e 0.000
1.000
R-Div
1.000-10.000
1.000=10.000
1.000
1.000 100000
1.000-t..00
1.000
18

---

D.2 PACS Dataset
PACS (A C)
Average Test Power
0.8
0.6
0.4
0.24
H-Div
R-Div
0
10
15
20
25
40
Number of Samples
Figure 5: The average test power at the significant level a = 0.05 on the art painting and cartoon domains of PACS.
D.3 Learning with Noisy Labels
CIFARTO (Paitip)
CIFARR1 (Parl (FFAR10
CIFARIO (Parlip)
Phehetted
Vocal
0.1
0.2
0.5
04
08
0.7
0.7
(a) Accuracy
(b) Detection
(c) Discrepancy
Figure 6: Results on CIFARIO with pair flipping. All values are averaged over five trials. Left: Classification accuracy of pretrained and retrained networks. Middle: Precision and recall rates of detecting clean and noisy samples. Right: Discrepancy between predicted clean and noisy samples.
19


Reviews:
[{"review_id": "IfLkl0b1w5", "reviewer": "Reviewer_EFgW", "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.", "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?\n- What is the effect of regularization of the trained neural networks (e.g., weight decay) on the porposed distance in the experiments?\n- 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?\n", "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?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Simple method.\n- Empirical results are very good.\n- 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.\n- 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.\n- 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}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank your constructive comments.\n\n**W1. Theoretical upper bound:** \n\nWe agree that a large L-divergence $\\mathcal{D}_{\\textup{L}} (p || q)$ will affect the convergence of the empirical estimator. However, a large L-divergence contributes to identifying whether samples of two datasets are drawn from different distributions as it indicates that the two distributions are significantly different. Accordingly, the empirical estimator will converge to the sum of the discrepancy and the L-divergence as the sample size increases, as shown in Corollary 4.5. Both discrepancy and L-divergence represent large distribution discrepancies. Hence, an empirical estimator represents the significant difference between two distributions. Conversely, a small L-divergence indicates that the empirical estimator rapidly converges to a small discrepancy for increasing the sample size, as shown in Corollary 4.4. Therefore, the empirical estimator also represents the small distribution discrepancy if the samples of two given datasets are drawn from the same distribution.\n\n**W2. Citations:** \n\nThe network over-fitting issue is mentioned in [50], and H-divergence is proposed by [63]. Furthermore, in the last paragraph of Introduction on page 2, we claim that the over-fitting issues will cause a slight discrepancy estimated by H-divergence even if the two distributions are significantly different. This is because the datasets used to learn the minimum hypothesis and calculate their empirical risks are the same, which causes two similar and small empirical risks for the two distributions. Accordingly, the empirical risk gap is small for two significantly different distributions. The proposed R-divergence aims to address their over-fitting issues in estimating discrepancy by learning the minimum hypothesis and evaluating its empirical risks on different datasets.\n\n**W3. Theoretical notation:** \n\nIn the second paragraph of Section 2 on page 2, we state that $a \\in \\mathcal{A}$ is the target function, e.g., $a(x) = y$ for supervised classification and $a(x) = x$ for unsupervised input reconstruction. The theorems reflect general results for any input and output spaces. In the second paragraph of Introduction on page 1, we describe that whether the samples from two datasets are drawn from the same distribution depends on a specific learning model. The distributions of two given datasets can be treated as identical for some models but significantly different for others. Different learning models hold different hypothesis spaces, loss functions, target functions, and optimization processes, thus having different sensitivities to distribution discrepancies. For example, ‘apple’ and ‘banana’ are significantly different for a binary classification task. However, if our learning task is to learn a binary classifier to distinguish between ‘animal’ and ‘fruit’, the binary classifier can treat ‘apple’ and ‘banana’ as being drawn from the same mixture distribution and is not sensitive to their discrepancy. Accordingly, we propose the model-oriented distribution discrepancy evaluation. Therefore, instead of selecting a specific learning model $\\mathcal{T}$, the theory of R-divergence evaluates the discrepancy between two datasets for the model.\n\n**Q1. Theoretical lower bound:** \n\nWe are usually not concerned about the lower bound of the convergence because a zero lower bound can ensure that the empirical estimator tends to the discrepancy for both small and large $\\mathcal{D}_{\\textup{L}} (p \\| q)$. The upper bound is more essential to analyze whether the empirical estimator can represent the difference between two datasets. As discussed in your Q1, the upper bound is small for a small discrepancy, which indicates that the empirical estimator tends to the discrepancy. Furthermore, the upper bound is large for a large discrepancy. However, the empirical estimator converges to the sum of discrepancy and the large L-divergence, where both of them can represent the difference between two datasets, as shown in Corollary 4.5.\n\n**Q2. Effect of regularization:** \n\nRegularization is not significant for discrepancy estimation methods. We evaluate the discrepancies with and without weight decay (WD) and obtained the same results. The regularization aims to alleviate the over-fitting issue for improving the generalization. The regularization could increase the training losses. However, it still causes similar empirical risks on different training datasets, which causes a slight empirical risk gap between two significantly different datasets for the considered discrepancy estimation task. Therefore, the network regularization cannot address the over-fitting issue and make the discrepancy more distinct for different distributions and datasets.\n\n| Datasets| A+C | A+P | A+S | C+P | C+S | P+S | Ave. |\n|------------|-------|-------|-------|-------|-------|-------|-------|\n| R-Div w/ WD| 1.000 |1.000 |1.000 |0.524 |0.572 |0.978 |0.846 |\n| R-Div w/o WD| 1.000 |1.000 |1.000 |0527 |0589 |0980 |0.849 |\n\n**Q3. Amount of over-fitting:** \n\nThe amount of over-fitting, i.e., the empirical risk, for L-divergence, H-divergence, and R-divergence on MNIST (N = 200) are reported below. The results show that R-divergence can obtain a much more distinct discrepancy due to the significantly different empirical risk values for $p$ and $q$. This is because R-divergence addresses the over-fitting issue by optimizing a minimum hypothesis on a mixed dataset and evaluating its empirical risks on different datasets. Therefore, R-divergence can induce a more distinct discrepancy for two significantly different distributions.\n\n| Methods | Empirical Risk for p  | Empirical Risk for q   | Estimated Discrepancy |\n|------------|-------|-------|-------|\n| L-Div    | 713.0658 | 713.1922 | 0.0212 |\n| H-Div    | 111.7207 | 118.9020 | 1.6603 |\n| R-Div    | 144.0869 | 99.6166 | 44.4703 |\n\nWe will clarify the above in the final version."}, {"review_id": "WL1UpCOmHn", "reviewer": "Reviewer_b1Kb", "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. ", "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?", "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?", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The method is very easy to follow. Authors also provide valid theoretical analysis (although some results rely heavily on previous literature). \n2. Sufficient experiments in different learning scenarios (e.g., multiple domains, spurious correlations, and noise labels) are performed. \n3. 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. \n2. Since R-divergence is model-oriented. How to select hypothesis space and loss functions in practice?\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your comments, below we address all and also clarify potential misreading and misunderstanding.\n\n**W1. Significance of R-divergence:** \n\nR-divergence is significantly different from L-  and H-divergence, discussed in the last paragraph of Introduction and Table 6. R- and L-divergences consider different hypotheses and for different scenarios. R- and H-divergences have different assumptions about the discrepancy evaluation principles and empirical risk calculation approaches. Specifically, R-divergence significantly improves performance by addressing the over-fitting issues of H-divergence.\n\nH-divergence assumes two distributions are different if the optimal decision loss is higher on their mixture distribution than on the individual ones. Accordingly, H-divergence trains a minimum hypothesis and evaluates its empirical risk on the same dataset, which causes small empirical risks for different datasets. The small empirical risks lead to a slight estimated discrepancy for two significantly different datasets, which fails to evaluate the discrepancy. In contrast, R-divergence addresses this issue by assuming that two distributions are likely identical if the optimal hypothesis has the same expected risk on each distribution. Accordingly, R-divergence merely learns a minimum hypothesis on the mixed data and evaluates its empirical risks on two individual datasets. R-divergence treats the empirical risk gap as the discrepancy, which ensures small and large gaps for similar and different datasets, respectively.\n\nTechnically, R-divergence merely explores a minimum hypothesis on the mixed data, while L-divergence explores all the hypothesis space. Hence, R-divergence is model-oriented, considering their hypothesis space, loss function, target function, and the optimization process. Theoretically, R-divergence can be bounded by L-divergence, as shown in Corollary 4.5 and quickly converges for small L-divergence , as shown in Corollary 4.4. However, H-divergence cannot guarantee this property theoretically.\n\n**W2. Significance of model-oriented discrepancy:**\n\nIt is essential to consider a model-oriented discrepancy measure because whether the samples of two datasets are drawn from the same distribution is relative. Specifically, different tasks have different requirements with corresponding hypotheses, loss functions, target functions, and optimization algorithms, inducing different sensitivities to distribution discrepancy. \n\nFor example, the samples of the two datasets are drawn from different distributions for a binary classification task, while they tend to be treated as samples drawn from a mixture distribution for outlier detection and one-class classification tasks. Another example is that images of ‘Shiba Inu’ and ‘Corgi’ tend to be treated as samples from two different distributions if we aim to learn a binary classifier to distinguish them. However, they tend to be treated as sampled from a mixture distribution if we annotate both as ‘Dog’ and learn a multi-class classifier with ‘Cat’ images for a binary classifier to distinguish between ‘Dog’ and ‘Cat’.\n\n**W3. Hypothesis space and loss functions:** \n\nWe believe there was a misreading of the definition. As stated in the second paragraph of Introduction, R-divergence is model-oriented for a specific learning model rather than hypothesis/loss function driven. Accordingly, it is unnecessary to select hypothesis spaces and loss functions for R-divergence, and R-divergence estimates the discrepancy for a specific learning task. Therefore, it is reasonable to obtain different results for different learning tasks.\n\nWe describe that whether the samples from two datasets are drawn from the same distribution depends on a specific learning model. Different learning models hold different hypothesis spaces, loss functions, target functions, and optimization processes, thus having different sensitivity levels to distribution discrepancies. Therefore, the distributions of two given datasets can be treated as identical for some models but significantly different for others. Accordingly, in our experiments, we evaluate the discrepancy estimation performance for different network architectures (Table 5), datasets (Table 4), and tasks (Table 7 for reconstruction and Table 2 for classification).\n\n**Q1. Analysis for improved performance:** \n\nThe discrepancy is distinct for two different distributions, even if the sample size is small, which benefits from addressing the over-fitting issue by learning the minimum hypothesis and evaluating its empirical risks on different datasets. \n\nR-divergence learns a minimum hypothesis on the mixed data. It achieves the same empirical risks on the two datasets where the samples are drawn from the same distribution. Contrarily, the empirical risks are different if the samples of two datasets are drawn from different distributions because the training dataset of the minimum hypothesis is not exactly the same as the two individual ones.\n\nFrom the theoretical perspective, as shown in Corollary 4.5, the empirical estimator of R-divergence can be bounded by discrepancy and L-divergence for significantly different distributions, which indicates that R-divergence can achieve a more distinct estimated discrepancy for different distributions. Please also refer to our response to Q1 for more information.\n\n**Q2. Case study:** \n\nThe application of H-divergence in learning with noisy labels struggles to outperform the state-of-the-art approaches. This is because the research field has evolved over many years with significantly better results. The H-divergence application is more of an exploratory attempt, where we have incorporated H-divergence as a plugin within the baseline. Our work identifies a new avenue in this research field beyond establishing superiority. Furthermore, the case study illustrates the applicability of our proposed model in other domains.\n\nWe will clarify the above in the final version."}, {"review_id": "9IMlBkND82", "reviewer": "Reviewer_3ypD", "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.\n", "questions": "Many of my questions have been included in a previous section but are summarized again below:\n\n1. Why is R-divergence a good measure of discrepancy?\n2. Do the results on MNIST hold if we consider a deep convolutional network?\n3. Can we separate out two distributions where one contains classes 0,1 and the other contains classes 2,3 from MNIST (or CIFAR10)?\n4. Do these results rely on the datasets having different scales for the losses and is this common across many datasets?\n\n", "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.", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "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.\n", "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.\n\n**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.\n\nI 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. \n\n**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.\n\n**Simple failure case of R-divergence**: Consider two distributions\n$$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),$$\ndefined on $\\mathbb{R} \\times$ { $-1, 1$}. \nThe 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. \n\n**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.\n\nFor 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.\n\n\n[1] Zhao, Shengjia, et al. \"Comparing distributions by measuring differences that affect decision making.\" International Conference on Learning Representations. 2021.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your comments, address them while also clarify potential misunderstandings below.\n\n**Q1. Advantages of R-divergence:** \n\nR-divergence is a good measure for both theoretical and practical advantages because R-divergence benefits from addressing the over-fitting issue and estimates the discrepancy with theoretical guarantees. Specifically, R-divergence learns a minimum hypothesis and calculates its empirical risk on different datasets to avoid a small empirical risk gap for significantly different distributions, as discussed in the second paragraph of Introduction. Furthermore, R-divergence can quickly converge to the sum of two terms as the sample size increases, where both terms can represent large discrepancies for two different distributions, as shown in Corollary 4.5.\n\n**Q2. Definition, Experiments with deep convolutional network, and Insight:** \n\nWe believe there was a misreading of the definition. As stated in the second paragraph of Introduction, 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. The distributions of two given datasets can be treated as identical for some models but significantly different for others. This is because different models have different sensitivities to distribution discrepancy. For example, images of ‘Shiba Inu’ and ‘Corgi’ tend to be treated as sampled from two different distributions if we aim to learn a binary classifier to distinguish them. However, they could be treated as sampled from a mixture distribution by annotating all the images as ‘Dog’ and learn a multi-class classifier with ‘Cat’ images to learn a binary classifier to distinguish ‘Dog’ from ‘Cat’.\n\nWe have performed experiments on MNIST with a deep neural network, i.e., LeNet. The results for the reconstruction task with MLP and binary cross-entropy are reported in Table 7, and the results for the classification task with LeNet and cross-entropy are reported below. The results show that the distribution discrepancies are distinct for both the reconstruction and classification tasks. The classification task achieves worst test power than the reconstruction task, which is reasonable. The classification task is less sensitive to the discrepancy because the two datasets have the same label space, and the samples of the two datasets are with covariate shifts. Furthermore, the minimum hypothesis on the mixed dataset can generalize to the samples from the two datasets, which causes the samples to tend to be drawn from a mixture distribution for this classification task.\n\n| N | 200  | 400    | 600    | 800    | 1000    | Avg.    |\n|------------|-------|-------|-------|-------|-------|-------|\n| R-Div | 0.000  | 0.210 | 0.512 | 0.976 | 1.000 | 0.539 |\n\nProposition 4.3 shows that the empirical estimator of R-divergence can quickly converge to the discrepancy if the L-divergence is small and the sample size goes to infinity. Furthermore, Corollary 4.5 shows that R-divergence can quickly converge to the sum of L-divergence and discrepancy by increasing the sample size for a large L-divergence, where both terms can represent the difference between two distributions. Therefore, for both scenarios, R-divergence can quickly converge to a measurement representing the difference between two distributions as the sample size goes to infinity. \n\n**Q3. Failure cases and experiments on different classes:** \n\nWe believe there was a misunderstanding. R-divergence can succeed in the mentioned simple case. It is impossible to find a linear hypothesis that perfectly fixes the two distributions, which indicates its empirical risks on the two datasets are not zero, and we measure the discrepancy by the empirical risk gap. 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 even if the math expressions are significantly different, and this task may treat the two as one mixture distribution. For example, ‘apple’ and ‘banana’ are significantly different for a binary classification task. However, if our learning task is to learn a binary classifier to distinguish between ‘animal’ and ‘fruit’, the binary classifier can treat ‘apple’ and ‘banana’ as being drawn from the same mixture distribution and is not sensitive to their discrepancy.\n\nR-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. Furthermore, the permutation test is applied to calculate the significant level which indicates whether the method can incorrectly decide two different distributions. The following experiment results show that R-divergence can easily separate samples with different classes from MNIST. R-divergence firstly learns a minimum hypothesis on the mixed data (classes 0~3) and calculates its empirical risks on classes 0,1 and classes 2,3, respectively. Using permutation, the minimum hypothesis is the same. However, both datasets contain samples of the four classes, which causes similar empirical risks and a small gap. Therefore, the estimated discrepancy between the original two datasets can easily be against the permutation cases. The experiments with LeNet are reported below for your reference.\n\n| N | 40  | 80    | 120    | 160    | 200    | Avg.    |\n|------------|-------|-------|-------|-------|-------|-------|\n| R-Div | 0  | 0.540 | 0.845 | 1.000 | 1.000 | 0.677  |\n\n**Q4. Data scales:** \n\nR-divergence is not sensitive to the data scales because the experiments for Imagenet vs. Its corrupted (1% Gaussian) variants with different scales lead to similar results.\n\n| Scales | 32 | 120 | 224 |\n|------------|-------|-------|-------|\n| Resize | 0.733 | 0.725 | 0.722 | \n| Crop  | 0.739 | 0.736 | 0.719 | \n\nWe will clarify the above in the final version."}, {"review_id": "rNXsdHce8F", "reviewer": "Reviewer_Z32S", "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.\nIf 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.\nThe 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.\n\nThe 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. \n\nThe paper conducts two-sample tests over different datasets and architecture and achieves superior numbers than H-divergence. ", "questions": "I have already mentioned the questions in the weakness section.", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "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. \n\n2. The paper achieves strong results over the baseline divergence metrics over different datasets and with different model architectures.  \n\n3. 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. \n\n4. 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.\n\n2. 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your comments and address them below.\n\n**Q1. Different corruptions:**\n\nThank you for your insightful comments and suggestions. Following the construction methods of corrupted samples in [56] and the setup of H-divergence [63], we have performed experiments of R-divergence with partial corruption types (Gauss, Snow, Speckle, and Impulse) at four corruption levels (0.5%, 1%, 2%, and 5%) on CIFAR10 and adopted Resnet18 as the backbone. Evaluating the discrepancies for data with subtle corruptions is challenging because the corresponding probability distributions are not significantly different. That is why we apply a large scale (N = 5000) for CIFAR10 vs. Corrupted-CIFAR10 and R-divergence achieves 0 test power when the corruption level is mild (e.g. 0.5%). The experimental results on different corruption types are consistent, i.e., R-divergence can obtain better performance for larger corruption levels and outperform H-divergence for all corruption types and levels.\n\nThe average test power of H-divergence / R-divergence:\n| Corruption | 0.5%  | 1%    | 2%    | 5%    |\n|------------|-------|-------|-------|-------|\n| Gauss     | 0.000 / 0.000 | 0.195 / **0.219** | 0.368 / **0.411** | 0.710 / **0.748** |\n| Snow      | 0.000 / 0.000 | 0.096 / **0.189** | 0.251 / **0.277** | 0.366 / **0.416** |\n| Speckle    | 0.000 / 0.000 | 0.275 / **0.340** | 0.458 / **0.513** | 0.685 / **0.771** |\n| Impulse   | 0.000 / 0.000 | 0.127 / **0.185** | 0.277 / **0.326** | 0.629 / **0.652** |\n\n[56] Sun et al, Test-time training with self-supervision for generalization under distribution shifts, ICML, 2020.\n[63] Zhao et al, Comparing distributions by measuring differences that affect decision making, ICLR, 2022.\n\n**Q2. ImageNet and its corrupted variants:**\n\nFollowing the setup of the experiments on CIFAR10 vs Corrupted-CIFAR10, we have performed experiments of R-divergence on ImageNet (N = 1000) and its corrupted variants (Gauss, Snow, Speckle, and Impulse) with backbone Resnet12. The test power of H-divergence and R-divergence monotonically increases as the corruption level increases. Furthermore, R-divergence outperforms H-divergence on all the corruption types and levels. The results verify that the proposed R-divergence can be applied to estimate the distribution discrepancy for large-resolution datasets effectively.\n\nThe average test power of H-divergence / R-divergence:\n| Corruption | 0.5%  | 1%    | 2%    | 5%    |\n|------------|-------|-------|-------|-------|\n| Gauss     | 0.000 / 0.000 | 0.680 / **0.722** | **1.000** / **1.000** | **1.000** / **1.000** |\n| Snow      | 0.000 / 0.000 | 0.774 / **0.816** | 0.785 / **0.836** | **1.000** / **1.000** |\n| Speckle    | 0.000 / 0.000 | 0.586 / **0.624** | 0.762 / **0.804** | **1.000** / **1.000** |\n| Impulse   | 0.000 / 0.000 | 0.339 / **0.485** | 0.545 / **0.635** | **1.000** / **1.000** |\n\nWe will clarify the above in the final version."}]

Author rebuttal:
We are grateful for all the reviewers for their valuable feedback and insightful comments on our paper. 

We are heartened to see that two of the reviewers have acknowledged the significance, contribution and quality of our work, where both assign a score of 7. We appreciate their positive remarks and thank them for acknowledging the significance of our research.

However, we acknowledge that the reviews also demonstrate a notable divergence of perspectives among the reviewers. We are also serious about the divided comments made by two other reviewers. After carefully reading comments by Reviewer b1Kb, s/he misreads or misunderstands our work by mixing our proposed R-divergence with a simple combination of L-divergence and H-divergence, which is incorrect and inconsistent with our design and statement in the paper. Accordingly, s/he misunderstands that our method is sensitive to hypothesis space and loss function, which is again incorrect and inconsistent with our design. We clarify their misunderstanding in the rebuttal. 

Further, Reviewer 3ypD basically misunderstands our work perhaps also because of lacky of background expertise in the area. His/her questions do not conform to our motivation of proposing R-divergence to address the over-fitting issue relating to a specific learning task. Their misunderstandings with the corresponding inappropriate examples may be because of their misalignment of our work to the related work on L-divergence and H-divergence. We clarify their misunderstandings in the rebuttal. 

Triggered by the notable divergence between the reviewers, during the rebuttal, we treat each comment seriously, especially those misunderstandings, and have made significant changes to address all comments and substantially improved the paper quality. We have provided more detailed explanations to address some of the points relating to misreadings and misunderstandings of our research setup and motivation. We are confident that the improved manuscript will be better aligned with the expectations of all the reviewers. In short, the main changes are summarized below. We have: 

1. provided more in-depth analyses of the theoretical results in order to explain why the algorithm converges rapidly and achieves favorable outcomes; 

2. adjusted the citations to avoid causing confusion and misunderstandings; 

3. offered additional examples and analyses to illustrate the significance of model-oriented discrepancy estimation; 

4. present the amount of over-fitting to validate the motivation; 

5. provided further explanations to illustrate the distinctions between the proposed approach and existing methods; 

6. provided additional analyses to explain why the proposed method can achieve impressive results even with limited samples; 

7. provided more explanations for the failure cases and performed extra experiments with different network architectures on different tasks to verify the effectiveness of the proposed methods; 

8. added experiments to verify R-divergence is not sensitive to data scales;

9. performed extra experiments on different corruption types and levels to verify the effectiveness of the proposed methods. 

Once again, we extend our sincere appreciation to all reviewers for their time and effort in evaluating our work. We are committed to enhancing the quality of our research and making it valuable to the community by addressing all valuable and constructive comments. Please feel free to reach out if there are any further questions or clarifications needed. We are eagerly looking forward to the opportunity to present our improved work to you.

Meta-review: This paper introduces a novel method for quantifying the divergence between two probability distributions. Reviewers have recognized the significance of this contribution, highlighting the simplicity and strong theoretical foundation of the presented method. Furthermore, the experimental results have been found to be compelling. One minor concern, raised by a reviewer, pertains to the lack of clarity regarding why the proposed R-divergence appears to be unaffected by overfitting while the H-divergence is susceptible to it. It is advisable for the authors to provide additional clarification or discussion on this matter in the final version of the paper.
Decision: Accept (poster)