Comparing Distributions by Measuring Dif- ferences that Affect Decision Making
Year: 2021

Abstract:
Measuring the discrepancy between two probability distributions is a fundamental problem in machine learning and statistics. We propose a new class of discrepancies based on the optimal loss for a decision task – two distributions are different if the optimal decision loss is higher on their mixture than on each individual distribution. By suitably choosing the decision task, this generalizes the Jensen-Shannon divergence and the maximum mean discrepancy family. We apply our approach to two-sample tests, and on various benchmarks, we achieve superior test power compared to competing methods. In addition, a modeler can directly specify their preferences when comparing distributions through the decision loss. We apply this property to understanding the effects of climate change on different economic activities and selecting features targeting different decision tasks.

heading: 1 Introduction
text: Quantifying the difference between two probability distributions is a fundamental problem in machine learning. Modelers choose different types of discrepancies (or probability divergences) to encode their prior knowledge about which aspects are relevant to evaluate the difference. Integral probability metrics (IPMs, Müller (1997)) and f -divergences (Csiszár, 1964) are widely used discrepancies in machine learning. IPMs, such as the Wasserstein distance, maximum mean discrepancy (MMD) (Rao, 1982; Burbea & Rao, 1984; Gretton et al., 2012), are based on the idea that if two distributions are identical, any function should have the same expectation under both distributions. IPMs are used to define training objectives for generative models (Arjovsky et al., 2017), perform independence tests (Doran et al., 2014), robust optimization (Esfahani & Kuhn, 2018) among many other applications. f -divergences, such as the KL divergence and the Jensen Shannon divergence, are based on the idea that if two distributions are identical, they assign the same likelihood to every point. One can then define a discrepancy based on how different the likelihood ratio is from one. KL divergence underlies some of the most commonly used training objectives for both supervised and unsupervised machine learning algorithms, such as cross entropy loss.
We propose a third category of divergences called H-divergences that overlaps with but also extends the set of integral probability metrics or the set f -divergences. Intuitively, H-divergence compares two distributions in terms of the optimal loss for a certain decision task. This optimal loss corresponds to a generalized notion of entropy (DeGroot et al., 1962). Instead of measuring the best average code length of any encoding scheme (Shannon entropy), the generalized entropy uses arbitrary 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 q, we compare the generalized entropy of the mixture distribution (p + q)/2 and the generalized entropy of p and q individually. Intuitively, if p and q are different, it is more difficult to minimize expected loss under the mixture distribution (p+ q)/2, 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 q, and hence should have the same generalized entropy.
Our divergence strictly generalizes the maximum mean discrepancy family and the Jensen Shannon divergence, which can be obtained with specific choices of the loss function. We
illustrate this via the Venn diagram in Figure 1. Our formulation allows us to choose alternative losses 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 leverage recent progress in modeling high dimensional images.
We demonstrate the effectiveness of H-divergence in two sample tests, i.e. to decide whether two sets of samples come from the same distribution or not. A test based on a probability discrepancy declares two sets of samples different if their discrepancy exceeds some threshold. We use H-divergences based on generalized entropy defined by the log likelihood of offthe-shelf generative models. Compared to state-of-the-art tests based on MMD with deep kernels (Liu et al., 2020), tests based on the H-divergence achieve better test power (given identical type I error) on a large set of benchmarks.
More importantly, scientists and policy makers are often interested not only in if two distributions are different, but how two distributions are different and whether the differences affect decision making. Typical divergence measures (such as KL) or two sample tests only quantify if two distributions are different, while we show that H-divergence is a useful tool for quantifying how distributions are different with three application examples: studying the effect of climate change, feature selection, and sample quality evaluation. In each of these examples, we compare different aspects of the distributions by choosing specific decision loss functions. For example, climate change (Figure 3) might impact agriculture in a region but not energy production, or vice versa. By choosing suitable loss functions (related to agriculture, energy, etc) we can quantify and test if the change in climate distribution impact different economic activities.

heading: 2 Background

heading: 2.1 Probability Divergences
text: Let X denote a finite set or a finite dimensional vector space, and P(X ) denote the set of probability distributions on X that have a density. We consider the problem of defining a probability divergence between any two distributions in P(X ), where a probability divergence is any function D : P(X )× P(X )→ R that satisfies D(p‖q) ≥ 0, D(p‖p) = 0,∀p, q ∈ P(X ). We call the divergence D “strict” if D(p‖q) > 0 ∀p 6= q, and “non-strict“ otherwise. In this paper we consider both types of divergences.
Integral Probability Metrics Let F denote a set of functions X → R. An integral probability metric is defined as IPMF (p‖q) = supf∈F |Ep[f(X)]−Eq[f(X)]|. Several important divergences belong to integral probability metrics. Examples include the Wasserstein distance, where F 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 → R+ and is defined by
MMD2(p‖q) = Ep,pk(X,Y ) + Eq,qk(X,Y )− 2Ep,qk(X,Y )
MMD is an IPM where F is the unit norm functions in the reproducing kernel Hilbert space (RKHS) associated with the kernel k.
f-Divergences Given any convex continuous function f : R+ → R such that f(1) = 0, the f -Divergence is defined as (assuming densities exist) Df (p‖q) = Eq[f(p(X)/q(X))]. Examples include the KL divergence, where f : t 7→ t log t and the Jensen Shannon divergence, where f : t 7→ (t+ 1) log ( 2 t+1 ) + t log t.

heading: 2.2 H-Entropy
text: For any action space A and any loss function ` : X ×A → R, the H-entropy (DeGroot et al., 1962; DeGroot, 2005; Grünwald et al., 2004) is defined as
H`(p) = inf a∈A
Ep[`(X, a)]
In words, H-entropy is the Bayes optimal loss of a decision maker who must select some action a not for a particular x, but in expectation for a random x drawn from p(x). Hentropy generalizes several important notions of uncertainty. Examples include: Shannon Entropy, where A as the set of probabilities P(X ), and `(x, a) = − log a(x); Variance where A = X , and `(x, a) = ‖x − a‖22; Predictive V-entropy, where A ⊂ P(X ) is some subset of distributions, and `(x, a) = − log a(x) (Xu et al., 2020). A key property we will use is that H-entropy is concave (DeGroot et al., 1962).
Lemma 1. For any choice of ` : X ×A → R, H` is a concave function.
This Lemma can be proved by observing that inf is a concave function: it is always better to pick an optimal action for p and q separately rather than a single one for both.
H` ( αp+ (1− α)q ) = inf
a (αEp[`(X, a)] + (1− α)Eq[`(X, a)])
≥ α inf a Ep[`(X, a)] + (1− α) inf a Eq[`(X, a)] = αH`(p) + (1− α)H`(q)
This Lemma reflects why H` can be thought of as a measurement of entropy or uncertainty. If the distribution is more uncertain (e.g. a mixture of p and q, rather than p or q separately) then decisions made under higher uncertainty will suffer a higher loss.

heading: 3 Definition and Theoretical Properties

heading: 3.1 H-Jensen Shannon Divergence
text: As a warm up, we present a special case of our divergence.
Definition 1 (H-Jensen Shannon divergence).
DJS` (p, q) = H`
( p+ q
2
) − 1
2
( H`(p) +H`(q) ) (1)
DJS` is always non-negative because H-entropy is concave (Lemma 1), and clearly D JS ` (p, q) = 0 whenever p = q. Therefore, DJS` is a valid probability divergence. In particular, if we choose H` as the Shannon entropy, Definition 1 recovers the Jensen Shannon divergence. Other special loss function choices can recover definitions in (Burbea & Rao, 1982).

heading: 3.2 General H-divergence
text: In addition to the H-Jensen Shannon divergence, there are other functions based on the H-entropy that satisfy the requirements of a divergence. For example,
DMin` = H`
( p+ q
2
) −min(H`(p), H`(q)) (2)
is also a valid divergence (this will be proved later as a special case of Lemma 2). We can define a general set of divergences that includes the above two divergences with the following definition:
Definition 2 (H-divergence). For two distributions p, q on X , given any continuous function φ : R2 → R such that φ(θ, λ) > 0 whenever θ + λ > 0 and φ(0, 0) = 0, define
Dφ` (p‖q) = φ ( H` (p+ q 2 ) −H`(p), H` (p+ q 2 ) −H`(q) ) Intuitively H` ( p+q 2 ) −H`(p) and H` ( p+q 2 ) −H`(q) measure how much more difficult it is to minimize loss on the mixture distribution (p+ q)/2 than on p and q respectively. φ is a general class of functions that map these differences into a scalar divergence, while satisfying some desirable properties described in the next section.
The following proposition shows that the H-divergence generalizes the previous definitions (1) and (2). Therefore, any property of H-divergence is inherited by e.g. the H-Jensen Shannon divergence.
Proposition 1. If φ(θ, λ) = θ+λ2 then D φ ` (p, q) is the H-Jensen Shannon divergence in Eq.(1). If φ(θ, λ) = max(θ, λ) then Dφ` (p, q) is the H-Min divergence in Eq.(2).

heading: 3.3 Properties of the H-divergence
text: We first verify that Dφ` is indeed a (strict or non-strict) probability divergence. Lemma 2. For any choice of ` and for any choice of φ that satisfy Definition 2, Dφ` is non-negative and Dφ` (p, q) = 0 whenever p = q. Furthermore, D φ ` is symmetric whenever φ is symmetric.
Depending on the choice of `, H-divergence may or may not be strict (i.e. whenever p 6= q, D(p‖q) > 0). The following proposition characterizes conditions for a strict divergence. Proposition 2 (Strict Divergence). For any choice of φ the following are equivalent 1) ∀p 6= q, D`(p‖q) > 0. 2) The H-entropy H`(p) := infa Ep[`(X, a)] is strictly convex in p. 3) ∀p 6= q, arg infa Ep[`(X, a)] ∩ arg infa Eq[`(X, a)] = ∅.
In particular, this proposition can be used to characterize all strict H-divergences, because the set of all losses ` that induces strict H-entropy functions H` can be characterized by Fenchel duality (Duchi et al., 2018).
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.e. the optimal solutions for their respective H-entropy are different. This is shown in the following proposition (proof in Appendix A).
Proposition 3. Dφ` (p‖q) > 0 if and only if arg infa Ep[`(X, a)] ∩ arg infa Eq[`(X, a)] = ∅.
Intuitively, Dφ` only takes into account differences between distributions that lead to different optimal action choices. This property allows us to incorporate prior domain knowledge. By choosing A and ` we can specify which differences between distributions lead to different optimal actions, and which differences do not. For example, we can choose A as a set of generative models (e.g., mixture of Gaussians) and `(x, a) as the negative log likelihood of x under generative model a. If under two distributions we end up learning the same generative model (by maximizing log likelihood), the H-divergence between them is zero.

heading: 3.4 Relationship to MMD
text: An important special case of the H-divergence is the set of squared Maximum Mean Discrepencies (MMD), as shown by the following theorem:
Theorem 1. The set of H-Jensen Shannon Divergences is strictly larger than the MMD2 distances.
To prove this theorem, we show that for each choice of kernel k : X × X → R, there exists an action space A and loss ` such that the corresponding squared MMD distance and Hdivergence are the same (see proof in Appendix A). In particular, this equivalence can be
achieved by choosing A to be the RKHS H of k(·, ·), and `(x, a) = 4‖k(x, ·)−a‖2H. Inclusion is strict because the Jensen Shannon divergence is a H-Jensen Shannon Divergence but not a squared MMD distance.

heading: 3.5 Estimation and Convergence
text: Many machine learning tasks can be reduced to the problem of estimating the divergence between two distributions given samples. Specifically, suppose we are provided with a set of m i.i.d. samples p̂m = (x1, · · · , xm) drawn from distribution p and q̂m = (x′1, · · · , x′m) drawn from distribution q, and would like to obtain an estimate of Dφ` (p‖q) based on the samples. Here, p̂m and q̂m denote empirical distributions drawn from p and q respectively. In this section we propose an empirical estimator for the H-divergence and show that it has favorable convergence properties.
Let D̂φ` (p̂m‖q̂m) be the empirical (random) estimator for D φ ` (p‖q) defined by
D̂φ` (p̂m‖q̂m) =φ ( inf a 1 m m∑ i=1 `(x′′i , a)− inf a 1 m m∑ i=1 `(xi, a), inf a 1 m m∑ i=1 `(x′′i , a)− inf a 1 m m∑ i=1 `(x′i, a) )
where x′′i = xibi + x ′ i(1− bi) and bi are i.i.d uniformly sampled from {0, 1}, so that x′′i is a sample from the mixture distribution (p+ q)/2 of size m.
Using x′′i as defined above is crucial for the convergence properties we will prove in Theorem 2. It might be tempting to replace the term 1m ∑m i=1 `(x ′′ i , a) with 1 2m ∑m i=1(`(xi, a) + `(x′i, a)) to use all the available samples. However, optimizing the action based on a finite set of samples (instead of in expectation) is prone to overfitting, and introduces bias. Intuitively, using m samples (x′′i ) ensures the bias for the mixture is comparable to that of p and q. Without this, Theorem 2 is no longer true, and empirical performance also degrades.
Before presenting the convergence results, we first must define several assumptions that make convergence possible. In particular, we are going to assume that the loss function ` is C-bounded, i.e. there exists some C such that 0 ≤ `(x, a) ≤ C, ∀a, x. This assumption seemingly exclude important special cases such as the Jensen-Shannon divergence (which is associated with the unbounded log loss). However, we show in the appendix that the JensenShannon divergence cannot be consistently estimated in general, hence correctly excluded by our theorem. One practical solution is to clip the log likelihood, which is the approach adopted in (Song & Ermon, 2019) for improved divergence estimation (for a similar KL divergence estimation problem).
In addition, we assume that φ is 1-Lipschitz under the ∞-norm, i.e. |φ(θ + dθ, λ + dλ) − φ(θ, λ)| ≤ max(dθ, dλ),∀θ, λ, dθ, dλ ∈ R . Both φ(θ, λ) = θ+λ2 and φ(θ, λ) = max{θ+λ} are 1-Lipschitz under the∞-norm. This is a mild assumption because if φ is not 1-Lipschitz we can rescale φ to make it 1-Lipschitz. Finally, define the Radamacher complexity
Rpm(`) = EXi∼p, i∼Uniform({−1,1}) [ sup a∈A 1 m m∑ i=1 i`(Xi, a) ]
We define Rqm(`) analogously. Based on these assumptions and definitions we can bound the difference between D̂φ` (p̂m‖q̂m) and D φ ` (p‖q). Theorem 2. If ` is C-bounded, and φ is 1-Lipschitz under the ∞-norm, for any choice of distribution p, q ∈ P(X ) and t > 0 we have
1. Pr[D̂φ` (p̂m‖q̂m) ≥ t] ≤ 4e − t2m 2C2 if p = q.
2. Pr [∣∣∣D̂φ` (p̂m‖q̂m)−Dφ` (p‖q)∣∣∣ ≥ 4 max(Rpm(`),Rqm(`)) + t] ≤ 4e− t2m2C2
Corollary 1. √ Var[D̂φ` (p̂m‖q̂m)] ≤ 4 max(Rpm(`),Rqm(`)) + √ 2C2/m
For proof see Appendix A. Note that when p = q, the convergence of D̂φ` (p̂m‖q̂m) does not depend on the Radamacher complexity of `, and converges to 0 very quickly. When p 6= q the estimator D̂φ` (p̂m‖q̂m) is still consistent (under regularity assumptions) Corollary 2. [Consistency] Under the condition of Theorem 2, if additionally either 1. A is a finite set 2. A is a bounded subset of Rd for some d ∈ N and ` is Lipschitz w.r.t. a, then almost surely limm→∞ D̂ φ ` (p̂m‖q̂m) = D φ ` (p‖q).
For both cases in Corollary 2 the Radamacher complexity Rpm(`) goes to zero (as sample size m → ∞) at a rate of O(1/ √ m). In other words we can conclude that the estimation error in Theorem 2 is bounded by O(1/ √ m) and the variance of the estimator is also bounded by O(1/ √ m) when the same size m→∞.

heading: 4 Experiment: Two Sample Test
text: The first application is to design more powerful two sample tests. We aim to show that H-divergence allow us to leverage inductive biases for each data type (e.g. image, bio, text) by choosing suitable actions A and loss `, which leads to improved test power. 1

heading: 4.1 Two Sample Test
text: For the task of two sample test, we would like to decide if two sets of samples are drawn from the same distribution or not. Specifically, given two sets of samples p̂m := (x1, · · · , xm) i.i.d.∼ p and q̂m := (x ′ 1, · · · , x′m)
i.i.d.∼ q we would like to decide if p = q. Typical approaches estimate a divergence D̂(p̂m‖q̂m) and output p 6= q if the divergence exceeds some threshold. There are two types of errors: Type I error happens when the algorithm incorrectly outputs p 6= q; the probability of type I errors is called the significance level. Type II error happens when the algorithm incorrectly outputs p = q; the probability of not making a Type II error is called the test power (higher is better). Note that both the significance level and the test power are relative to distributions p and q.
We follow the typical setup where we guarantee a certain 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 a permutation test, in addition to the original set of samples p̂m and q̂m, we also uniformly randomly swap elements between p̂m and q̂m, and sample multiple randomly swapped datasets (p̂1m, q̂ 1 m), (p̂ 2 m, q̂ 2 m), · · · . The testing algorithm outputs p 6= q if D̂(p̂m‖q̂m) is in the top α-quantile among {D̂(p̂1m‖q̂1m), D̂(p̂2m‖q̂2m), · · · }. Permutation test guarantees the significance level (i.e. low Type I error) because if p = q then swapping elements between p̂m and q̂m should not change its distribution, so each pair (p̂m, q̂m), (p̂ 1 m, q̂ 1 m), · · · should have the same distribution. Therefore, D̂(p̂m‖q̂m) happens to be in the top α-quantile with at most α probability. Note that the significance level guarantee does not rely on accurate estimation of H-divergence in Theorem 2 (accurate H-divergence estimation is still important because the test power does depends on it).
When the choice of D` is not a strict divergence (See Proposition 2) we may falsely conclude p = q (D(p‖q) = 0) when in reality p 6= q. This is true but inconsequential in finite data scenarios. With finite data, it is generally impossible to guarantee the test power (i.e. bounding the probability of concluding p = q when in reality p 6= q for any p, q) and prior literature do not provide such guarantees. Hence our guarantee is no weaker than prior two sample test literature.

heading: 4.2 Experiment Setup
text: Baselines We compare our proposed approach with six other divergences. All methods are based on the permutation test explained in Section 4.1. MMD-D (Liu et al., 2020) measures the MMD distance with a deep kernel, while MMD-O (Gretton et al., 2012) measures the MMD distance with a Gaussian kernel. Mean embedding (ME) and smoothed characteristic
1The code to reproduce our experiments can be found here.
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 a set of optimized frequencies. C2STS-S & C2ST-L (Lopez-Paz & Oquab, 2017; Cheng & Cloninger, 2019) use a classifier’s accuracy distinguishing between the two distributions.
Comparison Metrics and Setup All methods have the same significance level (which is provably equal to α = 0.05 because of the permutation test), therefore we only consider the test power. We follow Liu et al. (2020) and consider four datasets: Blob (Liu et al., 2020), HDGM (Liu et al., 2020), HIGGS (Adam-Bourdarios et al., 2014) and MNIST (LeCun & Cortes, 2010). Our method and all the baseline methods have hyper-parameters. To ensure fair comparison, we follow the same evaluation setup as (Liu et al., 2020) for all methods. We split each dataset into two equal partitions: a training set to tune hyper-parameters, and a validation set to compute the final test output. Implementation Details We choose φ(θ, λ) = ( θs+λs
2
)1/s for s > 1 (which includes the
H-Jensen Shannon divergence when s = 1 and the H-Min divergence when s = ∞). We define l(x, a) as the negative log likelihood of x under distribution a, where a is in a certain model family A. We experiment with mixture of Gaussian distributions, Parzen density estimtor and Variational Autoencoder (Kingma & Welling, 2013). Our hyper-parameters consist of the best parameter s and also the best generative model family. Choosing these hyperparameters might seem cumbersome, but compared to the second best baseline (MMD-D which chooses thousands of deep kernel parameters), we have much fewer hyper-parameters.
We use α = 0.05 in all two-sample test experiments. Each permutation test uses 100 permutations, and we run each test 100 times to compute the test power (i.e. the percent of times it correctly outputs p 6= q). Finally we plot and report the performance standard deviation by repeating the entire experiment 10 times.

heading: 4.3 Experiment Results
text: The average test powers are reported in Figure 4, Figure 2, Table 1 and Table 3. Our approach achieves superior test power across the board. Notably on Higgs we achieve the same test power with 2x fewer samples than the second best test, and on MNIST we can achieve perfect test power even on the smallest sample size evaluated in (Liu et al., 2020).
Following (Liu et al., 2020) we also evaluate the test power as the dimension of the problem increases (Figure 2). Our test power decreases gracefully as the dimension of the problem increases. We hypothesize 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; we use commonly used generative models (in modern literature) for each data type (e.g. KDE for low dimensional physics/bio data, VAE for simple images).

heading: 1000 0.120±0.007 0.095±0.007 0.082±0.015 0.097±0.014 0.132±0.005 0.113±0.013 0.240±0.020

heading: 2000 0.165±0.019 0.130±0.019 0.183±0.026 0.232±0.032 0.291±0.017 0.304±0.012 0.380±0.040

heading: 3000 0.197±0.012 0.142±0.025 0.257±0.049 0.399±0.058 0.376±0.022 0.403±0.050 0.685±0.015

heading: 5000 0.410±0.041 0.261±0.044 0.592±0.037 0.447±0.045 0.659±0.018 0.699±0.047 0.930±0.010

heading: 8000 0.691±0.067 0.467±0.038 0.892±0.029 0.878±0.020 0.923±0.013 0.952±0.024 1.000±0.000

heading: 10000 0.786±0.041 0.603±0.066 0.974±0.007 0.985±0.005 1.000±0.000 1.000±0.000 1.000±0.000

heading: 5 Experiment: Decision Dependent Discrepancy Measurement

heading: 5.1 Assessing Climate Change
text: As an illustrative example of how H-divergence can facilitate decision making, we use climate data and study how climate change affects decision making through the lens of H-divergence. Scientists and policy makers are often interested in how climate change disparately affect different geographical locations. Existing methods (Preston et al., 2011) focus on one aspect of climate change (such as the expected economic loss (Burke et al., 2018)) using tailordesigned analysis, while H-divergence provides a general tool for hypothesis testing and visualization for different aspects of climate change. In our example, we choose suitable loss functions to quantitatively measure aspects of climate change that are relevant to decision making in agriculture and renewable energy production.2
Setup We use the NOAA database which contains daily weather from thousands of weather stations at different geographical locations. For each location, we summarize the weather sequence of each year into a few summary statistics (average yearly temperature, humidity, wind speed and rainy days). We are interested in assessing changes in weather over this period at each location, from the perspective of agriculture and renewable energy activities. 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 at each location (e.g. wheat/barley/rice), and `(x, a) denote the loss of planting crop a if the yearly weather is x. We estimate the function ` by matching geographical locations in the FAO crop yield dataset (FAOSTAT et al., 2006) to weather stations in the NOAA database, and learn a function to predict crop yield from weather data with kernel ridge regression.
2Designing loss functions ` that capture the effect of climate on human activities is a well studied topic in economics, and beyond the scope of this work. Our results should be taken as an illustrative example of how domain experts might use H-divergence with more realistic loss functions.
The H-divergence has a 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 mina∈A E(p+q)/2[`(X, a)]); (2) plant the optimal crops for 1981-1999 and for 2000-2019 respectively. H 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. For each geographical location we can compute the H-divergence DJS` for the estimated ` (plotted in Figure 3 left).
Example: Energy production Changes in weather also affect electricity generation, since climate change could affect the amount of wind/solar energy available. Let A denote the number of wind/solar/fossil fuel power plants built, and `(x, a) denote the loss (negative utility) when the weather is x. We obtain the function ` using empirical formulas for energy production (Npower, 2012). The H-divergence for this loss function is shown in Figure 3 (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. While this is only an illustrative example, comparing the two maps we see that regions and industries are affected by climate change in different ways – H divergence provides a quantitative framework for this kind of assessments.

heading: 5.2 Feature Selection
text: In a feature selection task, we wish to know which input features are most predictive of the label. Feature selection provides information on which features have the biggest influence on the label, and can be used in scientific discovery (Jović et al., 2015; Zhang et al., 2015).
Off-the-shelf feature selection algorithms often do not take into account problem specific requirements. For example, denote the input features as X1, · · · , XK and label as Y , the mutual information feature selection algorithms estimate the Shannon mutual information I(Xi, Y ) := KL(p(Xi, Y )‖p(Xi)p(Y )) and select features with largest mutual information. However, scientists and policies makers often need fine-grained control to answer their specific scientific or policy questions. For example, social scientists might want to know which features are more important for high-income as compared to low-income groups (e.g. to understand potential glass ceilings).
With H-Divergence we can select features with large Dφ` (p(Xi, Y )‖p(Xi)p(Y )) (i.e. the optimal action is different under the joint p(Xi, Y ) and the product of marginals p(Xi)p(Y )). By choosing different loss functions ` we can get different feature selection results, each reflecting important features for that decision problem. For example, in Table 2 we show the features selected for the UCI income prediction dataset (Blake, 1998). For this dataset, we choose A as the set of logistic regression functions, l(x, a) as the cross entropy loss for regression function a on the sample x and φ(θ, λ) = max(θ, λ). If we want to focus on high income groups, we can assign a higher weight to the loss of high income samples, and vice versa. We observe that gender/race is more predictive of income for high-income groups, while relationship or marital status is more predictive of income for lower-income groups. This can help us identify potential inequality or suggest further investigation into the cause of low income and poverty. For example, our results suggest a connection between family and relationship status and poverty, and a connection between gender/race and high income. These connections merit further investigation into the cause and policy remedy.

heading: A Proofs
text: Lemma 2. For any choice of ` and for any choice of φ that satisfy Definition 2, Dφ` is non-negative and D φ ` (p, q) = 0 whenever p = q. Furthermore, Dφ` is symmetric whenever φ is symmetric.
Proof of Lemma 2. For any choice of p, q by the concavity of the H-entropy in Lemma 1 we have
H`
( p+ q
2
) −H`(p) ≥ 1
2 (H`(q)−H`(p))
H`
( p+ q
2
) −H`(q) ≥ 1
2 (H`(p)−H`(q))
Therefore by summing the two inequalities we have( H` ( p+ q
2
) −H`(p) ) + ( H` ( p+ q
2
) −H`(q) ) ≥ 0
By the requirement on φ we know that Dφ` (p‖q) ≥ 0. In addition when p = q since (p + q)/2 = p = q we have Dφ` (p‖q) = φ(0, 0) = 0. To show it is symmetric, note that
Dφ` (p‖q) = φ ( H` ( p+ q
2
) −H`(p), H` ( p+ q
2
) −H`(q) ) = φ ( H` ( p+ q
2
) −H`(q), H` ( p+ q
2
) −H`(p) ) = Dφ` (q‖p)
whenever φ is symmetric.
Proposition 3. Dφ` (p‖q) > 0 if and only if arg infa Ep[`(X, a)] ∩ arg infa Eq[`(X, a)] = ∅.
Proof of Proposition 3. Denote A∗p = arg infa Ep[`(X, a)] and A∗q = arg infa Eq[`(X, a)]. Also compute
H`
( p+ q
2
) = inf
a E p+q 2 [`(X, a)] = inf a
( 1
2 Ep[`(X, a)] +
1 2 Eq[`(X, a)]
) (3)
If A∗p∩A∗q = ∅, for any action a′ such that Ep[`(X, a′)] = H`(p), we must have a′ ∈ A∗p so a′ 6∈ A∗q and Eq[`(X, a′)] > H`(q). Similar if we choose a
′′ such that Eq[`(X, a′′)] = H`(q) we have similarly have Ep[`(X, a′′)] > H`(p). In other words, for any choice of action a ∈ A either a /∈ A∗p and Ep[l(X, a)] > H`(p) or a ∈ A∗p and Eq[l(X, a)] > H`(q). Therefore
inf a
( 1
2 Ep[`(X, a)] +
1 2 Eq[`(X, a)]
) > 1
2 H`(p) +
1 2 H`(q) (4)
Combining Eq.(3) and Eq.(4) we have
1
2
( H` ( p+ q
2
) −H`(p) ) + 1
2
( H` ( p+ q
2
) −H`(q) ) > 0
By Definition 2 this implies (for any choice of φ that satisfies the requirements in Definition 2) that Dφ` (p‖q) > 0. To prove the converse simply obverse that if A∗p ∩A∗q 6= φ, let a∗ ∈ A∗p ∩A∗q we have a∗ = arg infa∈A E p+q
2 [l(X, a)].
This implies that
2H`
( p+ q
2
) −H`(q)−H`(p) = 2E p+q
2 [l(X, a∗)]− Eq[l(X, a∗)]− Ep[l(X, a∗)] = 0
By Definition 2 we can conclude that Dφ` (p‖q) = 0.
Theorem 1. The set of H-Jensen Shannon Divergences is strictly larger than the MMD2 distances.
Proof of Theorem 1. Let k(x, y) be some kernel on an input space X , and let H be the RKHS induced by the kernel. The (squared) MMD distance is defined by
MMD2(p, q) = EX∼p,Y∼pk(X,Y ) + EX∼q,Y∼qk(X,Y )− 2EX∼p,Y∼qk(X,Y )
which we write more compactly as MMD2(p, q) = Ep,pk(X,Y ) + Eq,qk(X,Y )− 2Ep,qk(X,Y ).
Define φ(x, y) = ‖k(x, ·)− k(y, ·)‖2H. We can rewrite this in the following form:
MMD2(p, q) = Ep,qφ(X,Y )− 1
2 Ep,pφ(X,Y )−
1 2 Eq,qφ(X,Y ) (5)
= Ep,q‖k(X, ·)‖2H + ‖k(Y, ·)‖2H − 2k(X,Y )− 1
2 Ep,p‖k(X, ·)‖2H + ‖k(Y, ·)‖2H − 2k(X,Y )
− 1 2 Eq,q‖k(X, ·)‖2H + ‖k(Y, ·)‖2H − 2k(X,Y ) = Ep,pk(X,Y ) + Eq,qk(X,Y )− 2Ep,qk(X,Y )
We also observe an algebraic relationship for any function f(x, y) such that f(x, y) = f(y, x) for all x, y:
E p+q 2 , p+q 2 f(X,Y ) =
1 4 Ep,pf(X,Y ) + 1 4 Ep,qf(X,Y ) + 1 4 Eq,pf(X,Y ) + 1 4 Eq,qf(X,Y )
= 1
4 Ep,pf(X,Y ) +
1 4 Ep,qf(X,Y ) + 1 4 Eq,pf(Y,X) + 1 4 Eq,qf(X,Y )
= 1
4 Ep,pf(X,Y ) +
1 4 Eq,qf(X,Y ) + 1 2 Ep,qf(X,Y ) (6)
Furthermore, we have that
Ep,p‖k(X, ·)− k(Y, ·)‖2H = 2Ep‖k(X, ·)− Epk(Y, ·)‖2H (7)
Based on the above, noting that φ(x, y) = φ(y, x), we can derive
MMD2(p, q) = Ep,q‖k(X, ·)− k(Y, ·)‖2H − 1
2 Ep,p‖k(X, ·)− k(Y, ·)‖2H −
1 2 Eq,q‖k(X, ·)− k(Y, ·)‖2H Eq (5)
= 2E p+q 2 , p+q 2 ‖k(X, ·)− k(Y, ·)‖2H − Ep,p‖k(X, ·)− k(Y, ·)‖2H − Eq,q‖k(X, ·)− k(Y, ·)‖2H Eq (6) = 4E p+q 2 ‖k(X, ·)− E p+q 2 k(Y, ·)‖2H − 2Ep‖k(X, ·)− Epk(Y, ·)‖2H − 2Eq‖k(X, ·)− Eqk(Y, ·)‖2H Eq (7)
= 4 inf a∈H E p+q 2 ‖k(X, ·)− a‖2H − 2 inf a∈H Ep‖k(X, ·)− a‖2H − 2 inf a∈H Eq‖k(X, ·)− a‖2H. mean def.
Therefore we can define a loss ` : X ×H → R where
`(x, a) = 4‖k(x, ·)− a‖2H Under the new notation we have
MMD2(p, q) = inf a∈H E p+q 2 l(X, a)− 1 2 ( inf a∈H Epl(X, a) + inf a∈H Eql(X, a) )
= H`
( p+ q
2
) − 1
2 (H`(p) +H`(q)) = D
JS ` (p‖q)
Conversely we want to show that not every H-Jensen Shannon divergence is a MMD. For example, take H` to be the Shannon entropy, then the corresponding DJS` is the Jensen-Shannon divergence, which is not a MMD. This is because the JS divergence is a type of f -divergence, and the only f -divergence that is also an IPM is total variation distance Sriperumbudur et al. (2009). 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 ∞-norm, for any choice of distribution p, q ∈ P(X ) and t > 0 we have
1. Pr[D̂φ` (p̂m‖q̂m) ≥ t] ≤ 4e − t2m 2C2 if p = q. 2. Pr [∣∣∣D̂φ` (p̂m‖q̂m)−Dφ` (p‖q)∣∣∣ ≥ 4 max(Rpm(`),Rqm(`)) + t] ≤ 4e− t2m2C2
Proof of Theorem 2. Let p̂m be a sequence of n samples (x1, · · · , xm) drawn from p, and q̂m a sequence of n samples (x′1, · · · , x′m) drawn from q. Let r̂m the sub-sampling mixture (x′′1 , · · · , x′′m) defined in Section 3.5 (i.e. x′′i = xibi + x ′ i(1 − bi) where bi is uniformly sampled from {0, 1}). We also overload the notation H` by defining H`(p̂m) = infa∈A 1 m ∑m i=1 l(xi, a), and define H`(q̂m), H`(r̂m) similarly.
Before proving this theorem we need the following Lemmas
Lemma 3. Under the assumptions of Theorem 2
Pr [H`(p̂m)− E[H`(p̂m)] ≥ t] ≤ e− 2t2m C2
Pr [H`(p̂m)− E[H`(p̂m)] ≤ −t] ≤ e− 2t2m C2
Lemma 4. Under the assumptions of Theorem 2
Pr [|H`(p)−H`(p̂m)| ≥ 2Rm(`) + t] ≤ e− 2t2m C2
To prove the first statement of the Theorem, when p = q we can denote µ = E[H`(p̂m)] = E[H`(q̂m)] = E[H`(r̂m)], and we have
Pr [ D̂φ` (p̂m‖q̂m) ≥ t ] = Pr[φ(H`(r̂m)−H`(p̂m), H`(r̂m)−H`(q̂m)) ≥ t] Def 2 ≤ Pr [max(H`(r̂m)−H`(p̂m), H`(r̂m)−H`(q̂m)) ≥ t] φ 1-Lipschitz ≤ Pr [H`(r̂m)−H`(p̂m) ≥ t] + Pr [H`(r̂m)−H`(q̂m) ≥ t] Union bound ≤ Pr [H`(p̂m)− µ ≤ −t/2] + 2 Pr [H`(r̂m)− µ ≥ t/2] + Pr [H`(q̂m)− µ ≤ −t/2] Union bound
≤ 4e− t2 2C2/m Lemma 3
The third inequality is because ifH`(r̂m)−H`(p̂m) ≥ t then it must be eitherH`(p̂m)−µ ≤ −t/2 orH`(r̂m)−µ ≥ t/2. Similarly if H`(r̂m)−H`(q̂m) ≥ t then it must be either H`(q̂m)− µ ≤ −t/2 and H`(r̂m)− µ ≥ t/2. To prove the second statement of the Theorem, we observe that
|D̂φ` (pm‖qm)−D φ ` (p‖q)| = ∣∣∣φ (H`(r̂m)−H`(p̂m), H`(r̂m)−H`(q̂m))− φ(H` (p+ q
2
) −H`(p), H` (p+ q 2 ) −H`(q) )∣∣∣ Def 2 ≤ max (∣∣∣H`(r̂m)−H`(p̂m)−H` (p+ q 2 ) +H`(p) ∣∣∣ , ∣∣∣H`(r̂m)−H`(q̂m)−H` (p+ q 2 ) +H`(q)
∣∣∣) φ 1-Lip ≤ max (∣∣∣H`(r̂m)−H` (p+ q 2 )∣∣∣ + |H`(p̂m)−H`(p)| , ∣∣∣H`(r̂m)−H` (p+ q 2
)∣∣∣ + |H`(q̂m)−H`(q)|) Jensen Therefore, the event |D̂φ` (pm‖qm)−D φ ` (p‖q)| ≥ 4 max(Rpm(`),Rqm(`))+t happens only if at least one of the following events happen∣∣∣∣H`(r̂m)−H`(p+ q2 )∣∣∣∣ ≥ Rpm(`) +Rqm(`) + t/2 ≥ 2R(p+q)/2m (`) + t/2 R convex
|H`(p̂m)−H`(p)| ≥ 2Rm(`) + t/2 |H`(q̂m)−H`(q)| ≥ 2Rm(`) + t/2
Based on Lemma 4 each of these events only happen with probability at most e− t2m 2C2 . Therefore we can conclude by union bound that
Pr[|D̂φ` (p‖q)−D φ ` (p‖q)| ≥ 4 max(R p m(`),Rqm(`)) + t] ≤ 4e
− t2m 2C2
Finally we prove the two Lemmas used in the theorem. Lemma 4 is a standard result in the Radamacher complexity literature. For a proof, see e.g. Section 26.1 in (Shalev-Shwartz & Ben-David, 2014). Lemma 3 can also be proved by standard techniques. We provide the proof here.
Proof of Lemma 3. Consider two sets of samples x1, · · · , xj , · · · , xm and x′1, · · · , x′j , · · · , x′m where xi = x′i for every index i = 1, · · · ,m except index j.∣∣∣∣∣infa 1m∑
i
`(xi, a)− inf a
1
m ∑ i `(x′i, a) ∣∣∣∣∣ ≤ supa ∣∣∣∣∣ 1m∑ i `(xi, a)− 1 m ∑ i `(x′i, a) ∣∣∣∣∣ = 1
m sup a ∣∣`(xj , a)− `(x′j , a)∣∣ ≤ Cm Then we can conclude by Mcdiarmid inequality that
Pr [ inf a 1 m ∑ i `(Xi, a)− E [ inf a 1 m ∑ i `(Xi, a) ] ≥ t ] ≤ e− 2t2 C2/m = e− 2t2m C2
Corollary 1. √ Var[D̂φ` (p̂m‖q̂m)] ≤ 4 max(Rpm(`),Rqm(`)) + √ 2C2/m
Proof of Corollary 1. For notation convenience denote B = 4 max(Rpm(`),Rqm(`))
Var[D̂φ` (p̂m‖q̂m)] = E [( D̂φ` (p̂m‖q̂m)−D φ ` (p‖q) )2] =
∫ ∞ t=0 Pr [( D̂φ` (p̂m‖q̂m)−D φ ` (p‖q) )2 ≥ t ] dt
= ∫ ∞ t=0 Pr [∣∣∣D̂φ` (p̂m‖q̂m)−Dφ` (p‖q)∣∣∣ ≥ √t] dt
= ∫ ∞ s=0 Pr [∣∣∣D̂φ` (p̂m‖q̂m)−Dφ` (p‖q)∣∣∣ ≥ s] 2sds s = √t
≤ ∫ B s=0 2sds+ ∫ ∞ s=0 Pr [∣∣∣D̂φ` (p̂m‖q̂m)−Dφ` (p‖q)∣∣∣ ≥ B + s] 2(B + s)ds
≤ B2 + ∫ ∞ s=0 2(B + s)e− s2m 2C2 ds
≤ B2 + ∫ ∞ t=0 2(B + t √ 2C2 m )e−t 2 √ 2C2 m dt t = s √ m 2C2
= B2 + 2B
√ 2C2
m
∫ e−t 2 dt+ 4C2
m
∫ te−t 2 dt
= B2 +B
√ 2πC2
m +
2C2
m ≤ (B +
√ 2C2/m)2
Corollary 2. [Consistency] Under the condition of Theorem 2, if additionally either 1. A is a finite set 2. A is a bounded subset of Rd for some d ∈ N and ` is Lipschitz w.r.t. a, then almost surely limm→∞ D̂φ` (p̂m‖q̂m) = D φ ` (p‖q).
Proof of Corollary 2. We can prove the consistency results from Theorem 2 by observing that the expected Radamacher complexity goes to 0 when m→∞. The first statement is a simple consequence of Massart’s Lemma, (e.g. see Eq.(8.44) in (Ma, 2021)). In particular, because A is finite we have
Rpm(`) ≤ √ 2 log |A|/m→m→∞ 0
To prove the second statement, first observe that because A is bounded, there must exist some r ∈ R such that A ⊂ Br := {a, ‖a‖2 ≤ r}. In addition, without loss of generality we can assume that there exists L ∈ R such that ∀x ∈ X and a, a′ ∈ A
|`(x, a)− `(x, a′)| ≤ L‖a− a′‖2 There is no loss of generality because in finite dimensions all norms are equivalent, so if f is Lipschitz under any norm, then ` is Lipschitz under the 2-norm. We can apply the results on Radamacher complexity for smoothly parameterized class proved in (Bartlett, 2013), and conclude that limm→∞Rpm(`) = 0.

heading: B Additional Experimental Results
text: B.1 Blob dataset
B.2 Evaluating Sample Quality
The gold standard for evaluating image generative models requires human decision, which is nevertheless expensive. Several surrogate measurements are commonly used, such as the Frechet Inception Distance (FID) (Heusel et al., 2017) or the inception score. Here by formulating such evaluation as an estimation of the discrepancy between the generated and the real images, we can quantify the quality of image samples by calculating the corresponding H-Divergences.
We choose A as the set of Gaussian mixture distributions on the inception feature space, l(x, a) as the negative log likelihood of x under distribution a and φ(θ, λ) = max(θ, λ). To evaluate the performance, we use the same setup as (Heusel et al., 2017), where we add corruption from (Hendrycks & Dietterich, 2019) to a set of images. Intuitively, adding more corruption degrades the sample quality, so a good measurement of sample quality should assign a lower quality score (higher divergence from clean images). 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 on some perturbations (such as “snow”), where the FID fails to be monotonically increasing, but our method is still monotonic, better aligning with human intuition.

heading: 200 0.414±0.050 0.107±0.018 0.193±0.037 0.234±0.031 0.188±0.010 0.555±0.044 1.000±0.000

heading: 400 0.921±0.032 0.152±0.021 0.646±0.039 0.706±0.047 0.363±0.017 0.996±0.004 1.000±0.000

heading: 600 1.000±0.000 0.294±0.008 1.000±0.000 0.977±0.012 0.619±0.021 1.000±0.000 1.000±0.000

heading: 800 1.000±0.000 0.317±0.017 1.000±0.000 1.000±0.000 0.797±0.015 1.000±0.000 1.000±0.000

heading: 1000 1.000±0.000 0.346±0.019 1.000±0.000 1.000±0.000 0.894±0.016 1.000±0.000 1.000±0.000

heading: C Additional Theory and Experiment Details
text: C.1 Connection to Optimal Transport
We first show that H-divergence can also have a transportation interpretation. For all the intuitive interpretations we avoid technical difficulty by assuming X is a finite set, even though all the formulas are applicable when X has infinite cardinality.
Setup Choose A = X , and let l(x, a) be a symmetric function (l(x, a) = l(a, x)) that denotes the cost of transporting a unit of goods from x to a. When we say that a unit of goods is located according to p, we mean that there is 1 unit of goods dispersed in X locations, where p(x) is the amount of goods at location x.
Optimal Transport Distance The optimal transport distance is defined by
O`(p, q) = inf rXY ,rX=pX ,rY =qY ErXY [l(X,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 to 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
H`(p) = inf a Ep[`(X, a)] a∗ = arg inf a∈X Ep[`(X, a)]
Suppose we want to move goods located according to p to a storage location (for example, we want to collect all the mail in a city to a 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 2H` ( p+q 2 ) measures the minimum cost to transport both goods located according to p and goods located according to q to the same storage location. The H-divergence
2DJS` (p‖q) := 2H` ( p+ q
2
) − (H`(q) +H`(p))
measures the reduction of transportation cost with two storage locations (one for p and one for q) 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 4. If ` satisfies the triangle inequality ∀x, y, z ∈ X , l(x, y)+ l(y, z) ≥ l(x, z) then DJS` (p‖q) ≤ 12O(p, q)
Proof of Proposition 4. Let a∗q = arg inf Eq[l(X, a)] then we have
2H`
( p+ q
2
) = inf
a (Ep[`(X, a)] + Eq[`(X, a)]) ≤ Ep[`(X, a∗q)] + Eq[`(X, a∗q)]
≤ inf rXY ,rX=pX ,rY =qY ErXY [`(X, a∗q)] + Eq[`(X, a∗q)] ≤ inf rXY ,rX=pX ,rY =qY ErXY [`(X,Y ) + `(Y, a∗q)] + Eq[`(X, a∗q)]
= O`(p, q) + 2H`(q)
Intuitively, to move goods located according to p and goods located according to q to some storage location, one option is to first transport all goods from p to q (so that the goods at location x will be 2q(x)), then move the goods located according to 2q to the optimal storage location. Similarly we have
2H`
( p+ q
2
) ≤ O(q, p) + 2H`(p)
which combined we have
2DJS` (p‖q) = 2H` ( p+ q
2
) − (H`(q) +H`(p)) ≤ O(p, q)
C.2 Impossibility of Jensen-Shannon Divergence Estimation
Suppose we have a consistent estimator for the Jenson-Shannon divergence, i.e. a function ĴS such that for any pair of distribution p, q and given N i.i.d. samples pN ∼ p and qN ∼ q we have limN→∞ ĴS(pN‖qN ) = ĴS(p‖q), then we prove a contradiction by the probabilistic method.
Let p be a standard Gaussian distribution, let QM be a uniform distribution on a set of M i.i.d. samples from p (hence QM is itself a random variable that depends on the i.i.d. samples). Let Q∗ be the limit of QM when M →∞ (i.e. it is the uniform distribution on an infinite set of samples). Let q∗ denote a value that Q∗ can take. Because q∗ is always supported on countably many points, hence JS(p‖q∗) = 1. Note that for any N the following two sampling process leads to identical distribution on pN , qN :
pN ∼ p, qN ∼ p Q∗ ∼ p, pN ∼ p, qN ∼ Q∗
Hence, the expectation of any function (including ĴS) is also identical. EQ∗∼p [ EpN∼p,qN∼Q∗ [ĴS(pN , qN )] ] = EpN∼p,qN∼p[ĴS(pN , qN )]
Hence the limit when N →∞ must be identical lim N→∞ EQ∗∼p [ EpN∼p,qN∼Q∗ [ĴS(pN , qN )] ] = lim N→∞ EpN∼p,qN∼p[ĴS(pN , qN )]
Because the Jenson Shannon divergence is always bounded, any consistent estimator must also be bounded for sufficiently large N . By the dominated convergence theorem we can exchange the expectation and the limit.
EQ∗∼p [
lim N→∞
EpN∼p,qN∼Q∗ [ĴS(pN , qN )] ]
= lim N→∞ EpN∼p,qN∼p[ĴS(pN , qN )]
By the probabilistic method (i.e. for any function f if EQ∗∼p[f(Q∗)] = 0 there must exist some q∗ such that f(q∗) ≤ 0) there must exist some q∗ such that
lim N→∞ EpN∼p,qN∼q∗ [ĴS(pN , qN )] ≤ lim N→∞ EpN∼p,qN∼p[ĴS(pN , qN )] = 0 6= JS(p‖q∗) = 1
Therefore ĴS cannot be consistent.
C.3 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 x1990 is a 4 dimensional vector where each dimension correspond to one of the summary statistics above.
Let p denote the uniform distribution over {x1981, · · · , x1999} and q denote the uniform distribution over {x2000, · · · , x2019}. For example Ep[`(X, a)] denote the expected loss of action a for a 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 to measure the difference between two time periods 1981-1999 vs. 2000-2019, we choose the action space A to be a 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 we choose the action space A to be the proportion of different energy production methods that will be used for the entire time period.
Crop yield We obtain the crop yield loss function `(x, a) with the following procedure
1. We obtain the crop yield dataset from (FAOSTAT et al., 2006), each entry we 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 4 dimensional vector described in Setup Details). We update each entry in step 1 to 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 `(x, a) where x is the weather statistics, a is the crop type, and `(x, a) is learned to predict the yield (normalized by market price) of the weather x for crop type a.
Energy production We consider three types of energy production methods: solar, wind and traditional (such as fossil fuel). Solar energy and wind energy both depend heavily on weather, while traditional energy does not. In particular, we use empirical formulas for solar and wind energy calculation:
solar ∝ number of sunny days ∗ daylight hour wind ∝ wind velocity3

heading: D Discussions
text: Future Work In this paper we explored the applications of H-divergence to two sample testing. Future work can explore other applications of divergences. Potential applications include
• Generative model training. Many generative models learning algorithm minimize divergences (Nowozin et al., 2016; Arjovsky et al., 2017), and future work can explore if the new divergence family leads to new generative model learning algorithms. • Independence tests. Independence tests are two sample tests between the joint distribution pXY and the product of marginal distributions pXpY , therefore the two sample test results from this paper are applicable to independence tests. • Robustness. Many robust optimization, estimation or prediction methods aim to achieve good performance even when the data distribution is perturbed. Typically perturbation is measured by e.g. the KL divergence or the Lp distances. Future work can measure perturbation with the H-divergence H` by choosing loss functions ` that are tailored for the problem.
Computation Issues There are several situations where estimating the H-divergence is (provably) computationally feasible:
• When A is a small finite set, in which case we can enumerate all possible values of a ∈ A. • When the loss function `(y, a) is convex in a, in which case we can accurately estimate the H-divergence in
polynomial time by solving the optimization problem infa E[`(Y, a)] by gradient descent.
In general, while it is difficult to guarantee computational feasibility, we use a practical technique that works well in our experiments: we use the same number of gradient descent steps for evaluating H` ( p+q 2 ) and H`(p), H`(q). Intuitively, the “sub-optimality” when estimating the three terms is approximately the same in expectation and cancels out.

Review summaries:
This paper presents a new class of discrepancies between two continuous probability distributions. The proposed class, which is called the H-divergence, contains an extended class of Jensen Shannon divergences called H-Jensen Shannon divergences and another class (2) called the H-Min divergences as special cases. The conditions that the two probability distributions have non-negative H-divergence are given. It is seen that the set of H-Jensen Shannon divergences includes the set of squared Maximum Mean Discrepancies as a subset. Estimation and convergence of the H-divergence are discussed. The H-divergence is applied to propose two-sample tests and experiments suggest that the proposed tests outperform some existing tests in terms of power. The proposed methods are applied to climate data for decision making in agriculture and energy production. 

This paper proposes a new category of divergences, called H-divergence, for measuring the discrepancy  between two probability distributions. H-divergence is based on the optimal loss with respect to a chosen decision task and is therefore decision dependent. Further, it generalizes a few well known divergences such as the Jensen-Shannon divergence and the maximum mean discrepancy family. The paper proves a few properties of H-divergence including a convergence result when H-divergence is estimated using a finite set of samples. Further, three examples are used to illustrate the applications of H-divergence  including two sample tests, assessing climate change, and feature selection, which demonstrate the advantage of H-divergence compared with other commonly used discrepancies.

This paper proposes H-divergence, a new type of divergence based on H-entropy, to compare two probability distributions. This new divergence includes some of the commonly used integral probability metrics and f-divergences, such as Jensen Shannon divergence and MMD as special cases. A crucial property of H-divergence is that it takes into account the decision loss; namely, it compares two distributions in a way that distinguishes them based on the optimal decision loss, i.e., "two distributions are different if the optimal decision loss is higher on their mixture than on each individual distribution." It also provides an empirical estimator for H-divergence and studies its convergence properties. The paper studies several use cases of H-divergence, including two-sample tests. Experiments demonstrate that H-divergence achieves higher test power than tests based on MMD under the same type I error rate. Another important use case of H-divergence is understanding whether differences between distributions are significant enough to affect decision making (from the viewpoint of minimizing loss) in different experiments, including how climate change affects various economic activities.