Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################

Summary: This work proposes the max-sliced Bures (MSB) distance, a distance metric for comparing probability distributions. This work adds to the existing literature on transport based slicing techniques for comparing probability distributions, such as sliced-Wasserstein (SW), max-sliced-Wasserstein (MSW), generalized sliced Wasserstein (GSW).

Novel applications in (1) interpreting datasets and (2) critiquing generative models are claimed due to the assignment of energy-based scores to instances, which allows identification of specific subsets that are not well-matched.

The authors present several experiments demonstrating their technique
(1) detecting class-imbalance [Figure 2] 
(2) identifying under/over-represented data subsets in GAN generative models [Figure 3]
(3) detecting "covariate shift outlier detection" [Table 2]
(4) identifying covariate-shift through reweighting on synthetic CIFAR-10 [Figure 4]
(5) distribution matching on toy distributions (grid of 25 Gaussians) [Figure 5]

##########################################################################

Reasons for score: 

Overall I vote for acceptance, but with some reservations on the experiments. 
 
I found the mathematical analysis to be interesting and a potentially valuable contribution to the ML literature on probability distance. I did not check the math in detail, but the authors appears to know what they are talking about.

I was intrigued by the claimed applications. The technique is sold as a tool for (1) interpreting datasets (2) critiquing generative models. The community could benefit from more such tools. 

At first read I found the empirical results lacking, but after a second reading I concluded they are reasonable. As I understand it, one difficulty that arises in interpreting the experiments is their novelty, i.e. at present there is no standard set of experiments for these applications. This seems unavoidable, but I have still have some doubts whether these experiments are optimal.

What I was hoping to see was a compelling demonstration of the technique on common problem arising in the practice of machine learning.  For instance in the conclusion the authors write "Additionally, the one-sided max-sliced Bures divergences ... can be used to identify systematic discrepancies such as **mode dropping**" [emphasis mine]. 


##########################################################################

Pros: 
* Interesting mathematics
* Important problem

##########################################################################

Cons: 
* Some difficulty in interpreting experiments
* More compelling applications (e.g. solving mode-dropping are desired)
* Comparison with other methods where possible seems weak (Figure 5)

##########################################################################

Questions during rebuttal period: 

Mode-dropping is a very common problem. Can the authors show an example on which their technique identifies and helps solve mode dropping? 

Figure 5 compares max-sliced Bures (cases C,D) against max-sliced W2 (case A,B) on matching a grid of Gaussians starting from uniform, an example taken from Kolouri et al. (2019). Qualitatively, case D beats case B. Why didn't the authors consider the other cases (8 circular Gaussians, swiss-roll, half-moons, circle) as in Figure 2 Kolouri et al. (2019)? 

#########################################################################

Additional Feedback:

A code release will  improve this submission.

#########################################################################

POST-REBUTTAL RESPONSE:

I found the author's further work on (1) the mode-collapse experiments (2) quantitative comparisons with other slicing methods interesting and convincing. I have decided to increase my score. I reiterate that I have not checked the mathematical content of this paper in detail.
review_title: Interesting work on relevant problem, but I am left desiring more compelling applications

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper studies a family of integral probability metric (IPM) divergence on Hilbert spaces. This family can be characterized by the choice of the witness function, and specific witness function may give rise to the Bures distance, the MMD, Wasserstein, as well as many sliced variants. While this family has been well understood for distributions on finite dimensional space, this paper extends this insight to distributions on (possibly infinite dimensional) Hilbert space. By leveraging the representer theorem, the paper provides the finite dimensional optimization problems that can be solved to estimate the divergence from samples. The power of the method is demonstrated on the covariate shift experiments.

Positive points:
1. Extending previous results of IPM-type distance to the Hilbert space is a natural ideas. There are in fact many applications that can be nicely solved in the RKHS framework, and thus novel divergences that can substitute the MMD is desirable. The results can boost further learning tasks, and thus are relevant to the machine learning community.

Negative points:
I find that the exposition of this paper is extremely difficult to follow, and this downplays the contributions of this paper.

1. The title is misleading: the title implies that the paper will study the max-sliced Bures distance in-depth. However, the content of the paper is a general (more width and depth) on a general family of IPM on RKHS.
2. All results of this paper is provided in Section 2, and there is a tremendous difficulty to identify which results are from the literature, and which results are new in this paper.
3. From the theoretical viewpoint, it is still not clear to the reader why a divergence on a Hilbert space is necessary. Is it because of the possibility to have better sample complexity?

I think that the paper contains good results, but the paper needs to be thoroughly restructured. Currently, the main results of the papers are included in the Appendix. These results (theorems) should be streamlined into the main text. The introduction should be rewritten with a clear exposition of the contributions.

Minor comments:
- In page 5, the authors claim that a "local ascent algorithm will often yield the global optimum". Can the authors clarify how "often" is this? Otherwise, I would recommend to refrain from making unquantifiable claims.
- The first two lines in page 6 is difficult to parse.
- The word "optimizations" should be replaced by "optimization problems"

review_title: Good paper but the exposition is difficult to follow

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:

This paper proposes a sliced version of the Bures distance, which is a lower bound on the 2-Wasserstein distance. The purpose behind this is to identify instances that are have the highest contribution towards the discrepancy between two distributions. But compared to other sliced OT distances, this one operates on a the Bures lower bound, which yields a more tractable solution. The paper presents experimental results on image classification datasets, which are claimed to show an advantage of the proposed variant over the full sliced Wasserstein distance .

Strengths:
* Timely and relevant problem: designing faster, sliced versions of OT distances is a very active area of research
* Some interesting ideas, and lots of connections to other distances

Weaknesses:
* Limited novelty. This paper heavily builds on recent work on sliced wasserstein distances (e.g. Kolouri), and combines it with recent work on OT on RKHS (Zhang et al)
* Clarity/Intuition. Various aspects of the paper could be better motivated, discussed and analyzed (see below).
* Unconvincing / confusing experimental evaluation, misses necessary quantitative experiments and includes two many qualitative ones 

Detailed comments:
* The original sliced and max-sliced Wasserstein distances are never introduced here, which is surprising given how closely related they are. I would suggest prioritizing this over other (perhaps unnecessary) aspects of the background present in sections 2.1 and 2.2.
* The introduction of the proposed distances (6, 7, 8) could be better motivated. E.g., it is not immediately clear why (7) corresponds to a sliced version of (4). Going through the derivations in the Appendix sheds some light on this, but given that the main contribution of the paper is all contained in section 2.3, one would expect a more thorough discussion and presentation of this contribution
* Introducing RKHS and then falling back to finite dimensional embeddings (2.5.1) feels like an overkill. Also, under this setting, how is this different from just embedding all samples as a pre-processing step and then using the usual sliced Wasserstein?
* As for any lower/upper bound on a distance, the first question that the experiments should try to answer is: "how tight / good approximation is this bound"? Such an experiment is necessary to gauge the approximation-quality tradeoff that such a lower bound entails. In this case, I would have expected to see a vis-a-vis comparison of the three proposed distances, and the original sliced Wasserstein ones, on synthetic datasets of increasing size, to get a sense of their asymptotic behavior
* It might be just me, but I find the setup of the experiments in 3.1 very confusing, and have a hard time parsing the results. E.g. why is the one-sided version of the m-s-Bures distance used here? Is the plot on the right the usual sliced Wasserstein distance or the kernel one? Why is a first-moment approximation used? What is the relevance of the x-axis used here?
* A good chunk of the experimental results are purely qualitative and rely on the user comparing specific instances of images (Fig 3 and 4). Leaving aside the fact that the size/resolution is pretty small, I'm not sure what I'm looking for here. What should one expect to see here? Are these results good or bad? 
* The covariate shift detection experiments suffer from a similar lack of explanation for the various experimental design choices (e.g., why/how were these scenarios chosen?). In addition, the results exhibit very very wide s.d. confidence intervals, to the point that all the max-sliced distances have intersecting intervals, making it almost impossible to draw any statistically significant results from this table. 
review_title: Simple extension of sliced Wasserstein distance, with some interesting ideas but lacking in motivation, clarity and evaluation 

Meta-review: The goal in this submission is to find interpretable samples discriminating two probability distributions. In order to tackle this task the authors propose to use a sliced variant of the Bures distance (where the slicing is implemented via a one-rank tensor) and the associated witness function, and illustrate the idea in the discrimination task of fake and real images, and in the detection of covariate shift. 

Interpretable discrimination of probability measures with witness functions is a hot topic of machine learning with a large number of applications and available tools (including linear time ones in the sample size, and methods capable of handling independence testing, goodness-of-fit testing, relative tests among others, beyond the considered two sample setting). 

1)The motivation of the paper and the efficiency of the proposed method compared to available baselines are not clear; the relevance of the demos is questionable. 
2)Unfortunately, the submission also lacks mathematical contributions: for instance 
i)Is the proposed divergence a semi-metric or metric, and under what conditions on the domain and the kernel?
ii)Does the proposed estimator converge, under what assumptions, and how quickly (rates)?

The contribution represents a potentially interesting idea, but significantly more work is needed before publication.
Decision: Reject