Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Summary: The distance or divergence between two probability distributions is essential for machine learning. This paper introduces a new class of divergence functions based on optimal decision loss function. They first introduce a class of entropy functional, namely the loss function depending on the action and state. This type of function extends the classical entropy function, including negative Boltzman-Shannon entropy. Using it, they further construct a divergence based on the mixture of probability densities.  Several propositions and numerical experiments demonstrate the effectiveness of proposed divergence functions. 

Pro: The idea is clean, and the derivation is correct. Several analytical examples and detailed comparisons are presented. 

I still have some questions about the proposed approach. I may increase the rating if the author can address them. 

1. Have the author discuss the related Hessian metric for the proposed divergence function? For the KL divergence or Jen-Shannon divergence, the Hessian matrix for D(p, p+dp) recovers the Fisher information matrix. For the proposed approach, what is the corresponding information matrix? 

See related studies in 

Li, Zhao, Wasserstein information matrix, 2019.

2. The authors claim this divergence contains part of IPM (integral probability metrics). It would be better for the authors to discuss the relation of this proposed divergence with Wasserstein type divergences functions. 

3. Does the author consider the duality for the proposed divergence functionals? This could be useful in generative models. 
review_title: A new divergence for two sample tests 

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: This paper proposes a H divergence that is a generalization of many popular f divergences and IPMs. The paper gives an empirical estimator with convergence rates for this divergence, where the rates are very fast when the two distributions are equal. The paper shows how the empirical estimator has practical use for two sample tests and measuring the corruption of a sample. The proposed H divergence is "useful" when the two distributions are close to each other, but as the authors acknowledge in the future work, it is an open question whether it could be "useful" in other cases.

Overall I think this paper is very interesting and has a lot of novelty. I am not extremely on top of the most recent literature on measuring differences between probability distributions, so there may be literature that is not being reviewed and ignored, but from an "outsiders" perspective this seems to be a significant contribution to the area. There are some minor grammar issues (see minor comments for the ones I caught) and the paper could use a thorough re-read for grammar in general. 

Major Comments:
The proof for Proposition 2 shows that if the intersection between the optimal action spaces of p and q is empty, then the divergence is greater than 0. However it is not seem obvious that the converse is true i.e. if the divergence is greater than 0 then the intersection is empty. If the converse is trivial, having some explanation for it would be helpful.

The notation for the proof of Lemma 3 is rather confusing. The authors want to state that the two samples are equal except for at the points x_j and x'_j, but writing "i \neq j" seems to imply at first glance that the two samples are not equal where the indexes don't line up instead i.e. x_1 \neq x'_2. It would be clearer to just state x_i = x'_i except at one index j. Also remove the second "consider", it is not necessary.

Is it computationally possible to run the experiments more than 10 times? The power looks good but the type I errors still look a little noisy. Granted the scale is very small, but 10 is not considered a large number of "simulations".

Minor Comments:
- Please make Figures 2 and 3 bigger. There seems to be some white space you can play with and there is some room before the 8 page limit.

- Need an s here: "distance that work(s) well for distributions over high dimensional images."

- Remove "among of" here: "We show that H-divergences generally monotonically increases with the among of corruption added to the samples "?

- Use "or" instead of a slash here: "entropy / uncertainty"

- Remove "in order" here: "measure how much more difficult it is in order to minimize loss on the mixture distribution"

- Insert "that" here: "probability (that) an algorithm makes a type"

- "test power" is a strange term. Normally it is referred to as just "power" or "statistical power" or "power of a test"

- The caption in Figure 3 has (Left 2) and (Right 2) which are weirdly bolded and might be better written as (two on the left) and (two on the right)? Also missing an "s" here: "Our method (H-Div, dashed line) achieve(s)"

- Missing "s" here: "Each permutation test use(s) 100 permutation(s)"
review_title: Very Interesting and Significantly Novel

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors proposes a new class of divergence between probability distributions that generalizes both the Jensen-Shanon divergence and the Maximum Mean Discrepancy: the H-divergences.
Those divergences are constructed using the notion of the $H$-entropy of a probability distribution $H(p)$ defined as the minimum expected loss of an action $a$ in a set of possible actions $H(p)=\inf_{a\in A}E[l(X,a)]$ where the expectation is over samples  $X$ from $p$. Thus the $H$-entropy requires choosing a set of possible actions $A$ and a loss function $l(X,a)$.
The $H$-divergence between two probability distributions $p$ and $q$ is then obtained by comparing the difference between the $H$-entropy of the mixture distribution $(p+q)/2$ and each individual $H$-entropy of $p$ and $q$. By concavity of the $H$-entropy, the difference are both equal to $0$ only when $p$ and $q$ are equal. To allow for more generality, such differences are fed to an evaluation function $\phi$ so that the final form of the divergence is: 
$D(p|q) = \phi( H((p+q)/2) - H(p), H((p+q)/2) - H(q) ) $.
The authors show that this form is general enough to include both the JS-divergence and the MMD.
An estimator of the $H$-divergence using finite samples from $p$ and $q$ is proposed along with a concentration result for this estimator that is based on the Rademacher complexity.

Experiments:
In terms of experiments, to authors consider using the new divergence for two-sample tests and evaluating sample quality.
In the two sample setting, the authors perform extensive comparisons with other SOTA methods including the recent deep kernel two sample test outperforming all those methods in terms of test power, behavior with increasing dimension of the data and sample size.

On the sample quality task, the authors show that the proposed divergence is also correlated with human judgment for images. For this task, the authors chose the set of actions to be gaussian mixture of distributions on the inception feature space and the loss $l(X,a)$ to be the likelihood of a sample $X$ under the a mixture $a$. This is shown to often better capture corruption of the samples than the FID score. 






Strength:
 - The paper is clear and concise, the experiments are convincing as far as I understood.
 - The approach allows to incorporate prior knowledge about the problem by selecting a suitable set of actions $A$. In the case of two sample tests, this means that the method should capture differences between distributions that the user cares the most about. However it remains unclear if this flexibility cannot already be achieved using existing methods.

Weaknesses:
The paper does not really motivate the need for such new divergences. Hence, the impact might be limited.

The authors suggest that the additional freedom in choosing the set of actions allows to design divergences that are tailored to a particular problem. However, the authors do not explain whether this new generalization is able achieve something that already existing divergence fail to achieve. For instance, is there any particular reason to think one wouldn't achieve  similar experimental performance with a better choice of parametrization for the deep kernel? in the case of MMD-D?

In the experiments, the author make different choices for the set of actions depending on the dataset: mixture of gaussians, Parzen density estimator and for MNIST, a variational auto-encoder. However, the authors do not really explain what guides such choice.

The proposed estimator: In practice, the optimization is likely to be non-convex, especially when the set of actions is chosen to be a parametric family of probability distributions. How does this affects the estimation of the H-divergence? It doesn't seem to be an issue in the experiments, but wouldn't this be a disadvantage compared to other tests that have a closed form expression for the estimator?


Questions:
- Comparing the run time of each method? For instance SCF was designed to have a fast run time in the number of samples and tradeoff power for speed.
- On the sample quality task. How does the proposed method compare to the KID score, which has the advantage to be unbiased.
review_title: Interesting experimental results and clear presentation, but lacks motivation for the new method

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a new class of divergences defined by a decision-theoretic perspective, in the sense that two probability distributions are different if the optimal decision loss is
higher on the mixture distribution than on each individual distribution. This new class generalizes the popular Jensen-Shannon divergence and Maximum mean discrepancy and allows to define new divergences that only take into account differences that lead to different choice of optimal actions.
Some basic properties of the new class and a theorem providing error bounds when estimating a divergence from this class from samples are shown.
A two-sample test is proposed using  a permutation approach and some experimental results are provided on standard datasets.

Pros:
- Interesting new divergence class including both JS and MMD allowing to define new divergences with a decision-theoretic perspective
- Useful theoretical results 

Cons:
- I think that the decision-theoretic perspective has a great potential for making two-sample tests more meaningful but unfortunately it is not properly developed.
- Two-sample test presentation lacks rigor
- The experiments are not convincing



The paper is generally well written and the theoretical results seem correct although some proofs are a bit rushed. The experiments are not sufficiently detailed and no code is provided. The idea of generalizing divergences using a decision-theoretic perspective has already been proposed in [Grunwald&Dawid 2004] which is cited for the H-entropy but not for the generalized relative divergence, which should be mentioned. The proposed class of H divergences extending JS and MMD is novel as far as I know.  
What I found especially promising but disappointingly not exploited in the two-sample test section is the following idea : 
"Intuitively, $D^\phi_l$  only takes into account any difference between distributions that lead to different
choice of optimal actions. This property allow us to incorporate prior knowledge about the problem."
I would have liked to see this idea exploited in the two-sample test. Usually nonparametric two-sample tests aim at maximal power and this makes them sometimes not so useful in practice, in the sense that they summarize the output in 1 bit (saying whether p=q)  and don't tell anything about the nature of the difference, which could  be irrelevant under some decision-theoretic perspective.

I recommend rejection since the real interest of this new class is mentioned but not properly shown and the two-sample test part is not strong enough.

Detailed comments:

1) Regarding the structure: \
a) The "definition" part contains all the theoretical aspects of the proposed divergence not only the definition.\
b) The two-sample tests announced in the title only appear in the experimental part: I was expecting a section introducing definitions and literature for a general ML audience.

2) When you define a divergence in section 2.1: \
It would be useful to emphasize that your definition of divergence is broader than the usual in the sense that you can have $D(p,q) = 0$ for  $p \neq q$. 

3) Regarding the choice of $\alpha=1/2$, it would be interesting to the discuss whether it would relevant or not to consider a different $\alpha$ .

4) When $D^\min_\ell$ is defined, it is said that a proof regarding its validity as a divergence is provided later but I can't find such proof.

5) After definition 2, it is claimed that $\phi$  is the most general class function…, but there is no proof.

6) Inconsistent notation between main text and proofs: \
a) $\hat{p}_m$ sometimes used as a set of samples, sometimes as an emprirical distribution which is a different object.\
b) $x''$  seems to define $\hat{r}_m$ but it is not explicitly said

7) The following statement should be more precise in what makes it "impossible" : \
" it is well known that estimating the Jensen Shannon divergence between continuous distributions is impossible with finite data." 

8) You claim that part 1 (p=q) of theorem 2 is particularly useful for the two-sample test but in fact this is irrelevant in a permutation test. Under the null hypothesis (p=q), the distribution of the p-value is determined by the permutation procedure.

9) The two-sample test subsection lacks rigor. In particular:\
a) "The probability an algorithm makes a type I error is called the p-value.": This is not the standard definition of a p-value.\
b) What do you mean by a guaranteed p-value? Exact? Valid? This should be mathematically precise.\
c) In general, permutation tests should be presented with more rigor since there a different ways of doing them see e.g. 
	Ernst, Michael D. "Permutation methods: a basis for exact inference." Statistical Science 19.4 (2004): 676-685.
	
10) Experiments:\
a) MNIST dataset: what are the two samples? Are they the same used in [Liu et al. 2020] where one of them is composed of GAN generated images?\
b) The training sizes should be explicitly specified to be able to compare to two-sample tests that compute the statistic on the whole dataset (e.g.  Hall & Tajvidi. "Permutation tests for equality of distributions in high‐dimensional settings." Biometrika 89.2 (2002): 359-374.) or those that train in an online manner (e.g. Lhéritier & Cazals. "Low-Complexity Nonparametric Bayesian Online Prediction with Universal Guarantees." NeurIPS 2019.)\
c) Figure 2: The numbers seem to correspond to the number of samples per gaussian (9), per population (2) per train/test dataset (2) (from [Liu et al. 2020]) e.g.:  20 samples in your plot means that you used 20x9x2x2=720 samples in total, if I understand correctly. \
d) I am confused by the Blobs and HDGM experiments: by using a gaussian mixture model in your test, I think that you are giving an unfair advantage to your test while at the same time penalizing it "a little bit"  with "mild" mis-specification. The aim of this setup is unclear.\
e) Figure 3: the caption should mention the name of the dataset\
f) Can you give an intuition on why your Parzen density estimation based test is superior to the other kernel methods on the HIGGS dataset? Where the additional power comes from?\
g) Overall, you should clearly justify the action space and the aim of each experiment i.e.: by choosing a specific action space, do you want to make the test more powerful than the contenders by providing it prior knowledge or do you want to tell test that only some type of differences matter (which would make it insensitive to some differences and therefore less powerful in comparison to more general tests)?

11) Proofs:\
a) Proposition 2: the proof seems to be incomplete. the last line implies that the JS is strictly positive but it doesn't seem to prove the claim for the general H-divergence.\
b) Theorem 2: sub-sampling mixture should be properly defined, I guess it corresponds to x'' in section 3.5\
c) Theorem 2: \
c1) you should clarify how you define the empirical distributions in the multivariate case \
c2) it would be helpful for the reader to explictly mention the properties used in the different derivations: 1-lipschitz, union bound, triangular inequality…\
c4) Citation of (Shalev-Shwartz & Ben-David, 2014) should be more precise\
c3) Lemma 3: First sentence: the second "consider"  should be removed I think.
	
Typos:\
-- diveRgence : in the abstract\
-- we are able to recover a distance that workS\
-- that ~~have~~ have a density.\
-- 100 permutationS\
-- Last line of the proof of Lemma 2: $\ell$ should appear instead of $\mathcal{V}$\
-- Proof of theorem 1 says $V$ divergence instead of $H$ Jensen Shannon Divergence\
-- Proof of theorem 2: $\hat{D}_\ell^\phi(p \Vert q)$ should be $\hat{D}_\ell^\phi(\hat{p}_m \Vert \hat{q}_m)$.

=====POST-REBUTTAL COMMENTS======== 

I thank the authors for the response and the efforts in the updated draft, in particular with respect to :
- the new experiment (complementing the original one on blobs) whose results are reassuring 
- corrections and improvements in the proofs
- the new experiment on climate change 

The two-sample test part has been modified to take into account some of my comments but still lacks rigor. It doesn't explain the permutation procedure used and whether the p-values are just valid or exact. Now, the term "significance level" (replacing "p-value") is used to refer to the probability of type I error, which is not totally accurate in general. If the p-values are just valid and not exact, the significance level is a bound on the type I error. This should be fixed in the final version. 

Regarding my main concern, i.e. showing the interest of a decision-theoretic divergence using some custom loss, the new experiment on climate change is a good illustration of the interest of such divergences.

In summary, I see useful theoretical results and a step in this not-much-explored direction of tailoring divergences and two-sample tests with a decision-theoretic perspective, i.e. "detecting differences that matter", and thus I decided to raise my score.

review_title: Interesting generalization of JS and MMD divergence but two-sample test part not convincing

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

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