H-divergence: A Decision-Theoretic Probability Discrepancy Measure 
Authors: Shengjia Zhao
Abhishek Sinha
Yutong He
Aidan Perreault
Jiaming Song
Stefano Ermon
Venue:  (2021)
Keywords: probability divergence
two sample test
maximum mean discrepancy

Abstract: Measuring the discrepancy between two probability distributions is a fundamental problem in machine learning and statistics. Based on ideas from decision theory, we investigate a new class of discrepancies that are based on the optimal decision loss. Two probability distributions are different if the optimal decision loss is higher on the mixture distribution than on each individual distribution. We show that this generalizes popular notions of discrepancy measurements such as the Jensen Shannon divergence and the maximum mean discrepancy. We apply our approach to two-sample tests, which evaluates whether two sets of samples come from the same distribution. On various benchmark and real datasets, we demonstrate that tests based on our generalized notion of discrepancy is able to achieve superior test power. We also apply our approach to sample quality evaluation as an alternative to the FID score, and to understanding the effects of climate change on different social and economic activities.

Under review as a conference paper at ICLR 2021
H-DIVERGENCE: A DECISION-THEORTTC PROBABIL- ITY DISCREPANCY MEASURE
Anonymous authors Paper under double-blind review
ABSTRACT
Measuring the discrepancy between two probability distributions is fundamental problem in machine learning and statistics. Based on ideas from decision theory, we investigate new class of discrepancies that are based on the optimal deci- sion loss. Two probability distributions are different if the optimal decision loss is higher on the mixture distribution than on each individual distribution. We show that this generalizes popular notions of discrepancy measurements such as the Jensen Shannon divergence and the maximum mean discrepancy. We apply our approach to two-sample tests, which evaluates whether two sets of samples come from the same distribution. On various benchmark and real datasets, we demon- strate that tests based on our generalized notion of discrepancy is able to achieve superior test power. We also apply our approach to sample quality evaluation as alternative the FID score, and to understanding the effects of climate change on different social and economic activities.
INTRODUCTION
Quantifying the difference between two probability distributions is fundamental problem in ma- chine learning. Modelers choose different types of discrepancies, or probability divergences, to encode their prior knowledge, i.e. which aspects should be considered to evaluate the difference, and how they should be weighted. The divergences used in machine learning typically fall into two categories, integral probability metries (IPMs, Müller (1997)), and f-divergences (Csiszár, 1964). IPMs, such as the Wasserstein distance, maximum mean discrepancy (MMD), are based on the idea that two distributions are identical, any function should have the same expectation under both distributions. IPM is defined as the maximum difference in expectation for a set of functions. IPMs are used to define training objectives for generative models (Arjovsky et al., 2017), perform dependence tests (Doran et al., 2014), robust optimization (Esfahani & Kuhn, 2018) among many other applications. On the other hand, f-divergences, such as the KL divergence and the Jensen Shannon divergence, and are based on the idea that if two distributions are identical, they assign the same likelihood to every point, so the ratio of the likelihood always equals one. One can define a distance based on the how the likelihood ratio differs from one. KI. divergence underlies some of the most commonly used training objectives for both supervised and unsupervised machine learning algorithms, such as minimizing the cross entropy loss.
We propose a third category of divergences called H H-divergences that overlaps with but does not equate the set of integral probability metries or the f-divergences. Our distance is based on a generalization (DeGroot et al., 1962) of Shannon entropy and the quadratic entropy (Burbea & Rao, 1982). Instead of measuring the best average code length of any encoding scheme (Shannon entropy), the generalized entropy can choose any loss function (rather than code length) and set of actions (rather than encoding schemes), and is defined as the best expected loss among the set of actions. In particular, given two distribution p and g, we compare the generalized entropy of the mixture distribution (p + 42 and the generalized entropy of p and y individually. Intuitively, p and are different, it is more difficuul to minimize expected loss under the mixture distribution (p + 4), and hence the mixture distribution should have higher generalized entropy; if p and q are identical, then the mixture distribution is identical to p or g. and hence should have the same gen- eralized entropy. We define the divergence based on the difference between entropy of the mixture distribution and the entropy of individual distributions.

---

Under review as a conference paper at ICLR 2021
Divergence
Jenson Shannon
MMD
Total Voriation
KL
Wasserstein Distance
f-Dvergence
IPM
Figure 1: Relationship between H-divergence (this paper) and existing divergences. The Jensen Shannon divergence is an f-divergence but not an IPM; the MMD is an IPM but not an f-divergence; both are H-divergences. There also H-divergences that are not f-divergences or IPMs.
Our distance strictly generalizes the maximum mean discrepancy and the Jensen Shannon diver- gence. We illustrate this via the Venn diagram in Figure 1. This generalization allows us to choose special losses and actions spaces to leverage inductive biases and machine learning models from different problem domains. For example, if we choose the generalized entropy as the maximum log likelihood of deep generative models, we are able to recover a distance that works well for distributions over high dimensional images.
To demonstrate the empirical utility of our proposed divergence, we use for the task of two sample test, where the goal is to identify whether two sets of samples come from the same distribution or not. test based on a probability discrepancy declares two sets of samples different their discrepancy exceed some threshold. We use H-divergences based generalized entropy defined by the log likelihood of off-the-shelf generative models. Compared to state-of thethe-rrtt tests based on e.g. MMD with deep kernels (Liu al., 2020), tests based the H-divergence achieve better test power on a large set of benchmark datasets.
As another application, compare a set of samples (e.g. generated images from a GAN) with ground truth samples (e.g. real images). We show that H-divergences generally monotonically increase with the amount of corrup- tion added to the samples (which should lead to worse sample quality), even in certain situations where the FID score (Heusel al., 2017) not monotonically increasing.
H-divergence for sample quality evaluation, where the goal is to
Finally we show that H- H-Divergence can be used to understand whether distribution change affect decision making. As an illustrative example, we study whether climate change affect decision mak- ing in agriculture and energy production. Traditional divergences (such as KL. let policy makers measure if the climate has changed; H-Divergence can provide additional information on whether the change is relevant to decision making for different social and economic activities.
2 BACKGROUND
2.1 PROBABILITY DISTANCES
finite dimensional vector space, and P(X) denote the set of prob- ability distributions on X' that have a density. We consider the problem of defining probability divergence between any two distributions in P(X), where probability divergence is any function D : P(X) x P(X) + R that satisfies D(pll)) 2 0, D(pli) 0, Vp. E P(X) (Note that in general divergence does not require D(plig) Vp ②)
Let X' denote finite
Integral Probability Metrics ity metrics is defined
Let F denote some set of functions X - R. The integral probabil-
IPM = sup Bx(((X) - Ex([(())
feF
Several important divergences belong to integral probability metrics. Examples include the Wasser- stein distance, where FF is the set of 1-Lipschitz functions; the total variation distance, where F is the set of functions X + [-1, 1]. The maximum mean discrepancy (MMD) (Rao, 1982; Burbea & Rao, 1984; Gretton et al., 2012) chooses a kernel function k x X - R2 and defined by MMD(pllg) (Xp, Y) E. (x,, kEp.q (X.Y)
2

---

Under review as a conference paper at ICLR 2021
MMD is an IPM where F is the unit norm functions in the RKHS associated with the kernel At.
/- Divergences Choose any convex continuous function f 1 - R such that f(1) = 0, the f- D-ivergence is defined as (assuming densities exist) Dy q) = (x Examples of f f-Divergences include the KL divergence, where f : é log and the Jensen Shannon divergence,
where f + (t +
log F+1
+ tlgt.
Scoring Rule Distance (Grünwald et al., 2004; Gneiting & Raftery, 2007) Another large class of probability distances defined by proper scoring rules. A function S P(X) P(X) + R is called proper scoring rule if vp, 9 E P(X)) we have S(p, q) 2 S(p,p), Intuitively it is any function that is small when two distributions are identical and large when two distributions differ. Given scoring rule S we can define distance by Ds(pllg) S(p, ④) S(p.p).
2.2 H-ENTROPY
For any action space A and any loss function x A R. the H-entropy (DeGroot al., 1962; DeGroot, 2005; Grünwald et al., 2004) is defined as Hr(p) = infae (T[[(XXa)))
In words, Heenrrop
Bayes optimal loss of a decision maker who must select some action not for particular but for an expectation over p(z:).
H-entropy generalizes several important notions of uncertainty. Examples include: Shannon En- tropy, where A as the set of probabilities P(X), and f(xz a) log a(x); Variance where A X, and E(x, a) = || a [ Predictive V-entropy, where A C P(X) is some subset of distributions, and f(r, a) log a(x) (Xu al., 2020).
The most important property that we will use that the H entropy is concave.
Lemma 1. (DeGroot et al., 1962) For any choice of f X x A R, Hr is concave function.
This Lemma can be proved by observing that inf is a concave function, i.e., always better to pick an optimal action for and separately rather than a single one for both.
Hz + a1))) = inf (orEE, [8(X, a)] + - a) a)))
2 an E (ex. + - a1-a) inf inf a[ (1-a))(00
This Lemma reflects why Hg can be thought of as a measurement of entropy uncertainty. If the distribution is more uncertain (e.g. mixture of p and rather than p and & separately) then the optimal action always suffers higher loss.
DEFINITION AND THEORETICAL PROPERTIES
3.1 H-JENSEN SHANNON DIVERGENCE
As warm up, we first present special case of our definition. Definition (H-Jensen Shannon divergence).
D (p. = He
p
1 2 (He(p) + He(g))
(1)
2
2
The above is divergence between p and because H-entropy is concave, D. is always non- negative. In particular, if we choose He as the Shannon entropy. Definition recovers the usual Jensen Shannon divergence. Other special choices of entropy also recover definitions in (Burbea & Rao, 1982). addition, we can define divergence for any convex combination ap + (1 a)g where (0, 1) but for this paper only consider 1/2.
3

---

Under review as a conference paper at ICLR 2021
3.2 GENERAL H-DIVERGENCE
In addition to the H-Jensen Shannon divergence, there other functions based the H-entropy that satisfy the requirements of a divergence. For example, the following quantity
D Min = He (p++t (ain(He))),H(lo 2
(2)
also a valid divergence (this will be proved later as a special case of Lemma 2). We can define general set of divergences that includes the above two divergences with the following definition:
Definition 2 (H-divergence). For two distributions p. P on X, choose any continuous function I²a + I. such that o(0, A) > O whenever 0 + À > and 6(0, X) = =0 whenever 0 + X = 0, define
(plll))) = Φ He
- He(p), He p
p 2
He(())
2
Intuitively He (2 - He(p) and He ( He(g) measure how much more difficult to minimize loss the mixture distribution 4// than on p and q respectively. ø is general class of function that could convert these differences into divergence, while satisfying the desirable properties in the next section.
The H-divergence generalizes all the previous definitions, as shown by the following proposition. Therefore any property of H-divergence is inherited by e.g. H-Jensen Shannon divergence.
Proposition 1. Choose @60, A) 6+2 then D2 (p. q) the H-Jensen Shannon divergence in Eq.(1).
Choose @00, A) max(#, X) then D (p. q) the H-Min divergence in (q.
3.3 PROPERTIES OF THE H-DIVERGENCE
We first verify that D is indeed probability divergence. In particular, Lemma 2 show that D satisfies the requirements for a probability divergence. For the proof see Appendix A.
Lemma 2. For any choice of and for any choice of o that satisfy Definition 2, D is non-negative and D (p.9) g) = 0 whenever p
One important property of the H-divergence is that two distributions have non-zero divergence if and only if they have different optimal actions, i.c. the optimal solutions for their respective H-entropy different. This is shown in the following proposition (proof in Appendix A).
Proposition 2. arg inf, Ep [X( a)] n ang By [e(X, a]] 0 if and only D 0.
Intuitively, Dj only takes into account any difference between distributions that lead to different choice of optimal actions. This property allow us to incorporate prior knowledge about the problem. By choosing the A and & we can specify which differences between distributions lead to different optimal actions, and which differences do not. The corresponding D will only non-zero when two distributions differ in way we would like to capture.
For example, we can choose A set of generative models (e.g. VAEs) and {(x, a) is the negative log likelihood of æ under generative model a. If under two distributions we end up learning the same generative model that maximizes log likelihood, the H-divergence between them is zero.
3.4 RELATIONSHIP TO MMD
An important special case of the H-divergence is the set of Maximum Mean Discrepency (MMD) distances, as shown by the following theorem
Theorem 1. The set of H-Jensen Shannon Divergences is strictly larger than the set of MMD dis- lances.
4

---

For the task of two sample test, we would like to decide if two sets of samples are drawn from the same distribution. Specifically, given two sets of samples Pm = (æ1, 2mm p and qm == Typically two sample test algorithm estimates Under review as a conference paper at ICLR 2021
To prove this theorem for each choice of kernel & X X (details in Appendix A) such that
R+ construct some A and &
+ 4 - _ E [0 X) + 2 R
1
1
(X, He(p) - [ X - (xx,,
P [ ()
4 g l: (x Y)
マ Bn. (xx,,
2
2
He(g) E.y [k X)]
E. (X, (X Y)]
Simple algebra show that applying Definition recovers the MMD distance with kernel k.
3.5 ESTIMATION AND CONVERGENCE
In many downstream tasks, we would like estimate the H-divergence from data. Specifically we are provided with set of i.idd samples P... = (I1,'* Fm) drawn from distribution and 4m -=11. II'n drawn from distribution q. and would like to obtain estimate of D2 (pllg) based on the samples. In this section we propose an empirical estimator for the H-divergence and show that has nice convergence properties.
Let Dg (fm (m)m be the empirical (random) estimator for Dj (pll4) defined by
m
Σ Exo7 a) inf T7 inf m
Σ
Ele,, a), inf m Σ ((]) a) -inf m i=1
Σ E(())aa)
where x² = .rGb + 21((1 - b,) is sample from the mixture distribution (p + g)/2 for b, uniformly sampled from {0, 1}.
Before presenting the convergence results, we first must define several assumptions that make con- vergence possible. In particular, we are going to assume that the loss function is C-bounded, i.e. there exists some C such that ( S E(x, a) < C, Va, v. In addition, we assume that ø is 1-Lipschitz under the oc-norm, i.e. 1Ø(0- + d0, À + dA) s00, X)] S max(d0, dA), V0, X, d0, dλ E is not 1-Lipschitz can often rescale ø to make it I-Lipschitz. Finally, define the Radamacher complexity of l as
m Σ e,l(xxaa)
Rh (E) =
((x=)=)===paeae Expsp.cr
sup aeA m
Based on these assumptions we can bound the difference between D (pm (4m) and Dj (pllq). Theorem Ifí is C-bounded, and & is 1-Lipschitz under the co-norm, for any choice of distribution P.q E P(X) and f. >> O we have
1. Pr[D) (m)) 2 2) 4e 202 ifp=
12m 2. Pr (pm - D2 2 mm, R4. (1)) + < 4e 263
For proof see Appendix A. What is most interesting about Theorem 2 is that when p g, the con- vergence of D (fm (. does not depend on the Radamacher complexity of This particularly useful for two sample test, where we would like to decide if p q based on finite samples. If the empirical estimate Dj @P (Pm.llmm) will quickly converge to 0 for relatively small sample size m.
EXPERIMENT: TWO SAMPLE TEST
4.1 TWO SAMPLE TEST
lt
(1',--- .,... ltd. q would like to decide if some divergence (pm (l)m)) and outputs p + q if the divergence exceeds some threshold.
5

---

tune pyrre-parameters as Under review as a conference paper at ICLR 2021
Ra01002 Tapes EEne
3.00
2.00
42
100
20
60
100
Samples
Figure 2: Average test power (Left) and the average type I error (Right) on the Blob dataset for different sample sizes. For our method (dashed line). H-Div (10) and H-Div (15) use a mixture of Gaussian distribution with 10 and 15 mixture components respectively (details in Section 4.3). Our method has significantly better test power (left plot).
There are types of errors: Type error happens when p q but the algorithm incorrectly outputs # 9. The probability that an algorithm makes a type I error is called the significance level. Type error happens when p # q but the algorithm incorrectly outputs p q. The probability an algorithm does NOT make type II error is called the test power (higher is better). Note that both the significance level and the test power are defined relative to the distribution p and g.
We follow the typical setup where we would like to guarantee the significance level while empirically measuring the test power. In particular, the significance level can be guaranteed with a permutation test (Ernst et al., 2004). In permutation test, in addition to the original set of samples Pm. and Qm. we also uniformly randomly swap elements between Pm and q... and sample multiple randomly swapped datasets (pi.., (m)), (Pe (m)).... The testing algorithm outputs * if (f (m) is in the top a-quantile among { (D(i) (1 DGE l ...... "..,.....
Permutation test guarantees the sig- nificance level (i.e. low Type I error) because if p = then swapping elements between p... and im should not change its distribution, so each pair (pm: 9m), (p 4t,) ",. should have the same distribution. Therefore, (pm (m) happens to be in the top a-quantile with at most probability.
4.2 EXPERIMENT SETUP
Dataset We follow Liu et al. (2020) and consider four datasets: Blob (Liu et al., 2020), HDGM (Liu et al., 2020), HIGGS Addam-Bourdane et al., 2014) and MNIST (LeCun & Cortes, 2010).
Baselines We compare our proposed approach with six other divergences. All methods are based on the permutation test explained in Section 4.
MMD-D & MMD-O: MMD-D (Liu al., 2020) measures the MMD distance with deep kernel, while MMD-O (Gretton et al., 2012) measures the MMD distance with a Gaussian kernel.
ME & SCF: Mean embedding (ME) and smoothed characteristic functions (SCF) (Chwialkowski et al., 2015; Jitkrittum et al., 2016) are distances based on the difference in Gaussian kernel mean embedding at a set of optimized points, or set of optimized frequencies.
C2STS-S & C2ST-L: (Lopez-Paz & Oquab, 2017; Cheng & Cloninger, 2019) classifier's accuracy distinguishing between the two distributions to measure the probability discrepancy.
4.3 IMPLEMENTATION DETAILS
In the evaluation benchmark proposed in (Liu et al., 2020) there are two sets of samples, a training set used to tune hyper-parameters, and validation set used to for evaluating the test performance. The training set and the validation set have the same number of samples. We also leverage the training set, but we only have one choice of hyper-parametee. which is the function In particular,
choose d0, A) = (8"+x*) 1/s for > 1 (which includes the H-Jensen Shannon divergence when 8 = and the H-Min divergence when s = Do. We use the training set to find the best parameter For fair comparison each baseline method also the training implemented in (Liu et al., 2020).
If a tie is possible, then always break ties by sorting D(pm ((@m) in front. In this case the significance level most (and could be less).

---

Under review as a conference paper at ICLR 2021
MMD-O
C2ST4L
C25T-8
ME
MMD-O
HADV
1.00
0.10
10
0.10
Becrngo TooggToo..e Toa.
Asaage Erie
Aaclugh Todl Plwvec
Avorage Typo: Enie
2.26
0.0g
25.0
4003) 20-33
50.00
10000
0.00g
2000
403 9233 5000 5000
Figure 3: Average test power and type error on HDGM dataset. Left: results with the same sample size (4000) and different data dimensions. Right: results with the same sample dimension (10) and different sample sizes. Our method (H-Div, dashed line) achieve better test power for almost every setup. In particular, when the data dimension is small, all tests have high test power. Our method scales better with data dimension and shows an advantage for higher dimensional problems.
For all the experiments, we always choose to be set of distributions, and (xx a) as the negative log likelihood of / under distribution For the Blob and HDGM dataset, we choose A as the set of mixture Gaussian distributions. The number of mixture component intentionally different from the ground truth dataset to show that our approach performs well under mild mis-specifiiation. We also provide results for Blob choosing Parzen density estimtor as A in Appendix B.1. For the Higgs dataset we Parzen density estimator, and for MNIST use variational autoencoder (Kingma & Welling, 2013).
Each permutation test 100 permutations, and power (i.e. the percent times correctly outputs p + q)- Finally we plot and report the perfor- mance standard deviation by repeating the entire experiment 10 times.
each test 100 times compute the test
4.4 EXPERIMENT RESULTS
The average test powers are reported in Figure 2, Figure 3, Table and Table 2. Our approach achieves superior test power across the board. Notably on the Higgs dataset we achieve the same test power with 2-5x fewer samples than the second best test, and on the MNIST dataset we can achieve perfect test power even on the smallest sample size evaluated in (Liu et al., 2020). Our method also produces consistent test power in comparison with the baselines as we observe much lower variance of the test power between different random draws of the dataset.
Following (Liu et al., 2020) we also evaluate the test power as the dimension of the problem increases (Figure 3). Our test power decreases gracefully the dimension of the problem increases.
N
ME
SCF
C2ST-S
C2ST-L
MMD-O
MMD-D
H-Div
1000
0. 0000
0.095-10.007
0.082-t0005
0.097-1:004
0.132-ta0.05
0.113
0.240-L..020
2000
0. 1..
0.130=t0.019
t.003
0.232.to.02
0.291
0.304
0.380-10.040
3000
0. 197-
0..142+0.025
0.257+00m9
0.399-Honss
0.376-tuaz2
+..00-+0.000
0.685-+..00
5000
0.410:2o.041
0.261=10.044
0.592-10.097
0.447
0.659-10.01
0.699
1.00011..000
8000
0.691 +-0067
0.4677
0.892++0009
0.
0.923
0.952-+-.0024
1.000
10000
0.786
0..03
0.974:10.007
0.985:10005
1.000
1.000=1..000
1.000-L0.000
Avg.
0.395
0.283
0.497
0.506
0.564
0.579
0.847
Table 1: Average test power + standard error for N samples over the HIGGS dataset.
N
ME
SCF
C2ST-S
C2ST-L
MMD-O
MMD-D
H-Div
200
0.404
0.107-10.018
0.193-La.037
0.234-io.081
0.188-La.010
0.555-Lo.044
1.000-10.000
400
0.92 i..032
0.152-:0.021
0.646-20.039
0.706=t0.047
0.363-ta.017
0.996=20.001
1.000=20.000
600
-.000-10.000
0.294-1-0.00
1.000-L0.000
0.977=t0.012
0.619-10.021
1.000=10.000
1.000-10.000
800
1. t0.000000000
0.317=t0.017
1.000=20.000
1.000=1:.000
0.797=t0.015
1.000=10.000
1.000=20.000
1000
1. 1.000
0.346:50.019
1.000=00.000
1.000=t0.000
0.894-10.016
1.000=00.000
1.000=10.000
Avg.
0.867
0.243
0.768
0.783
0.572
0.910
1.000
Table 2: Average test power + standard error for N samples over the MNIST dataset.
7

---

Under review as a conference paper at ICLR 2021
0.200
32
0.175
2.8
0.150
2.4
0.125
2.0
1.6
0.075
12
0.050
0.8
0.025
0.4
0.000
0.0
Figure 4: Example plots of H-divergence across different geographical locations for losses é related agriculture (left) and energy production (right). Darker color indicates larger H-divergence. Com- pared to divergences such as KL. H-divergence measures changes relevant to different social and economic activities (by selecting appropriate loss functions f). For example, even though climate change significantly impact the high latitude or high altitude areas, this change has less relevance to agriculture (because few agriculture activities are possible in these areas).
5 EXPERIMENT: MEASURING CLIMATE CHANGE
This experiment aims to show that a domain expert designs a loss function f: X'xAAA - IR, they can obtain valuable insight from the associated H-JS divergence DJS. As illustrative example climate data and study how climate change affects decision making. The H-divergence allows policy makers to quantitatively measure aspects of climate change that are relevant decision making in different areas such as agriculture or renewable energy production.
Setup We use the NOAA database which contains daily weather from thousands of weather sta- tions at different geographical locations. For each location, we summarize the weather sequence of each year into a few summary statisties (the average temperature, rainfall, etc). In other words, E X' represents the yearly weather summary. Let p denote the empirical distribution of yearly weather for the years 1981-1999, and q denote the empirical distribution of yearly weather for the years 2000-2019. (p + 4) 2 can be interpreted as the yearly weather empirical distribution for the entire period 1981-2 Further details of these experiments are in Appendix C.2.
Example: Agriculture It is known that climate changes affect crop suitability (Lobell et al., 2008). Let A denote the set of possible crops to plant such as wheat/barley/rice, and f(x, a) de- note the loss of planting crop if the yearly weather is x. We estimate the function E by matching geographical locations in the FAO crop yield dataset (FAOSTAT et al., 2006) to weather stations in the NOAA database, and learn function to predict crop yield from weather data with kernel ridge regression. For each geographical location we can compute the H-divergence D for the estimated (plotted Figure 4 left).
The H-divergence has natural interpretation: a geographical location could either (1) plant the same crop for the entire period 1981-2019 that is optimal for the local climate (i.e. choose a" = arg min I (2(p)))/2((()) ((((, a)): (2) plant the optimal crops for 1981-1999 and for 2000-2019 respectively. divergence measures the additional loss of option (1) compared to option (2). In other words, it is the excess loss of not adapting crop type to climate change.
Example: Energy production Changes in weather also affect electricity generation, since cli- mate change could affect the amount of wind/solar energy available. Let A denote the number of wind/solar/fossil fuel power plants built, and É(z, a) denote the loss (negative utility) when the weather is We obtain the function é by empirical estimation formulas for energy produc- tion (Npower, 2012). The H-divergence for this loss function is shown in Figure (right). Intuitively the H divergence measures the excess loss of using the same energy generation infrastructure for the entire time period vs. using different infrastructure that adapts to climate change.
EXPERIMENT: EVALUATING SAMPLE QUALITY
We also qualitatively verify that H- E--ivergeece defines a distance between distributions that are often consistent with human intuition. For example, this can be used to evaluate generative models, where
Designing loss functions l that capture the effect of climate on human activities is a well studied topic in economics and environmental science, and beyond the scope of this work. Because of the simplifications we' 'vee made, our results should he taken illustrative example of how domain experts might H-divergence.
8

---

Under review as a conference paper at ICLR 2021
the gold standard evaluation of the distance between generated images and real images usually with human judgement (Zhou et al., 2019). Human evaluation expensive, so several surrogate measurements are commonly used, such the Frechet Inception Distance (FID) (Heusel et al., 2017) or the inception score.
For this task, choose A as the set of Gaussian mixture distributions on the inception feature space and [[x a) as the negative log likelihood of x under distribution a. To evaluate the performance, we use the same setup (Heusel et al., 2017), where we add corruption (such Gaussian noise) from (Hendrycks & Dietterich, 2019) to a set of samples. Intuitively, adding more corruption degrades the sample quality, so a good measurement sample quality should assign lower quality score (higher divergence). The results are plotted in Figure 5. The remaining plots of other perturbations are in Appendix B.2. Both FID and H-divergence are generally monotonically increasing as we increase the amount of corruption. Our method is slightly better some perturbations (such "snow"), where the FID fails be monotonically increasing, but our method is still monotonic.
FII
F.D
PD
HGN
Homa and Draacc
60
Figure 5: The divergence between corrupted image and original image measured by H-divergence vs. FID. For better comparison we normalize each distance to between [o, 1] by a linear transforma- tion. For "speckle" and "impulse" corruption, both divergences monotonically increasing with more corruption. For "snow" corruption H-divergence is monotonic while FID is not. Other types of corruptions are provided Appendix
7 DISCUSSION AND OPEN QUESTIONS
Explaining improved test power We postulate that the test power improvements come from leveraging progress in generative model research: for each type of data (e.g. bio, image, text) there has been decades of research finding suitable generative models; models (in modern literature) for each data type (e.g. KDE for low dimensional physics/bio data, VAE for simple images). Further study is needed to further explain the observed experiment result.
commonly used generative
Computational efficiency If l is not a convex function then evaluating the H-divergence can be computationally difficult. In particular, gradient descent does not guarantee finding arg inf, (EX, This can be a short-coming terpret the empirical H-divergence estimation with caution. The practical remedy we use in paper (when is non-convex) is to use the same number of gradient update steps for evaluating He (2t))) He(p), He(g). Additional techniques to address non-convex optimization (such Stein Variational Gradient Descent, restarts, beam search, etc) are interesting future work.
H-divergence, and practitioners should in-
For H-divergence there is trade-off between faster computation and accurate estimation of H- divergence (which should lead to improved test power). Our implementation takes about hours a single GPU, while the second best baseline (MMD-D) takes about 30 minutes. In time sensitive applications, studying the trade-off between computation time and test power is an interesting question.
Statistical efficiency In Theorem H-divergence can be efficiently estimated (i.e. independent of the Radamacher complexity of E) when p q. However, MMD can be efficiently estimated even when p * q (Gretton et al., 2012). It is an open question whether this is true for other special classes of H-divergences.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Claire Adam-Bourdarios, Glen Cowan, Cécile Germain, Isabelle Guyon, Balázs Kégl, and David Rousseau. The higgs boson machine learning challenge. In Proceedings of the 2014 International Conference on High-Energy Physics and Machine Learning - Volume 42, HEPML' 14, pp. 19-55. JML,.org, 2014.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. arXiv:1701.0787. 2017.
Wasserstein gan.
arXiv preprint
Jacob Burbea and Radhakrishna Rao. Entropy differential metric, distance and divergence mea- sures in probability spaces: A unified approach. Journal of Multivariate Analysis, 12(4))575-596 1982.
Jacob Burbea and C Radhakrishna Rao. Differential metrics in probability spaces. Probah. Math. Stat, 3:241-258, 1984.
X. Cheng and A. Cloninger. Classification logit two-sample testing by neural networks. ArXiv, abs/1909.11298, 2019.
Kacper P Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, and Arthur Gretton. Fast two-sample testing with analytic representations of probability measures. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 1981-1989. Curran Associates, Inc., 2015.
Imre Csiszár. Eine informationsthhorrtishhee ungleichung und ihre anwendung auf beweis der er- godizitaet markoffschen ketten. Magyer Tud. Akad. Mat. Kutato Int. Koezl, 8:85-108, 1964.
Morris H DeGroot. Optimal statistical decisions, volume 82. John Wiley & Sons, 2005.
Morris H DeGroot et al. Uncertainty, information, and sequential experiments. The Annals of Mathematical Statistics, 33(2):404-419 1962.
Gary Doran, Krikamol Muandet, Kun Zhang, and Berhaard Schölkopf. A permutation-based kernel conditional independence test. In UAI, pp. 132-141, 2014.
Michael D Ernst et al. Permutation methods: a basis for exact inference. Statistical Science, 19(4): 676-685, 2004.
Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 17 171(1-2):115-16) 2018.
FAO FAOSTAT et al. Fao statistical databases. Rome: Food and Agriculture Organization of the United Nations, 2006.
Tilmann Gneiting and Adrian E Raftery. Strietly proper scoring rules, prediction, and estimation.
Journal of the American statistical Association, 102(477):359-37, 2007.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola.
A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Peter D Grünwald, A Philip Dawid, et al. Game theory, maximum entropy, minimum discrepancy and robust bayesian decision theory. the Annals of Statistics, 32(4):1367-1433 2004.
Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. arXiv preprint 19X. 2019,
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge local nash equilibrium. In Advances in neural information processing systems, pp. 6626-6637, 2017.
Wittawat Jitkrittum, Zoltán Szabó, Kacper P Chwialkowski, and Arthur Gretton. Interpretable dis- tribution features with maximum testing power. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 181-189. Curran Associates, Inc., 2016.
10

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Max Welling. arXiv:1312.61 1v110, December 2013.
Auto-Encoding variational bayes.
arXiv preprint
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann
lecun. comm/exdb/nee /wtts//ni//////.mmm///mm/m....ms
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang. Gretton, and D. Sutherland. Learning deep kernels for non-parametric two-sample tests. ArXiv, abs/2002.09116, 2020.
David B Lobell, Marshall B Burke, Claudia Tebaldi, Michael D Mastrandrea, Walter P Falcon, and Rosamond Naylor. Prioritizing climate change adaptation needs for food security 2030. Science, 319(5863):00--610, 2008.
David Lopez-Paz and M. Oquab. Revisiting classifier two-sample tests. arXiv: Machine Learning. 2017.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, pp. 429 429-443, 1997.
Npower. Wind turbine power calculations. Mechanical and Electrical Engineering Power Industry, The Royal Academy of Engineering, 2012.
C Radhakrishna Rao. Diversity and dissimilarity coefficients: unified approach. Theoretical population biology, 21(1):24-43, 1982.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints. arXiv preprint arXiv:2002.10689 2020.
Sharon Zhou, Mitchell Gordon, Ranjay Krishna, Austin Narcomey, Li F Fei-Fei, and Michael Bern- stein. Hype: A benchmark for human eye perceptual evaluation of generative models. In Advances in Neural Information Processing Systemx, pp. 3449-3461, 2019.

---

Under review as a conference paper at ICLR 2021
A PROOFS
Lemma 2. For any choice of E and for any choice of & that satisfy Definition 2, Dj is non-negative and Dt (p:0) q) 0 whenever p 9-
Proof of Lemma 2. For any choice of p, q by the convexity of the H-entropy we have
He
+ 9
He(p) 2 / (Hell)) He(p))
2
p p+q q
Hi
-H((g) 2 2 (He(p) -He(a))
2
Therefore we have
+
Hc(o))
He p Ho(a) 20
Hi
2
By the requirement on & we know that (pllg) 2 0.
Proposition 2. arg inf E,le(X, a)] n arginf, Eg ((x a)] = 0 if and only if (pllg) > 0.
Proof of Proposition 2. Denote A; arg inf Ep[e(X a)] and A7 = ing Eg a)]. Also compute
p q 2
inf E Bug [6(X = = ( B a)] - =
Hi
(3)
If A A; = 0. for any action a' such that a)]]( a' & Ar and (,(((X,a))] > Helg). Similar if we choose a" such that 1 Hz(1) we have similarly have Ep[e(X, > He(p). In other words, for any choice of action E A either ExX((,a)]] He(p) or ((, a)] Helg). Therefore
He(p), we must have a' E AB so
(2,1((_0))) 01l > He(p) + He(l))
inf E a)] + 1 19,
(4)
Combining (3) and (4) we have
1
He +
Hp(p))
+
He
+ q
He(g)
>
2
2
By Definition 2 this would imply (for any choice of à that satisfies the requirements in Definition 2
D2 > 0.
To prove the converse simply obverse that if A n A + Φ. E A₂ Ar we have arg inf P2p [)., This implies that
p pp+9) 9g) He(g) H2(p) 2E [(X, a -B,ta""aI',,,,,,,,,, -E,K,""")) 2
2Hg
By Definition we can conclude that (pllg) =
Theorem 1. The set of H-Jensen Shannon Divergences is strictly larger than the set of MMD dis- tances.
Proof of Theorem I. Let k(x,, y) some kernel on an input space X, and let H. be the RKHS induced by the kernel. Define ((x, y) = [|k(x,,) -) k(y, )) The MMD distance is defined by MMD(p, q) k(X, Ey (xx, (X,Y) 2E,.k(X,Y
12

---

Under review as a conference paper at ICLR 2021
We can rewrite this in the following form:
MMD(p, q) Ep.o X, X,Y) Fm.o(XX)) 11002EEE (x,,)(XX
We also observe algebraic relationship for any function f(X,Y)
Eeta mpe (e,, p -
1
I (X + pxp.((X.
4
2
Based on the above we can derive
MMD(p.g 9) = Ep.lll((x, :) - ((XY 2 Bp Bp.pllk(x; ((X)))) -
2 1 (1x,,, k(x,
= 24 240 [|x, :) - k(Y, 11 11 - Ep (Kx, k(x,)) 11 - Eg
- k(x
= -41E ||((X, :) - E p4o k(Y, -11 2E, (xx, EY,,,Y, - 2E (1., AE,,)
= 4 inf Beju [xx,, - all2r - inf aEH
Epl k(X,, all22 - -2 inf B,y (Ax((, -a112-
dEH
Therefore we can define a loss 8: X x H. + R where
((x, 0) 411b(2,, ( -al12
Under the new notation we have
1
MMD(p, q) -inf EeEEzlll EefEEe(aaa ((,a)
inf Ep((X,, a) + inf (X,(X, a))
2
-He p p
1 (H²( Hl(()) 12
2
Conversely we want to show that not every H-Jensen Shannon divergence a MMD. For example, take He be the Shannon entropy, then the corresponding D is the Jensen-Shannon divergence, which is not a MMD. This is because the JS divergence is type of f-divergence, and the only f-divergence that is also an IPM is total variation distance. Therefore, the set of H-Jensen Shannon Divergences is strictly larger than the set of MMDs.
Theorem 2. If is C-bounded, and Φ is 1-Lipschitz under the co-norm, for any choice of distribution P.q E (()) and we have
1. Pr[D (mm)) 2 t) < 4e 20 i-p=
2. Pr D (fm (mmmmmmmmmmm-)))m))))))) (oll))) 2 4 (R), (O) + < 4e
12m 22
Proof of Theorem 2. Let Pm sequence of n samples (x),... ,m, drawn from p. and Ôm a se-
quence of n samples (x',,- xnm)) drawn from q. Let fm the sub-sampling mixture (xf). =mm)
defined in Section 3.5 (i.e. x² = n.b; + x1 - b.) where b, is uniformly sampled from {0, 1)).
We also overload the notation He by defining Hz(mm) = infaEA m Em [(x, a), and define He He(ūm), (fm) similarly.
Before proving this theorem we need the following Lemmas
Lemma 3. Under the assumptions of Theorem 2
[r(Hee(m)) - E[Hi(fm) - 23m
6²
Lemma 4. Under the assumptions of Theorem
2 6 Pr Pr[[Hppp> He ) 2R (2) Se
13

---

Under review as a conference paper at ICLR 2021
To prove the first statement of the Theorem, when p q can denote E[He(pm)]
E Hl = (f)) and we have
D2 (pm lbm) 2 21 Pr
Pr(((He((Fm) He (mm), Hf H)((m)) 2
Def 2
Pr (f) Hm()m) 2 21 + [H:((m) Hz(mm) 2
Def 2, Union bound Union bound
Pr [He(pm) - μ 2 t/2] + Pr (fm) - μ t/2] + Pr He((m) - t/2]
de 2027m
Lemma 3
To prove the second statement of the Theorem, observe that
1D (pm lgm) (plla)
= =(H(H((fm)) Helfm)) He(fm)) He((m)) (He [ ( Help). He (2+ He(e))
Def 2
S <max (He(fm)) He He(dm) - He ( ( + He(p)) He((fm) - Helâm) - He (p+9) + H((e))
Φ 1-Lip
S max (Hr(fm)) - He p (P-2) He((m) Hr(p)l. HH((m)) H. (P (P+ + [Hr(qm)) H.(g)))
Jensen
2
2
Therefore, the event 110 (pmllam) D2 (xlla) 2 Max least one of the following events happen
(f), (f), Rg. (!) + happens only if
He((mm) H1 P 2 R. + RR, + +1/22 22 (2) + t/2
R convex
2
(He(Pm) - Hp(p)
2 2R (() t/2
[He(mm) H2(2)) > 2m (C) t/2
Based on Lemma each of these events only happen with probability at most conclude by union bound that
207 Therefore we
Pr|lD)(pllg)) - DJ (pllg)) 2 4 max (f), R2 (f)) + S 4e
Finally we prove the Lemmas used in the theorem. Lemma 4 is standard result in the Radamacher complexity literature. For proof, see e.g. Section 26.1 in (Shalev-Shwartz & Ben- David, 2014). Lemma also be proved by standard techniques. We provide the proof here.
Proof of Lemma 3. Consider two sets of samples -1,-.. ,I 2m and -',.... zyy, x where z! for every index i 1,... except index j.
inf 1 E(x,, inf Σ E( a) m
Σ ((1;,a) Σ (a),aa)
S sup
1
sup (((z,,)) - E(xx' S C
Then we can conclude by Mediarmid inequality that
Pr
inf 1 Σ m
((x,,
a)
E inf 1 m
Σ
E(X,,
21
62
2,2
212
14

---

Under review as a conference paper at ICLR 2021
B ADDITIONAL EXPERIMENTAL RESULTS
B.1 BLOB DATASET WITH PARZEN DENSITY ESTIMATOR
Average Typed Errrr
0.08
0.6
0.00
02
20
40
100
0.00
20
40
80
100
Samples per
Samples
Figure The same plot as Figure 2, but with Parzen density estimator and different hyper- parameters (with 30 random runs rather than 10). The conclusion is identical to Figure 2.
B.2 COMPLETE RESULTS FOR EVALUATING SAMPLE QUALITY EXPERIMENT
RD
1D
Serert
Sene bo Laraaou
1.0
1.2
HDV
14:3w
02
Seue ta Comsation
Serett at Canution
Sinito Camadiss
ploaltte
gaundien
oifecus
1.
115h
05
63
Smerdy Canelee
Figure 7: Additional plots that extend Figure 5.
15

---

Under review as a conference paper at ICLR 2021
C ADDITIONAL RESULTS
C.I CONNECTION TO OPTIMAL TRANSPORT
We first show that H-divergence also have transportation interpretation. For all the intuitive in- terpretations we avoid technical difficulty by assuming X' a finite set, even though all the formulas applicable when X' has infinite cardinality.
Setup Choose A = X, and let [(r, a) be a symmetric function (I(x, a) = Ma, x)) that denotes the cost of transporting unit of goods from x to When we say that unit of goods is located according to p. we mean that there is I unit of goods dispersed in X' locations, where p(x) is the amount of goods at location
Optimal Transport Distance The optimal transport distance is defined by
inf Or(p.4) rxy. rx Exxr [(XX,] Y)]
Intuitively the optimal transport distance measures the following cost: initially the goods are located according to p, we would like to move them to locate according q; O(p, q) denote the minimum cost to accomplish this transportation task.
H-Divergence as Optimal Storage We first consider the intuitive interpretation to the H-entropy (p)p) inf (x,(X,,)))
a" arg inf (,)(((X, a)]
aEX
Suppose we want to move goods located according to p to a storage location (for example, we want to collect all the mail in city to package center), then a" is the optimal location to build the storage location, and H-entropy measures the minimum cost to transport all goods to the storage location. Similarly 2Hz (et2) measures the minimum cost to transport both goods located according p and goods located according to to the same storage location. The H-divergence
2 == 2Hg
P g+
(H& He(p))
2
measures the reduction of transportation cost with storage locations (one for p and one for ②) rather than a single storage location (for both p and q).
The H-Divergence is related to the optimal transport distance by the following inequality.
Proposition If satisfies the triangle inequality Vx. y, E X, N,1(1,1) v) - 1(y. 2) 2 1(x, 2) then (pllg) O(p.9)
Proof of Proposition 3. Let dz = arg inf (x, then we have
+ q
2Hg
inf (E,, a)) E,, a))) < EE, E,l(( at)l
2
inf XXx-Xx-Xx.Y inf Or(p. 9) + +He(g)
E Exxy ((X E, at) TXY Exxy (X C(Y, الحه + E. [X( am)]
Intuitively, to move goods located according to p and goods located according to to some storage location, option is first transport all goods from p g (so that the goods at location x will be 2g(x)), then move the goods located according to 2g to the optimal storage location. Similarly we have
p +
2H
s <()g.)) 2HH(p)
2
which combined have
2D
2H,
(p+g q
-(Helg) + H.(p)) S O(p.g)
2
16

---

Under review as a conference paper at ICLR 2021
C.2 CLIMATE CHANGE EXPERIMENT DETAILS
Setup Details In this experiment, we extract the statistics of yearly weather for each year from 1981-2019. We use the NOAA dataset, which contains daily weather data from thousands of weather stations across the globe. For each year we compute the following summary statistics: average yearly temperature, average yearly humidity, average yearly wind speed and average number of rainy days in an year. For example 21990 is a 4 dimensional vector where each dimension correspond to one of the summary statistics above.
Let denote the uniform distribution over {#1981. (1199) and q denote the uniform distribution over f ... #2019 For example [E,,((X, a)] denote the expected loss of action for random year sampled from 1981-1999. Note that for many decision problems, it is possible to make yearly decisions (e.g. decide the best crop to plant for each year). However, because we want measure 2000-2019,
the difference between two time periods 1981-1999 to be single crop selection that will be used for the entire time period (rather than a different crop selection for each year). Similarly for energy production choose the action space A to be the proportion of different energy production methods that will be used for the entire time period.
choose the action space A
Crop yield We obtain the crop yield loss function ((x, a) with the following procedure
1. We obtain the crop yield dataset from (FAOSTAT al., 2006), each entry extract is the following tuple: (country code, year, crop type, yield per hectare (kg/ha))
2. We associate each country code with the central coordinate (i.e. the average latitude and longitude) of the country. For each central coordinate we find the nearest weather station in the NOAA database. We use data for the nearest weather station as the weather data for the country.
3. Based on step 2 for each (country code, year) pair we can associate a weather statistics (i.e. the dimensional vector described in Setup Details). We update each entry in step be (weather statistics, crop type, yield per hectare).
4. Based on the data entries we obtain in step 3 we train a Kernel Ridge regression model to learn the function E(x, a) where is the weather statisties, is the crop type, and f(r, a) is learned to predict the yield (normalized by market price) of the weather x for crop type
Energy production We consider three types of energy production methods: solar, wind and tra- ditional (such fossil fuel). Solar energy and wind energy both depend heavily weather, while traditional energy does not. particular, we use empirical formulas for solar and wind energy calculation:
solar x number of sunny days * daylight hour wind wind velocity
17


Reviews:
[{"review_id": "Vc2sfDvaolZ", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a H divergence that is a generalization of many popular f divergences and IPMs. The paper gives an empirical estimator with convergence rates for this divergence, where the rates are very fast when the two distributions are equal. The paper shows how the empirical estimator has practical use for two sample tests and measuring the corruption of a sample. The proposed H divergence is \"useful\" when the two distributions are close to each other, but as the authors acknowledge in the future work, it is an open question whether it could be \"useful\" in other cases.\n\nOverall I think this paper is very interesting and has a lot of novelty. I am not extremely on top of the most recent literature on measuring differences between probability distributions, so there may be literature that is not being reviewed and ignored, but from an \"outsiders\" perspective this seems to be a significant contribution to the area. There are some minor grammar issues (see minor comments for the ones I caught) and the paper could use a thorough re-read for grammar in general. \n\nMajor Comments:\nThe proof for Proposition 2 shows that if the intersection between the optimal action spaces of p and q is empty, then the divergence is greater than 0. However it is not seem obvious that the converse is true i.e. if the divergence is greater than 0 then the intersection is empty. If the converse is trivial, having some explanation for it would be helpful.\n\nThe notation for the proof of Lemma 3 is rather confusing. The authors want to state that the two samples are equal except for at the points x_j and x'_j, but writing \"i \\neq j\" seems to imply at first glance that the two samples are not equal where the indexes don't line up instead i.e. x_1 \\neq x'_2. It would be clearer to just state x_i = x'_i except at one index j. Also remove the second \"consider\", it is not necessary.\n\nIs it computationally possible to run the experiments more than 10 times? The power looks good but the type I errors still look a little noisy. Granted the scale is very small, but 10 is not considered a large number of \"simulations\".\n\nMinor Comments:\n- Please make Figures 2 and 3 bigger. There seems to be some white space you can play with and there is some room before the 8 page limit.\n\n- Need an s here: \"distance that work(s) well for distributions over high dimensional images.\"\n\n- Remove \"among of\" here: \"We show that H-divergences generally monotonically increases with the among of corruption added to the samples \"?\n\n- Use \"or\" instead of a slash here: \"entropy / uncertainty\"\n\n- Remove \"in order\" here: \"measure how much more difficult it is in order to minimize loss on the mixture distribution\"\n\n- Insert \"that\" here: \"probability (that) an algorithm makes a type\"\n\n- \"test power\" is a strange term. Normally it is referred to as just \"power\" or \"statistical power\" or \"power of a test\"\n\n- The caption in Figure 3 has (Left 2) and (Right 2) which are weirdly bolded and might be better written as (two on the left) and (two on the right)? Also missing an \"s\" here: \"Our method (H-Div, dashed line) achieve(s)\"\n\n- Missing \"s\" here: \"Each permutation test use(s) 100 permutation(s)\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "VUnSd3bB7kk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors proposes a new class of divergence between probability distributions that generalizes both the Jensen-Shanon divergence and the Maximum Mean Discrepancy: the H-divergences.\nThose divergences are constructed using the notion of the $H$-entropy of a probability distribution $H(p)$ defined as the minimum expected loss of an action $a$ in a set of possible actions $H(p)=\\inf_{a\\in A}E[l(X,a)]$ where the expectation is over samples  $X$ from $p$. Thus the $H$-entropy requires choosing a set of possible actions $A$ and a loss function $l(X,a)$.\nThe $H$-divergence between two probability distributions $p$ and $q$ is then obtained by comparing the difference between the $H$-entropy of the mixture distribution $(p+q)/2$ and each individual $H$-entropy of $p$ and $q$. By concavity of the $H$-entropy, the difference are both equal to $0$ only when $p$ and $q$ are equal. To allow for more generality, such differences are fed to an evaluation function $\\phi$ so that the final form of the divergence is: \n$D(p|q) = \\phi( H((p+q)/2) - H(p), H((p+q)/2) - H(q) ) $.\nThe authors show that this form is general enough to include both the JS-divergence and the MMD.\nAn estimator of the $H$-divergence using finite samples from $p$ and $q$ is proposed along with a concentration result for this estimator that is based on the Rademacher complexity.\n\nExperiments:\nIn terms of experiments, to authors consider using the new divergence for two-sample tests and evaluating sample quality.\nIn the two sample setting, the authors perform extensive comparisons with other SOTA methods including the recent deep kernel two sample test outperforming all those methods in terms of test power, behavior with increasing dimension of the data and sample size.\n\nOn the sample quality task, the authors show that the proposed divergence is also correlated with human judgment for images. For this task, the authors chose the set of actions to be gaussian mixture of distributions on the inception feature space and the loss $l(X,a)$ to be the likelihood of a sample $X$ under the a mixture $a$. This is shown to often better capture corruption of the samples than the FID score. \n\n\n\n\n\n\nStrength:\n - The paper is clear and concise, the experiments are convincing as far as I understood.\n - The approach allows to incorporate prior knowledge about the problem by selecting a suitable set of actions $A$. In the case of two sample tests, this means that the method should capture differences between distributions that the user cares the most about. However it remains unclear if this flexibility cannot already be achieved using existing methods.\n\nWeaknesses:\nThe paper does not really motivate the need for such new divergences. Hence, the impact might be limited.\n\nThe authors suggest that the additional freedom in choosing the set of actions allows to design divergences that are tailored to a particular problem. However, the authors do not explain whether this new generalization is able achieve something that already existing divergence fail to achieve. For instance, is there any particular reason to think one wouldn't achieve  similar experimental performance with a better choice of parametrization for the deep kernel? in the case of MMD-D?\n\nIn the experiments, the author make different choices for the set of actions depending on the dataset: mixture of gaussians, Parzen density estimator and for MNIST, a variational auto-encoder. However, the authors do not really explain what guides such choice.\n\nThe proposed estimator: In practice, the optimization is likely to be non-convex, especially when the set of actions is chosen to be a parametric family of probability distributions. How does this affects the estimation of the H-divergence? It doesn't seem to be an issue in the experiments, but wouldn't this be a disadvantage compared to other tests that have a closed form expression for the estimator?\n\n\nQuestions:\n- Comparing the run time of each method? For instance SCF was designed to have a fast run time in the number of samples and tradeoff power for speed.\n- On the sample quality task. How does the proposed method compare to the KID score, which has the advantage to be unbiased.", "extra_scores": {}, "extra_text": {}}, {"review_id": "NRkF4rYLju", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new class of divergences defined by a decision-theoretic perspective, in the sense that two probability distributions are different if the optimal decision loss is\nhigher on the mixture distribution than on each individual distribution. This new class generalizes the popular Jensen-Shannon divergence and Maximum mean discrepancy and allows to define new divergences that only take into account differences that lead to different choice of optimal actions.\nSome basic properties of the new class and a theorem providing error bounds when estimating a divergence from this class from samples are shown.\nA two-sample test is proposed using  a permutation approach and some experimental results are provided on standard datasets.\n\nPros:\n- Interesting new divergence class including both JS and MMD allowing to define new divergences with a decision-theoretic perspective\n- Useful theoretical results \n\nCons:\n- I think that the decision-theoretic perspective has a great potential for making two-sample tests more meaningful but unfortunately it is not properly developed.\n- Two-sample test presentation lacks rigor\n- The experiments are not convincing\n\n\n\nThe paper is generally well written and the theoretical results seem correct although some proofs are a bit rushed. The experiments are not sufficiently detailed and no code is provided. The idea of generalizing divergences using a decision-theoretic perspective has already been proposed in [Grunwald&Dawid 2004] which is cited for the H-entropy but not for the generalized relative divergence, which should be mentioned. The proposed class of H divergences extending JS and MMD is novel as far as I know.  \nWhat I found especially promising but disappointingly not exploited in the two-sample test section is the following idea : \n\"Intuitively, $D^\\phi_l$  only takes into account any difference between distributions that lead to different\nchoice of optimal actions. This property allow us to incorporate prior knowledge about the problem.\"\nI would have liked to see this idea exploited in the two-sample test. Usually nonparametric two-sample tests aim at maximal power and this makes them sometimes not so useful in practice, in the sense that they summarize the output in 1 bit (saying whether p=q)  and don't tell anything about the nature of the difference, which could  be irrelevant under some decision-theoretic perspective.\n\nI recommend rejection since the real interest of this new class is mentioned but not properly shown and the two-sample test part is not strong enough.\n\nDetailed comments:\n\n1) Regarding the structure: \\\na) The \"definition\" part contains all the theoretical aspects of the proposed divergence not only the definition.\\\nb) The two-sample tests announced in the title only appear in the experimental part: I was expecting a section introducing definitions and literature for a general ML audience.\n\n2) When you define a divergence in section 2.1: \\\nIt would be useful to emphasize that your definition of divergence is broader than the usual in the sense that you can have $D(p,q) = 0$ for  $p \\neq q$. \n\n3) Regarding the choice of $\\alpha=1/2$, it would be interesting to the discuss whether it would relevant or not to consider a different $\\alpha$ .\n\n4) When $D^\\min_\\ell$ is defined, it is said that a proof regarding its validity as a divergence is provided later but I can't find such proof.\n\n5) After definition 2, it is claimed that $\\phi$  is the most general class function…, but there is no proof.\n\n6) Inconsistent notation between main text and proofs: \\\na) $\\hat{p}_m$ sometimes used as a set of samples, sometimes as an emprirical distribution which is a different object.\\\nb) $x''$  seems to define $\\hat{r}_m$ but it is not explicitly said\n\n7) The following statement should be more precise in what makes it \"impossible\" : \\\n\" it is well known that estimating the Jensen Shannon divergence between continuous distributions is impossible with finite data.\" \n\n8) You claim that part 1 (p=q) of theorem 2 is particularly useful for the two-sample test but in fact this is irrelevant in a permutation test. Under the null hypothesis (p=q), the distribution of the p-value is determined by the permutation procedure.\n\n9) The two-sample test subsection lacks rigor. In particular:\\\na) \"The probability an algorithm makes a type I error is called the p-value.\": This is not the standard definition of a p-value.\\\nb) What do you mean by a guaranteed p-value? Exact? Valid? This should be mathematically precise.\\\nc) In general, permutation tests should be presented with more rigor since there a different ways of doing them see e.g. \n\tErnst, Michael D. \"Permutation methods: a basis for exact inference.\" Statistical Science 19.4 (2004): 676-685.\n\t\n10) Experiments:\\\na) MNIST dataset: what are the two samples? Are they the same used in [Liu et al. 2020] where one of them is composed of GAN generated images?\\\nb) The training sizes should be explicitly specified to be able to compare to two-sample tests that compute the statistic on the whole dataset (e.g.  Hall & Tajvidi. \"Permutation tests for equality of distributions in high‐dimensional settings.\" Biometrika 89.2 (2002): 359-374.) or those that train in an online manner (e.g. Lhéritier & Cazals. \"Low-Complexity Nonparametric Bayesian Online Prediction with Universal Guarantees.\" NeurIPS 2019.)\\\nc) Figure 2: The numbers seem to correspond to the number of samples per gaussian (9), per population (2) per train/test dataset (2) (from [Liu et al. 2020]) e.g.:  20 samples in your plot means that you used 20x9x2x2=720 samples in total, if I understand correctly. \\\nd) I am confused by the Blobs and HDGM experiments: by using a gaussian mixture model in your test, I think that you are giving an unfair advantage to your test while at the same time penalizing it \"a little bit\"  with \"mild\" mis-specification. The aim of this setup is unclear.\\\ne) Figure 3: the caption should mention the name of the dataset\\\nf) Can you give an intuition on why your Parzen density estimation based test is superior to the other kernel methods on the HIGGS dataset? Where the additional power comes from?\\\ng) Overall, you should clearly justify the action space and the aim of each experiment i.e.: by choosing a specific action space, do you want to make the test more powerful than the contenders by providing it prior knowledge or do you want to tell test that only some type of differences matter (which would make it insensitive to some differences and therefore less powerful in comparison to more general tests)?\n\n11) Proofs:\\\na) Proposition 2: the proof seems to be incomplete. the last line implies that the JS is strictly positive but it doesn't seem to prove the claim for the general H-divergence.\\\nb) Theorem 2: sub-sampling mixture should be properly defined, I guess it corresponds to x'' in section 3.5\\\nc) Theorem 2: \\\nc1) you should clarify how you define the empirical distributions in the multivariate case \\\nc2) it would be helpful for the reader to explictly mention the properties used in the different derivations: 1-lipschitz, union bound, triangular inequality…\\\nc4) Citation of (Shalev-Shwartz & Ben-David, 2014) should be more precise\\\nc3) Lemma 3: First sentence: the second \"consider\"  should be removed I think.\n\t\nTypos:\\\n-- diveRgence : in the abstract\\\n-- we are able to recover a distance that workS\\\n-- that ~~have~~ have a density.\\\n-- 100 permutationS\\\n-- Last line of the proof of Lemma 2: $\\ell$ should appear instead of $\\mathcal{V}$\\\n-- Proof of theorem 1 says $V$ divergence instead of $H$ Jensen Shannon Divergence\\\n-- Proof of theorem 2: $\\hat{D}_\\ell^\\phi(p \\Vert q)$ should be $\\hat{D}_\\ell^\\phi(\\hat{p}_m \\Vert \\hat{q}_m)$.\n\n=====POST-REBUTTAL COMMENTS======== \n\nI thank the authors for the response and the efforts in the updated draft, in particular with respect to :\n- the new experiment (complementing the original one on blobs) whose results are reassuring \n- corrections and improvements in the proofs\n- the new experiment on climate change \n\nThe two-sample test part has been modified to take into account some of my comments but still lacks rigor. It doesn't explain the permutation procedure used and whether the p-values are just valid or exact. Now, the term \"significance level\" (replacing \"p-value\") is used to refer to the probability of type I error, which is not totally accurate in general. If the p-values are just valid and not exact, the significance level is a bound on the type I error. This should be fixed in the final version. \n\nRegarding my main concern, i.e. showing the interest of a decision-theoretic divergence using some custom loss, the new experiment on climate change is a good illustration of the interest of such divergences.\n\nIn summary, I see useful theoretical results and a step in this not-much-explored direction of tailoring divergences and two-sample tests with a decision-theoretic perspective, i.e. \"detecting differences that matter\", and thus I decided to raise my score.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4U_ZTlhTxV", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The distance or divergence between two probability distributions is essential for machine learning. This paper introduces a new class of divergence functions based on optimal decision loss function. They first introduce a class of entropy functional, namely the loss function depending on the action and state. This type of function extends the classical entropy function, including negative Boltzman-Shannon entropy. Using it, they further construct a divergence based on the mixture of probability densities.  Several propositions and numerical experiments demonstrate the effectiveness of proposed divergence functions. \n\nPro: The idea is clean, and the derivation is correct. Several analytical examples and detailed comparisons are presented. \n\nI still have some questions about the proposed approach. I may increase the rating if the author can address them. \n\n1. Have the author discuss the related Hessian metric for the proposed divergence function? For the KL divergence or Jen-Shannon divergence, the Hessian matrix for D(p, p+dp) recovers the Fisher information matrix. For the proposed approach, what is the corresponding information matrix? \n\nSee related studies in \n\nLi, Zhao, Wasserstein information matrix, 2019.\n\n2. The authors claim this divergence contains part of IPM (integral probability metrics). It would be better for the authors to discuss the relation of this proposed divergence with Wasserstein type divergences functions. \n\n3. Does the author consider the duality for the proposed divergence functionals? This could be useful in generative models. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The focus of the submission is the measuring of the discrepancy of two probability distributions. Using the notion of H-entropy, the authors propose a new divergence measure the H-divergence (Def. 2), as a common generalization of Jensen-Shannon divergence and maximum mean discrepancy. They suggest an empirical estimator for H-divergence and show that it is consistent (Theorem 2). The efficiency of the technique is illustrated in the context of 2-sample testing, sample quality evaluation and measuring climate change.

Overall, the submission addresses an important problem (defining a class of divergence measure). As pointed out by the reviewers, however fundamental questions on the proposed estimator are not addressed:
1)the motivation of using a set of actions (in the definition of H-divergence) and how to design them are unclear, 
2)the impact of the loss function l (in the definition of H-divergence) is not explored: this can easily lead to instabilities due to the lack of closed-form solution and by the arising non-convex optimization task.
The gain compared to existing solutions have to be understood and explored further.
Decision: Reject