Comparing Distributions by Measuring Differences that Affect Decision Making
Authors: Shengjia Zhao
Abhishek Sinha
Yutong He
Aidan Perreault
Jiaming Song
Stefano Ermon
Venue: ICLR 2022 Oral (2022)
Keywords: probability divergence
two sample test
generative model

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 social and economic activities, evaluating sample quality, and selecting features targeting different decision tasks.

Published as a conference paper at ICLR 2022
COMPARING DISTRIBUTIONS BY MEASURING DIF- FERENCES THAT AFFECT DECISION MAKING
Shengjia Zhao", Abhishek Sinha', Yutong He', Aidan Perreault, Jiaming Song, Stefano Ermon Department of Computer Science Stanford University {s jzhao, a 7b23, kel 1 lyyee aperr, tsong, emonn
ABSTRACT
Measuring the discrepancy between two probability distributions is fundamental problem in machine learning and statistics. We propose a new class of discrepan- cies 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 competing methods. In addition, 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.
INTRODUCTION
Quantifying the difference between two probability distributions fundamental problem in ma- chine learning. Modelers choose different types of discrepancies (or probability divergences) to encode their prior knowledge about which aspects are relevant to evaluate the difference. Inte- gral probability metrics (IPMs. Müller (1997) and f-divergences (Csiszár) 1964) are widely used discrepancies in machine learning. IPMs, such as the Wasserstein distance, maximum mean discrep- ancy (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 used define training objectives for generative models (Arjovsky al. (017), perform independence tests (Doran et al. 2014), robust optimization (Esfahani & Kuhn 2018) among many other applications. /ddivergences. 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 discrepancy based on how different the likelihood ratio 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 metries or the set /ddivergences. Intuitively, H-divergence compares two distributions in terms of the optimal loss for a certain decision task. This optimal loss corre- sponds 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 arbi- trary 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+ g)/2 and the generalized entropy of p and q individually. Intuitively, if p and q are different, it is expected loss under the mixture distribution (p + /2, and hence the mixture distribution should have higher generalized entropy; p and q are identical, then the mixture distribution is identical to p or g. and hence should have the same generalized entropy.
difficult to minimize
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
"Co-first author

---

Published as a conference paper at ICLR 2022
Jensen Shannon
MMD
Wasserstein
6-Divergence
IPM
Figure 1: Relationship between H-divergence (this paper) and existing divergences. The Jensen Shannon divergence is f-divergence but not IPM; the MMD is IPM but not always f-divergence; both are H-divergences. There are H-divergences that are not f f-divergences or IPMs.
the Venn diagram in Figure Our formulation allows us to choose alternative losses to leverage inductive biases and machine learning models from different problem domains. For example, if 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.c. to decide whether two sets of samples come from the same distribution or not. test based on 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 off-the-shelf generative models. Compared to state-of-the-ar tests based on MMD with deep kernels (Liu et al. 20200), tests based on the H-divergence achieve better test power (given identical type 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 show that H-divergence is useful tool for quantifying how distributions different with three application examples: studying the effect of climate change, feature selection, and sample quality evaluation. In each of these examples, distributions by choosing specific decision loss functions. For example, climate change (Figure B} might impact agriculture
compare different aspects of the
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.
BACKGROUND
2.1
PROBABILITY DIVERGENCES
Let X' denote a finite distributions on X' that have density. We consider the problem of defining probability divergence between any two distributions in P(X), where probability divergence any function D P(Y) x P(X)) + R that satisfies D(pllg) 2 0, D(plp))
finite dimensional vector space, and P(X)) denote the set of probability
Vp, q E P(X). We call the divergence D "strict" if D(pllq) > 0 Vp + 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 defined as (PM)(Pllg) = sup [x)] F. [[ 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 is the set functions X' + 1 The maximum mean discrepancy (MMD) (Rao 1982; Burbea & Rao 1984, Gretton et al. 2012 chooses a kernel function & X +
R_ and is defined by
MMD2(ppl4) = kp,, Y) + kx,,k(X))) kE,
MMD is an IPM where F is the unit norm functions the reproducing kernel Hilbert space (RKHS) associated with the kernel k.
2

---

Published as a conference paper at ICLR 2022
f- D-ivergences Given any convex continuous function R+ - R such that f(1) 0, the
f- D-ivergence is defined as (assuming densities exist) (p(p)))) = (x Examples include the KL divergence, where f t flogt and the Jensen Shannon divergence, where f t + (t + 1) log E+1 + tlogt.
2.2 H-ENTROPY
For any action space A and any loss function f x A -> R, the H-entropy (DeGroot et al. DeGroot 2005 Grünwald al. 2004) defined as
1962
H₂(p) inf Ep]e(X,a)] aEA
In words, Heentrop is the Bayes optimal loss of a decision maker who must select some action for a particular z, but in expectation for random x drawn from p(z). H-entropy generalizes several important notions of uncertainty. Examples include: Shannon Entropy, where A as the set of probabilities (2)), and (xx, a) = log a(x); Variance where A X, and f(r, a) = | -a-aap Pre- dictive V-entropy, where A C P(X) is some subset of distributions, and f(x, a) log ( Xu ict al. 2020).
A key property will use is that H-entropy is concave (DeGroot et al. 1962).
Lemma 1. For any choice of L. X x A + R. H3 is concave function.
This Lemma can be proved by observing that inf is concave function: it is always better to pick an optimal action for p and q separately rather than a single one for both.
Helap + ()) inf (a [[(X a)] (1- (1-a))E (
a En Epl((
a) inf ( [[(() aH((p) + (1-a))el0
This Lemma reflects why Hy can be thought of as a mcasurement entropy or uncertainty, the distribution is more uncertain (c.g. mixture of and g, rather than p or q separately) then decisions made under higher uncertainty will suffer higher loss.
3 DEFINITION AND THEORETICAL PROPERTIES
3.1 H-JENSEN SHANNON DIVERGENCE
As a warm up, we present special case of our divergence. Definition (H-Jensen Shannon divergence).
D (p. = H1g p 2
(H + Hc(g))
(I)
DJ is always non-negative because H-entropy is concave (Lemma and clearly D (p, 9) whenever 4. Therefore, DJIS is a valid probability divergence. In particular, if we choose He as the Shannon entropy, Definition function choices recover definitions in (Burbea & Rao 1982..
[ recovers the Jensen Shannon divergence. Other special loss
3.2 GENERAL H-DIVERGENCE
In addition to the H-Jensen Shannon divergence, there other functions based on the H-entropy that satisfy the requirements of a divergence. For example,
D Min = He
p 2
min(H+(p), Hz(g)
(2)
also a valid divergence (this will be proved later as a special case of Lemma 2 We can define a general of divergences that includes the above divergences with the following definition:

---

Published as a conference paper at ICLR 2022
Definition 2 (H-divergence). For two distributions p.q on X. given any continuous function Φ R² + R such that c(0,, X) > O whenever 0 + X and @00, 0) = 0, define
(ollg) = (He p HT(p), He p p+ q
H((g))
2
2
Intuitively Hz (222) (p) and H2 ( H2(9) measure how much more difficult it is to minimize loss on the mixture distribution (p + q)/2 than on p and respectively. e is general class of functions that map these differences into scalar divergence, while satisfying some desirable
properties described in the next section.
The following proposition shows that the H-divergence generalizes the previous definitions ① and 2). Therefore, any property of H-divergence is inherited by c.g. the H-Jensen Shannon divergence.
2+À then D (p,9) the H-Jensen Shannon divergence Eq. If Proposition If @(0, A) 2 @(0, A) max(0, A) then Dj (p. 9) is the H-Min divergence in Eq.
3.3 PROPERTIES OF THE H-DIVERGENCE
We first verify that D2 indeed (strict or non-strict) probability divergence.
Lemma 2. For any choice of and for any choice of & that satisfy Definition 2 and D (p. q) = 0 whenever = Furthermore, D is symmetric whenever e is symmetric.
Dj is non-negative
Depending on the choice of f, H-divergence may or may not be strict (i.e. whenever p # q. D(plly) 0). The following proposition characterizes conditions for strict divergence.
Proposition (Strict Divergence). For any choice of 6 the following are equivalent 1) Vp + q. (e > 0. 2) The H-entropy (p) = inf, Ep(e(X,a)) is strictly convex in p. 3) Vp # q. arg inf (,, a)] arg in E [eX, a)] 0.
In particular, this proposition can be used 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
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. D2 (pllg) > O if and only if arg inf Ex(e((X))) O arg inf, Eg [ a)] = -
Intuitively, DJ only takes into account differences between distributions that lead to different opti- mal action choices. This property allows to incorporate prior domain knowledge. By choosing A and we can specifly which differences between distributions lead to different optimal actions, and which differences do not. For example, can choose A as set of generative models (e.g., mixture of Gaussians) and f(r a) as the negative log likelihood of x under generative model a. If under two distributions end up learning the same generative model (by maximizing 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 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 X + R. there exists an action space A and loss such that the corresponding squared MMD distance and H-divergence 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 f(x, a) = [[] - all? Inclusion is strict because the Jensen Shannon divergence is H-Jensen Shannon Divergence but not squared MMD distance.
4

---

Published as a conference paper at ICLR 2022
3.5 ESTIMATION AND CONVERGENCE
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 set of m i.i.d. samples mm) drawn from distribution g.
Pm = (x1, -mm) drawn from distribution p and dm = (x), and would like to obtain an estimate of D (pllg) based on the samples. Here, Pm and 4m denote empirical distributions drawn from p and respectively.
this section we propose an empirical estimator for the H-divergence and show that it has favorable convergence properties.
Let (fm m
be the empirical (random) estimator for D (pllg) defined by
Dr (Pmllåm) =Φ inf Σ la a) inf m
Σ (xx
a) inf (x. a) -inf 1
1
m Σ Elldaa)
m
where x² xxcb + 21 11 b:) and by are i.i.d uniformly sampled from {0, 1). so that x!! is sample from the mixture distribution (p + 1)/2 2 of size m.
Using x as defined above is crucial for the convergence properties we will prove in Theorem It might be tempting to replace the term 1 ΣE= E(x"'' a) with 1 Σm= (4(2,,) + [[2,, a)) to use 2m
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 (a²") ensures
the bias for the mixture comparable 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 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 0 S f(x,, a) S C, Va, x. This assumption seemingly exclude important divergence (which is associated with the unbounded log
special cases such as the Sensen-Shannee loss). However, we show in the appendix that the ensen-SShnnoo divergence cannot be consistently estimated in general, hence correctly excluded by theorem. One practical solution is 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 I-Lipschitz under the co-norm, i.e. 10(0 + d0, = ((0, max(d0, dA), v0, X, d0, dA E RR. Both @00, A) 2 and 6(0, A) = max (0 + >} are 1-Lipschitz under the co-norm. This is mild assumption because if é is not 1-L.ipschitz we can rescale e to make it 1- I-Lipschitz. Finally, define the Radamacher complexity
m Σ ()) aeA m
Re (t) Ex
sup
We define R4,(0 analogously. Based on these assumptions and definitions we can bound the dif- ference between (pm (qm) and (p(l)) Theorem 2. Ifß is C-bounded, and @ is 1-Lipschitz under the co-norm, for any choice of distribution p.q E (X and t > 0 we have
2m
1. Pr[D (pmll(m)) 2 t) 5 de
10
=-p=q.
P.m. 2. Pr D (pmllámm) - (p(le)) 2 44max (4), (f)) + < 4e
20
Corollary 1. v V (Dm llmm) < ma (f), Rg (()) 22C
For proof Appendix A. Note that when p q, the convergence of Di (pm (mm) does not depend on the Radamacher complexity of f, and converges to 0 very quickly. When p # the estimator Df (pm (l@m) is still consistent (under regularity assumptions)
Corollary 2. [Consistency] Under the condition of Theorem 2 if additionally either I. A is a finite set 2. A is bounded subset of a for some d E N and E is Lipschitz w.r.t. a, then almost surely lim 200 Dg (pm [m D (pl(g).
5

---

Published as a conference paper at ICLR 2022
For both cases in Corollary the Radamacher complexity (e) goes zero (as sample size m - o0) at a rate of / mm). In other words we can conclude that the estimation error in Theorem is bounded by O(1/ vm and the variance of the estimator is also bounded by mm)
when the sample size m -> oC.
4 EXPERIMENT: TWO SAMPLE TEST
The first application is to design more powerful two sample tests. We aim to show that H-divergence allow 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.
4.1 TWO SAMPLE TEST
For the task of two sample test, we would like decide two sets of samples are drawn from the same distribution or not. Specifically, given two sets of samples pm == (21, :mm)
and Qm : (a'1, mmm 1i g we would like to decide if p = q. Typical approaches estimate a divergence (pm [m)) and output & q if the divergence exceeds some threshold.
There two types of erros: Type I error happens when the algorithm incorrectly outputs p F q the probability of type errors is called the significance level. Type II error happens when the algorithm incorrectly outputs p q: the probability of not making a Type Il 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 mea- suring the test power. In particular, the significance level can be guaranteed with a permutation test (Frnst et al. 2004). In permutation test, in addition to the original set of samples P... and im. we also uniformly randomly swap elements between Pm and q.. and sample multiple randomly swapped datasets (pt,, (mn) (D (m)), .... The testing algorithm outputs * D( is in the top a-quantile among (D(iL, (.))) (52 nificance level (i.e. low Type I error) because if p then swapping elements between P... and in should not change its distribution, so each pair (fm: gm), (Ph ) should have the same distribution. Therefore, D (mm) happens to be in the top a-quantile with at most probability. Note that the significance level guarantee does not rely on accurate estimation of H-divergence in Theorem (accurate H-divergence estimation is still important because the test power does depends on it).
[mm),, ...))... Permutation test guarantees the sig-
When the choice of Df is not strict divergence (See Proposition 2) we may falsely conclude (D(pllg) 0) when in reality * q. This is true but inconsequential in finite data scenarios. With finite data, it is generally impossible guarantee the test power (i.e. bounding the probability of concluding = g when in reality * for any p, q) and prior literature do not provide such guarantees. Hence our guarantee no weaker than prior two sample test literature.
4.2 EXPERIMENT SETUP
Baselines We compare our proposed approach with six other divergences. All methods are based on the permutation test explained in Section 4. 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. Mean embedding (ME) and smoothed characteristic functions (SCF) (Chwialkowski et al.) 20155 Jitkrittum et al., 2016) are distances based the difference in Gaussian kernel mean embedding at a set of optimized points, or set optimized frequencies. C2STS-S S & C2ST-L (Lopez-Pat Paz & Oquab] 2017]; Cheng & Cloninger 2019) use classifier's accu- racy distinguishing between the two distributions.
Comparison Metrics and Setup All methods have the same significance level (which is provably equal to a 0.05 because of the permutation test), therefore we only consider the test power. We follow Liu et al. (2000) and consider four datasets: Blob (Liu et al.) 2020), HDGM (Liu et al.
'The code reproduce experiments he found here

---

Published as a conference paper at ICLR 2022
2020), HIGGS (Adam-Bourdanl) Bourdarios et al., 2014) and MNIST (LeCun & Cortes 2010). Our method and all the baseline methods have papper-prraeterss. To ensure fair comparison, we follow the same evaluation setup (Liu et al. 2020) for all methods. We split each dataset into two equal partitions: a training set to tune parper-praamters, and a validation set to compute the final test output.
Implementation Details We choose (60, X) = - for & > 1 (which includes the H- Jensen Shannon divergence when s 1 and the H-Min divergence when s = oo). We define [xx, a) as the negative log likelihood of under distribution a, where a is in certain model family A. We experiment with mixture of Gaussian distributions, Parzen density estimtor and Variational Autoen- coder (Kingma& & Welling, 2013). Our
consist of the best parameter and also the best generative model family. Choosing these hyper-paramest might seem cumbersome, but com- pared to the second best baseline (MMD-D which chooses thousands of deep kernel parameters), we have much fewer paree-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 q). Finally we plot and report the performance standard deviation by repeating the entire experiment 10 times.
4.3 EXPERIMENT RESULTS
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).
The average test powers are reported in Figure 4 Figure 2 Table and Table 3
Following (Liu et et 2020) 20200) we also evaluate the test power as the dimension of the problem increases (Figure 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).
MMD-0
C2ST-L
C2ST-S
ME
SCF
MMD-D
H-Div
Average Test Power
Average Teot Power
0.75
0.75
0,50
0.50
0.25
2.5
5.0
10.0
12.5
15.0
17.5
20.0
0.00
0
2000
4000
8000
8000
10000
Samples
Semples
Figure 2: Average test power 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. All tests have high test power for low data dimensions, but our method scales better for higher data dimensions.
N
ME
SCF
C2ST-S
C2ST-L
MMD-O
MMD-D
H-Div
1000
0.000
0.005-
0.082-10.05
0.097-10014
0.132-Lo.00
0.113
0.240-Lo.020
2000
0. 165
0.130-t0.019
0.183:t0026
0.232-to05
0.291
+20001
0.304
0.380-t0.040
3000
0. 1997-t0012
0.142-t:.025
0.257-:0049
0.399-Lo.ss
0.376:La.022
0.403-10.000
0.685-Le.0d
5000
0.410
0.261 =t000
0.592-t00037
0.447-t0015
0.659:t0.018
0.699
0. 0.930-t0.010
8000
0.691 +:0.67
0.467--o.000
0.892++0.02
0.0
0.923-ta.01
0.952-+0.024
1.000-t-..00
10000
0.786120.011
0.603
0.974
0.985
1.000=00.000
1.000=20.000
1.000=10.000
Avg.
0.395
0.283
0.497
0.506
0.564
0.579
0.847
Table 1: Average test power + standard emror for N samples over the HIGGS dataset. The results on MNIST is similar and presented in Table Appendix B.I
7

---

Published as a conference paper at ICLR 2022
0,200
32
2.8
2.4
0.125
2.0
0.100
0.075
12
0.050
0.8
0.025
0.4
0.000
0.0
Figure 3: Example plots of H-divergence across different geographical locations for losses l related to agriculture (left) and energy production (right). Darker color indicates larger H-divergence. Com- pared to divergences such KI., H-divergence measures changes relevant to different social and economic activities (by selecting appropriate loss functions E). For example, even though climate change significantly impact the high latitude high altitude areas, this change has less relevance to agriculture (because few agriculture activities are possible in these areas).
5
EXPERIMENT: DECISION DEPENDENT DISCREPANCY MEASUREMENT
5.1
ASSESSING CLIMATE CHANGE
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. Scien- tists and policy makers are often interested in how climate change disparately affect different geo- graphical locations. Existing methods (Preston al., (01IT) focus on one aspect of climate change (such as the expected economic loss (Burke et al., 201 8)) using tailor-desinned 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 as- pects climate change that are relevant to decision making in agriculture and 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 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. wheatbbaley/rice)) and f(xx a) denote the loss of planting crop a if the yearly weather x. We estimate the function é by matching geographical locations in the FAO crop yield dataset (FAOSTAT et al., (0066) to weather stations the NOAA database, and learn a function to predict crop yield from weather data with kernel ridge regression.
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 min.gA E 2/ a))); (2) plant the optimal crops for 1981-1999 and for 2000-2019 respectively. H divergence measures the additional loss of option (1) compared 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 D for the estimated l (plotted in Figure left).
Energy production Changes in weather also affect electricity generation, since cli- mate change could affect the amount wind/solar energy available. Let AA denote the number of wind/solar/fossil fuel power plants built, and f(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 (right). Intuitively the H di-
Example:
DDsigning loss functions l 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 he taken as an illustrative example of how domain experts might H-divergence with more realistic loss functions.
8

---

Published as a conference paper at ICLR 2022
Loss Selection
Selected Features
Neutral
education, cap-gain, sex, age, occupation education, cap-gain, relationship, marital-status, sex education, cap-gain, sex, age, race
Upweight low income
Upweight high income
Features selected by different approaches. With H- H-Divergence we can select different features that important in different decision problems. For example, if we assign high / low penalty to making incorrect prediction for higher income groups, we select a different set of features.
Table 2:
vergence 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 quantitative framework for this kind of assessments.
5.2 FEATURE SELECTION
In feature selection task, 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 (Jović al. 2015) Zhang al., 2015).
Off-the-shelff feature selection algorithms often do not take into account problem specific require- ments. For example, denote the input features as , and label as Y. the mutual in- formation feature selection algorithms estimate the Shannon mutual information [(,,, Y) == (L(p(X,, ()))p((X))(())) and select features with largest mutual information. However, scien- tists and policies makers often need fine- 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 (xX,, Y)Il (),(() (i.e. the optimal action is different under the joint p(X,, Y) and the product of marginals p(X)) By choosing different loss functions l we 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, choose A the set of logistic regression functions, ((x, a) as the cross entropy loss for regression function a on the sample x and ((0,A) max(0, A). If we want to focus high income groups, we can assign 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 more predictive 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 connection between gender/race and high income. These connections merit further investigation into the cause and policy remedy.
ACKNOWLEDGEMENTS
SE acknowledges support by NSF(#1651565, #1522054, #1733686), ONR (N000141912145) AFOSR (FA95501910024), ARO (W911NF-21-1-0125)) and Sloan Fellowship.
REFERENCES
Claire
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. JMMR.org, 2014.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223, PMLR, 2017.
Peter Bartlett. Theoretical statistics, lecture 13. https: stat wtw.:/eetttt...eee............ fdff 2013.
"bartlee http:///wowaaeeee/////////ee//ee

---

Published as a conference paper at ICLR 2022
Catherine Blake. Uci repository of machine learning databases. http://www. ics. uci. edu Inlearn/LLReposstory html, 1998.
Jacob Burbea and C 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. Probab. Math. Stat, 3:241-258, 1984.
Marshall Burke, W Matthew Davis, and Noah S Diffenbaugh. Large potential reduction in economic damages under un mitigation targets. Nature, 557(7706):549-553 2018
X. Cheng and A. Cloninger. Classification logit two-sample testing by neural networks. ArXiv, abs/1909.11299 1298, 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 informationsthoorrticche ungleichung und ihre anwendung auf beweis der godizitaet von 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 Bernhard Schölkopf. A permutation-based kernel conditional independence test. In UA,, pp. 132-141, 2014.
John Duchi, Khashayar Khosravi, Feng Ruan, et al. Multiclass classification, information, diver- genee and surrogate risk. Annals of Statistics, 46(6B) 2018
Michael D Ernst et al. Permutation methods: 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, 171(1-2):115-166 2018.
FAO FAOSTAT et al. Fao statistical databases. Rome: Food and Agriculture Organization of the United Nations, 2006.
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 Statisties, 32(4):1367-1433 2004.
Dan Hendryeks and Thomas Dietterich. Benchmarking neural network robustness to common cor- ruptions and perturbations. arXiv preprint urXiv:1903.. 12261, 2019.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to 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

---

Published as a conference paper at ICLR 2022
Alan Jović, Karla Brkić, and Nikola Bogunović. A review of feature selection methods with appli- cations. In 2015 38th international convention on information and communication technology, electronics and microelectronies (MIPRO), pp. 1200-1205, leee, 2015.
Diederik Kingma and Max Welling. arXiv:1312.61 14v10, December 2013.
Auto-Encoding variational bayes.
arXiv preprint
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. UtLhttp:///an
lecun. wttp///c/////////eeeee/eooo
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang. A. Gretton, and D. Sutherland. Learning deep kernels for non-parametric two-sample tests. ArXiv, abs/2002.09116, 2020.
David B Lobell, Marshall Burke, Claudia Tebaldi, Michael D Mastrandrea, Walter P Falcon, and Rosamond L Naylor. Prioritizing climate change adaptation needs for food security in 2030. Science, 31965863):007-610, 2008.
David Lopez-Paz and M. Oquab, Revisiting classifier two-sample tests. arXiv: Machine Learning. 2017.
Tengyu Ma. Machine
notes/
pdf, 2021.
Alfred Müller. Integral probability metrics and their generating classes of functions. Advances in Applied Probability, pp. 429-443, 1997.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 271-279, 2016.
Npower. Wind turbine power calculations. Mechanical and Electrical Engineering Power Industry, The Royal Academy of Engineering, 2012.
Benjamin L Preston, Emma J Yuen, and Richard M Westaway. Putting vulnerability climate change on the map: review of approaches, benefits, and risks. Sustainability science, 6(2): 177-202, 2011.
Radhakrishna Rao. Diversity and dissimilarity coefficients: a unified approach. Theoretical population biology, 21(1):24-43, 1982.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Jiaming Song and Stefano Ermon. Understanding the limitations of variational mutual information estimators. arXiv preprint arXiv:1910.06222. 2019.
Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet. On integral probability metrics, metrics...hiiddvergee -phidiieereencss and binary classification. arXiv preprint arXiv:0901.22 2699, 2009.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints. arXiv preprint 200::20022.0880 2020.
Yudong Zhang, Zhengchao Dong, Preetha Phillips, Shuihua Wang, Genlin Ji, Jiquan Yang, and Ti- Fei Yuan. Detection of subjects and brain regions related to alzheimer's 's disease using 3d mri scans based on eigenbrain and machine learning. Frontiers in computational neuroscience, 9:66, 2015.
11

---

Published as a conference paper at ICLR 2022
A PROOFS
Lemma 2. For any choice of and for any choice of 6 that satisfy Definition whenever p q. Furthermore, Di is symmetric whenever & is symmetric.
D2 is non-negative and (p,g) = =0
Proof of Lemma For any choice of p. 9 by the concavity of the H-entropy in Lemma
we have
+
1 (He(g) He(p))
He
He(p)
2
2 1 ; (He(p) He(g))
+
He(e))
2
2
Therefore by summing the two inequalities we have
He
+
He(o))
[1e
p p
He(g) 20 0
2
By the requirement on o we know that D2 (pllg) 2 0. In addition when since (p + 9)/2 = we have D& (pllg) (0, 0) O. To show it is symmetric, note that
D (ollg) ( [1i p -
(pt - (o(oo) = 8 (Ile (p+q
(p+g
He(p), He
He) H1
Hp(p)
2
2
2
2
(gllp)
whenever é is symmetric.
Proposition 3. (pll4) > 0 if and only arg inf, E ( a)] n arginf, Eg [[(,, a)] = 0.
Proof of Proposition
Denote AI = ing F., X, a)] and A = arginf, E. [,( [C((X,)), a)). Also compute
He p +
inf E 24z [6(X, a)] inf Bxle(x, a)] 1e
(3)
2
If A A =, 0, for any action a' such that E,, d')] ] He(p), must have a' A₁ so a' & A and E,["(X, aa)l
He(g)- Similar if we choose a" such that E. [(X, d")] Helg) have similarly have Ep ((((((aa) > Help). In other words, for any choice of action a E A either a & A and E, a)] > He(p) or E AA and E, ([(((Xaa) > Hz(g). Therefore
inf (2 a)]
1 _ > > Hc(p) He(g)
(4)
Combining Eq. and Eq. we have
1 2
He
p ( (2t - -Hilp)
Hi
p p
HHo()) >0
2
By Definition this implies (for any choice of @ that satisfies the requirements in Definition 2) that D (pllg) 0.
To prove the converse simply obverse that if Ar n A # o, let a' E A Ag we have a* = arg inf E agg [(X, a)]. This implies that
p+q
2H:
H((() - He(p) = 2E [((X( [,,((X,")) -x,((,"")]
By Definition we can conclude that (pllg) = 0.
Theorem 1. The set of H-Jensen Shannon Divergences is stricily larger than the 2MD2 distances.
12

---

Published as a conference paper at ICLR 2022
Proof of Theorem Let k(2 y) be some kernel an imput space X, and let H be the RKHS induced by the kernel. The
(squared) MMD distance is defined by
MMD (p.g) 9) =xxxp, (o + a k 21E Yxg
which we write more compactly as MMD3 (p, q) = ((X, + kX, 2Ep.gk(X,,))
Define o(x, y) = [|,( k(y, 1122- We can rewrite this in the following form:
1 MMD*(p, g) = E X, Y) p
2 2
(5)
EmallA(X, 11l + ||A((X,))) -2(XX,)) - 1
Ep )I + [|
(OXKK))) ) 22(X,
1 B (1x,,l, 1) + ||K(Y, 11 2) kX 2 Y) -2Ep. (X, Y)
We also observe an algebraic relationship for any function [(x, 3) such that ((x,)) 4) = =V( x) for all x, y
Exts, 233 ((X - 4 /x + p (X,Y) + En (x,,)((X)))))))))))))) + (X,
4
1 P (X, + E p (X, + E (X) + 7 /
Bnpl(X,,) (X,Y)
E f (X, +)+ E E
(6)
Furthermore, we have that
(( - k(Y,-) = 2F EY, )11
Based on the above, noting that Φ(x,1) v) = KbV, 2),, we can derive
MMD (p. 4) = Eppalkk( )) - k(Y, 1133 1ー2 Bpp ||((| - A(Y, )13e - E, - K<YY,))
1
Eq 5
2E n+a, 2to 2 | k(Y, -) >>3 Ep.plk((X :) K(Y, 1E (1, -) K-(
Eq 6
-4E,3o ||,(X, )) - E Exge kYY, >11 2 (E,((Y,))) )1 - 2E, (E(,),(X,)) - AY,
Eq
= inf E a [x(x, al 1
2 inf E. [x((, - -al13 2 inf Ey (x - -a113-
mean def.
aEH
dEH
aE7
Therefore we can define a loss f: X' x
H where
Ux, u) = 411k(x,,) - al1
Under the new notation we have
1 1/ inf Ex,((, inf Ex,((Xa) inf E Egga (X,a)) dEHt
MMD
aEH
oEH
p + q
- (11(2) + He(()) (plla)
He
2
Conversely we want to show that not every H-Jensen Shannon divergence is MMD. For example, take He to be the Shan-
non entropy, then the corresponding DJSS is the Jensen-Shannon divergence, which is not 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 al. 2009). Therefore, the set of H-Jensen Shannon Divergences is strictly larger than the set of MMDs.
Theorem 2. If l is C-bounded, and o is 1-Lipschitz under the oo-norm, for any choice of distribution p, P(X) and t > 0
we have
1. P
2.m ifp= g. (pm (lmm) 2 t) < 4e
2. Pr D (pmll1mm) - (pll)) 2 4 1.4maaxPR (2),, +1 < 4e
2m
13

---

Published as a conference paper at ICLR 2022
Let Pm be sequence of samples (z1,-.. 2m) drawn from p. and 9m sequence of sam- ples (z), Vmm drawn from q. Let f' the sub-sampling mixture (.i.... z/ 2,b; + 21 b,) where b, is uniformly sampled from {0, 1)). We also overload the notation He by defining H,(P.)) infaEA - Li (z,, a), and define He((m), He(fm) similarly.
Proof of Theorem
defined in Section 3.5 (i.e. x. =
Before proving this theorem we need the following Lemmas
Lemma 3. Under the assumptions of Theorem
Pr (r( E(He((m) 2 2 2
Pr (((()m)))B((((())) S --15 6
Lemma 4. Under the assumptions of Theorem 2
21.m
Pr[ - (e()))) 2Rm (E) + S
62
To prove the first statement of the Theorem, when p q we can denote μ [fHe( E[H.(am)) (F and
we have
D (pm 2
Pr
= (r(o(He((mm) - Hz (e((m)),mmm))mmmm))))))))))))H Ho(fm))(mm)))))mm He((m)) 2
Def 2
Pr (max(He(ffm)) He (fm), Hem))
H)( 2 t]
1-Lipschitz
Pr [He((mm) - He (pm) 2 1] + Pr (f Hm 2 t]
Union bound
S Pr [[le(mm) / S -t/2] 2r (fe(fm) p 2 t/2] + Pr (el(mm) - - S -t/2]
Union bound
I 4e 2m
Lemma
The third inequality is because if Hf( Hp())) 2 t then it must be either He((m) - - -t/2 or He(fm) - 2 1/2. Similarly if (f( He(gm) then it must be either He Hê(mm) - p S -t/2 and H He(fmn) 1 2 21/2.
To prove the second statement of the Theorem, observe that
(pm lmm) (pll))
(HH((Fm) - H, (pm): He(f..) - H)((m))) & He p PP=2 !) Hrlp), Hi (D+ -Ha(4))
Def
2
S max [(e((m)) He(fm) - He (P+ He(p)), He((fm) - He(ām) - -He P (pt H((l))
1-Liip
< max ([He(tm)) He ( (P+9) 9) (e(((m) - He(e)l, He((mm) He (P+9) + +(He((m)) - Hc(a)))
Jensen
Therefore, the event events happen
[D (pm)llmm) - (rlle)) 2 max((2 (e)) happens only if at least one of the following
He(F - He p
(P,(1) (f) t/2 (2((+))/2))))) (2+t)//222)) t
R convex
2
He(Pm) He(p)
> 2Rm (L) + t/2
He(âm) Ht)
2 2R (E) + 1/2
Based on Lemma 4 each of these events only happen with probability at most e 202 bound that
Therefore we can conclude by union
Pr[lD)(pllg) - (rllg) 2 4 4ma (f), Rg. (4) +
< 4e
262
Finally we prove the two Lemmas used in the theorem. Lemma is standard result in the Radamacher complexity literature. For a proof, see e.g. Section 26.1 in (Shalev-Shwarzz Ben-David 2014). Lemma can also be proved by standard techniques. We provide the proof here.
14

---

Published as a conference paper at ICLR 2022
Proof of Lemma 3 Consider two sets of samples :1,".. 2g. 2m and 24. z ,n where 22 z for every
index
1,10, m except index j.
inf Σ ( inf Σ (a a) m
ssup Σ ( a)- 1 Σ e(atta)
-
1
{(z' S C
sup [((x,
m
m
Then conclude by Mediarmid inequality that
Pr inf 1 Σ ((X,, m
0) -
E
inf
1
Σ a)
2
S
2r2 247m
212
62
m
Corollary 1. / Var[D) (pmllâm)) S maxx(2g,))) (2) 22C2
Proof of Corollary
7
For notation convenience denote B 4 max(R2, (f), Rg, (!))
Var DJ (pmlllm))
(
[D (pmlllm)) (plla)) -g(
=E
(D% D2 (plla)) 2 dt
Pr
1=1
Pr (fm
12 -DX 2 v dt
0
Pr [ - D2 (plla) 2 2sds
= Vi
==0
1 Pr
2sds +
(pm - (plle) 2 B + 2(B + s)ds
==
==0
< B2 +
2(B + s)e
2 ds
8=0
< B2 +
(B + /1
20
)e 12
202 di
8
m
m
m
2C
20
20
f te dt
2 + 2B
dt
m
CTC
20
B² + B
+
S + 22C2/222//2 m3
m
m
Corollary 2. [Consistency] Under the condition of Theorem 2 if additionally either 1. A is a finite set 2. A is bounded subset 1f ddd for some d I and & is Lipschitz w.r.t. a, then almost surely limm- D (pm (l@m) (xllg)
Proof of Corollary We can prove the consistency results from Theorem by observing that the expected Radamacher complexity goes when -
The first statement is a simple consequence of Massart's Lemma, (e.g. see (8.48.4) Ma 2021 In particular, because A is finite we have
R2 (f) /2log A//m moc
15

---

Published as a conference paper at ICLR 2022
To prove the second statement, first observe that because A is bounded, there must exist some E R such that A C B, {a, ||a]l2 $ r). In addition, without loss of generality we can assume that there exists such that ve E X and a, E A
[ a) (1x a - L|la a'112
There no loss of generality because in finite dimensions all norms are equivalent, so f is i Lipschitz under any norm, then l Lipschitz under the 2-norm. We apply the results Radamacher complexity for smoothly parameterized class proved in (Bartlett 2013), and conclude that limm-so Ri (f) 0.
B ADDITIONAL EXPERIMENTAL RESULTS
B.1 BLOB DATASET
MMD
O0P MED
1400
OIL
CIT
Nanborr Gamps
100
43
SaSpples
500
Figure 4: Left: Average power the Blob dataset for different sample sizes and significance level a = 0.05. Our method (H-Div, dashed line) has significantly better test power, especially for setups with small sample sizes. Right: The same plot with significance level 0.01.
B.2 EVALUATING SAMPLE QUALITY
Impulte
1.0
+C
00
Swatts CoCoader
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 [0, 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 provided in Appendix B.2.
The gold standard for evaluating image generative models requires human decision, which is nevertheless expensive. Sev- eral 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 as the set of Gaussian mixture distributions on the inception feature space, 1(x, a) as the negative log likelihood of x under distribution and Φ(0, X) max(@ A). 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 images. Intuitively, adding more corruption degrades the sample quality, 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. increase the amount of corruption. Our method is
Both FID and H-divergence 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.
generally monotonically increasing
16

---

Published as a conference paper at ICLR 2022
Tog
10
RD
HDv
Wornslbos Dietance
08
Vermalooo Disance
0.3
0.6
044
0.4
04
0.2
0.
0.
2
Severity of Corvatton
Severty of Correttin
frost
shot
blur
FI
1.0
FID
H Eiv
H-Dv
H-Div
Nermston Dicinnce
Nermalzos Distance
Mormslizee Distancee
9.6
0.4
02
02
0.2
Sevel by
Severity Commatton
Comuptiinn
brightness
1.0
Mormatowd tHelnnc
0.8
Normatood Cietance
0.6
044
2.4
0.4
0.0
3.0
0.0
Severtty Comrattio
Severtty of Comuption
Severity of Comuation
geussian
1.0
Nomatred DibAre
0.8
Memmatzed Deeance
Nomalted Dratanoe
6.6
0.6
0.6
0.4
0.4
0.0
Severity Corrantion zoom
Severit of Corruttion
Severity of Comuotiin spatter
glass
1.0
3.0
1.0
H-DM
H Div
H.Div
Koreloood DiSunce
0.8
Nomnloow Disanua
Nomatioed Dieance
0.4
0.4
0.4
0.0
Severity Comuption
Severity Cormation
Severity Corruction
Figure 6: Additional plots that extend Figure 5
C ADDITIONAL THEORY AND EXPERIMENT DETAILS
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 A' is finite set, though all the formulas are applicable when X' has infinite cardinality.
17

---

Published as a conference paper at ICLR 2022
N
ME
SCF
C2ST-S
C2ST-L
MMD-O
MMD-D
H--Div
200
0.414
0.107=t0.018
0.193:t0.037
0.234
0.188=t0.010
0,555
1.000=00,00
400
0.921 -.002
0.152:4:0.021
0.646-t0.009
0.706=1:0.04
0.363-1-0.017
0.996=1-0.004
1.000=20.000
600
0.000
0.294
1.000=to.000
0.977=:0.012
0.619=20.021
1.000
1.000=
800
1. 0.000
0.317=t0.017
1.000:00.000
1.000=1:.000
0.797=t0.015
1.000=10.000
1.000-10.000
1000
1. 1.000
0.346++0.019
1.000++0.000
1.000-+00000
0.894-+0.0016
1.000++0.000
1.000-
Avg.
0.867
0.243
0.768
0.783
0.572
0.910
1.000
Table Average test power standard error for N samples over the MNIST dataset.
Choose A = X, and let ((,, a) be a symmetric function (1(x, a) = I(a, æ)) that denotes the cost of transporting a unit of goods from a. When we say that unit of goods is located according to p, mean that there is unit of goods dispersed in X' locations, where p(z) is the amount of goods at location x.
Setup
Optimal Transport Distance
The optimal transport distance defined by
inf 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; (p. q) denote the minimum cost to accomplish this transportation task.
Oclp. = XXY Exxy [X)
H-Divergence as Optimal Storage
We first consider the intuitive interpretation to the H-entropy
Hy(p) = inf (eple((.a))
a" = -ar inf E, [p(((X,a)
aEX'
Suppose we want to move goods located according to 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 build the storage location, and H-entropy measures the minimum cost to transport all goods to the storage location. Similarly 2He (P*+) measures the minimum cost to transport both goods located according to p and goods located according q to the same storage location. The H-divergence
[ [ (He(a) + Hc()))
(pllg) = -HH,
2
measures the reduction of transportation cost with two storage locations (one for p and one for q) rather than single storage location (for both and q).
The H-Divergence is related to the optimal transport distance by the following inequality.
Proposition 4. Ift satisfies the triangle inequality Vx, y, E X, [xx, y) + I(y; 2 [(x, 2) then (plla)) - _0ppp g)
Proof of Proposition
Let o, = arg inf (X,[(((,,)) a)] then we have
p + 9
2H
inf (Ep(e(X, + E,((((X a))) E,I((, E,le( ag)
2
inf PX inf XXx.xx=xx.y=x0 O2(p, 9) + 2Hr(g)
Bxxy [(( + a7]]
Exxy (((,)) + C(Y ال + E. (((Xx
Intuitively, to move goods located according to p and goods located according to g to some storage location, one option is to first transport all goods from p to (so that the goods at location r will be 2q(x)), then move the goods located according to 2q to the optimal storage location. Similarly we have
p +
2H,
S Olg.p)++HH.0
2
which combined have
2D/ = 2H:
p p
- (He(g) + He(p)) S ((p.g)
2
18

---

Published as a conference paper at ICLR 2022
C.2 IMPOSSIBILITY OF JENSEN-SHANNON DIVERGENCE ESTIMATION
Suppose we have a consistent estimator for the Jenson-Shannon divergence, i.e. a function JS such that for any pair of distribution p. q and given N i..d. samples PN ~ p and qN ~ q we have lim JS(pN]laN) = JS(pllg), then we prove a contradiction by the probabilistic method.
Let be a standard Gaussian distribution, let Q- be a uniform distribution on a set of M i.i.d. samples from p (hence QM itself a random variable that depends on the i.i.d. samples). Let Q* be the limit of Q² when M - oc (i.e. it is the uniform distribution on an infinite set of samples). Let q" denote value that Q can take. Because q" is always supported on countably many points, hence JS(pllq") 1. Note that for any N the following two sampling process leads identical distribution on pN, QN:
PN - PN ~
Q'~PPPN P.9N ~ Q
Hence, the expectation of any function (including JS) is also identical.
Eqrap
E Epx-n.aN-Q- Caapeoo--JS((pppp [JS(pN. qx)]]
= E (pSppp
Hence the limit when N - 3o must be identical
lim N
Eq-ap
E Ep Epr-p.aw [JS(pp 2x)1]
= lim ppp- 2x)]
N
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 Exx-n-un--- (J [w)]]
lim E (JpSp gN)]
NN
N
By the probabilistic method (i.e. for any function f if Eqq~) = there must exist some 9" such that f(x") s 0) there must exist some 9" such that
lim E Exxcr-ax- (JS(pN, S N -00
lim E Bipx = JS(plla") =1 N-+00
Therefore JSS 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 4 dimensional vector where each dimension correspond to one of the summary statistics above.
Let p denote the uniform distribution over {-1981.... ] and q denote the uniform distribution over {222000 22019 J. For example (,,.(((,,)) a) denote the expected loss of action for a random year sampled from 1981-1999. Note that for many decision problems, 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 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.
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, yicld 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
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.c. the 4 dimensional vector described in Setup Details). We update each entry in step I to be (weather statistics, crop type, yield per hectare).
4. Based on the data entries we obtain in step 3 train a Kernel Ridge regression model to learn the function {(z, a) where x is the weather statistics, a is the crop type, and f(x, a) is learned to predict the yield (normalized by market price) of the weather x for crop type a.
19

---

Published as a conference paper at ICLR 2022
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 x number of sunny days * daylight hour
wind wind velocity
D DISCUSSIONS
Future Work In this paper explored the applications of H-divergence to two sample testing. Future work explore other applications of divergences. Potential applications include
Generative model training. Many generative models learning algorithm minimize divergences (Nowozin et al. 2016 Arjovsky al., 2017). and future work can explore if the new divergence family leads to new generative model learning algorithms.
Independence tests. Independence tests 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 several situations where estimating the H-divergence is (provably) computationally feasible:
When is small finite set, in which case
enumerate all possible values of a E A. When the loss function é a) is convex in a, in which case we can accurately estimate the H-divergence in polynomial time by solving the optimization problem inf, E ((((Y, a.] by gradient descent.
In general, while it is difficult to guarantee computational feasibility, use practical technique that works well in our experiments: we use the same number of gradient descent steps for evaluating He (et9) and Hz(p). He(g). Intuitively, the "sub-optimality" when estimating the three terms is approximately the same in expectation and cancels out.
20


Reviews:
[{"review_id": "yTr83cYb6Hx", "reviewer": "Reviewer_pdf2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "**Strengths:**\n\n(a) The proposed class of divergences, H-divergences, includes well-known divergences such as Jensen Shannon divergence and squared Maximum Mean Discrepancy as special cases. The H-divergence also contains new classes of divergences, including the ones defined in Equations (1) and (2), which appear to be potentially useful in practice.\n\n(b) Some results are given to prove the convergence of the empirical H-divergence to its theoretical one; see Theorem 2 and Corollary 1. \n\n(c) The conditions on the non-negativity of the H-divergence are obtained; see Section 3.3. These theoretical results partly justify the proposed divergence as a reasonable discrepancy between two probability distributions.\n\n(d) A sufficient number of experiments are given to demonstrate the usefulness of the presented methods; see Sections 4 and 5. \n\n(e) The paper is clearly written. Appendix provides helpful information including detailed proofs of the theoretical results of the main article.\n\n&nbsp;\n\n**Weaknesses:**\n\n(f) Applications of divergences include not only two sample tests but also other methods such as robust estimation and independence tests. However the paper does not discuss possible applications other than two sample tests and plots in Figure 3. A brief discussion about other applications would be helpful for readers.\n\n(g) The variance of the proposed estimator $\\hat{D}^{\\phi}_{\\ell}  (\\hat{p}_m || \\hat{q}_m) $ is not discussed in the paper. Is it possible to discuss any result about the variance?\n\n&nbsp;\n\n**Minor Comments:**\n\n(h) p.1, Section 1, 1st paragraph, l.13: Add a full stop after 'point'.\n\n(i) p.1, Section 1, 2nd paragraph, l.1, etc.: There are at least three different expressions, namely, *H*-divergence, H-divergence and H-Divergence, in the paper to denote the same divergence. The expression should be standardized throughout the paper.\n\n(j) p.4, Section 3.3, l.6 up: This property allow us to  ===>  This property allows us to ", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper is generally well-written. Properties of the proposed class of divergences are well-investigated. A sufficient number of experiments are provided to demonstrate the usefulness of the proposed method.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ofIwg4cYIt", "reviewer": "Reviewer_SZbR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths: \n\nProposes a new type of divergence that compares two probability distributions from the lens of optimal decision-making. By setting an action set and loss function, one can identify \"how far two distributions are\" in terms of leading to the same optimal action. Moreover, the paper clearly explains the connection of H-divergence with f-divergence and integral probability metrics. Overall, H-divergence can be seen as a valuable contribution to the family of divergences used in machine learning tasks. \n\nExperiments are satisfactory. Especially, the flexibility achieved by using H-divergence by choosing application tailored actions and losses highlight the merit of H-divergence in performing two samples test. \n\nWeaknesses:\n\nThe convergence properties of the empirical estimator of H-divergence deserve more discussion in the main paper. In particular, the role of Rademacher complexity in the bounds in Theorem 2 and Corollary 1 is not clearly explained. It will be good to add a discussion in line with proof of Corollary 1 (on how fast Rademacher complexity vanishes) into the main paper. \n\nThe paper does not give enough detail about computational aspects. This clearly depends on the structure of the action set and loss function. The paper would benefit from the characterization of a set of (general) sufficient conditions under which computation of H-divergence is feasible. \n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "This paper makes a fundamental contribution to the family of divergences used for machine learning tasks and provides convincing evidence on the usefulness of H-divergence. However, there is still room for improvement related to the computation of H-divergence. Please describe the feasibility of computation of H-divergence for the experimental examples studied in the paper in your response.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QIZSXyvvm6t", "reviewer": "Reviewer_jd8q", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "Strengths\n\n1. Measuring the difference between two probability distributions is a fundamental problem in machine learning. Although many different types of divergencies have been proposed in the literature, they are typically decision independent. H-divergence seems a simple yet effective way of incorporating decision related domain knowledge into the discrepancy measure. \n2. The theoretical results are non-trivial are provide insightful connections between H-divergence and other commonly used discrepancies. \n3. The paper is well written. The theoretical results are solid and clearly explained. The three examples  clearly illustrate the broad applicability of H-divergence. \n\nQuestions:\n\n1. Theorem 2 assumes that the same number of data points are sampled from p and q, respectively. I wonder if the result can be generalized to the case when the number of samples is different for p and q. \n2. Can H-divergence still be useful when the decision task is initially unknown (as in reward-free reinforcement learning) or uncertain (as in multi-task learning)? \n3. In Section 4.2, only the results for alpha = 0.05 are given. I wonder if similar patterns hold for other values of alpha. \n", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall I think this is a very interesting paper. The new family of discrepancies is likely to find broad applications in machine learning and data science and can potentially inspire the development of other decision dependent discrepancy measures. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although by now there are several approaches for comparing probability distribution, the paper innovates by making their measure take into account the decision space and loss functions directly. The paper also frames its contribution within the literature at large. Reviewers were unanimous that the result is of major interest to the ICLR audience.
Decision: Accept (Oral)