Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Applications of Wasserstein distance to large-scale machine learning problems have been limited by its enormous computational cost. The Sliced Wasserstein (SW) distance and its variants increase computational efficiency using random projections but suffer from low accuracy if the number of projections is not large enough. In this work, the authors propose a new family of sliced-Wasserstein distance measures, called Hierarchical Sliced Wasserstein distances (HSWDs). 

HSWDs are based on projecting original measures into $k$ one dimensional projected measure via Radon transform with $k\ll L$ and where $L$ is the number of projections. Towards this end, the authors define hierarchical Radon transform, which has an injectivity property. This latter yields the metricity property of HSWDs. Several numerical experiments in generative modeling are conducted on CIFAR10, CelebA and Tiny ImageNet datasets.
strength_and_weaknesses: ### Strength ###
- HWD: novel variant of sliced Wasserstein distance based on a hierarchal Radon transform.
- HWD is a proper distance in the space of probability measures.
- Equivalence between HWD, SWD, and Max-SWD.
- Numerical experiments on generative modeling with HWD.

### Weaknesses ###
- In most experiments, the number of projections $L$  is taken significantly large. So, this affects badly the computational cost of calculating the linear mixing of the bottleneck projections. This mean, at last for me, HWD gains efficiency with a price of a large number of projections. At that time, one can consider vanilla SWD. I will appreciate it if the authors give more details about this point. 
- The paper lacks comparison with other approaches like augmented sliced Wasserstein (Chen et al. ICLR 2022) and distributional sliced Wasserstein (Nguyen et al. ICLR 2021).
clarity,_quality,_novelty_and_reproducibility: The code is attached to the supplementary materials. I thank the authors for that. Reproducibility of results is guaranteed.
The paper is easy to follow and well-explained. 

### Typos ###
- Page 1: "sample complexity": it is a little bit confusing, since this term we use for the number of training samples that we need to supply to a learner algorithm. It will be better if the authors clarify this point as the bounding gap between the evaluation of divergence on two probability measures versus samples from these measures. 
- Page 5: "success of overparametrization in DNN" (Add a reference or details).
- Page 7: "while comparing HSW with the SW.e experiments while comparing the HSW with the SW" --> "while comparing the HSW with the SW"
- References: "radon" --> "Radon"

summary_of_the_review: the paper introduces novel variants of sliced Wasserstein distance to reduce the computational cost. The paper lacks comparison with other approaches like augmented sliced and/or distributional sliced Wasserstein distances.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper introduced a new variant of sliced Wasserstein (SW) distance, the hierarchical sliced Wasserstein (HSW) distance. The HSW distance is derived based on the proposed hierarchical Radon transform (HRT), which is a composition of partial Radon transform and overparametrised Radon transform. In the HSW, compared probability measures are first projected onto k bottleneck directions, yielding new probability measures $f_\mu(t_{1:k}, \theta_{1:k})$ and $f_\nu(t_{1:k}, \theta_{1:k})$, then the generated measure are projected onto a one-dimensional space using the partial Radon transform (PRT) in a $k$-dimensional subspace with L directions $\psi$. The HSW is defined as the expectation of Wasserstein distances between the obtained one-dimensional probability measures over the distribution of $\theta_{1:k}$, a product probability measure of k uniform distributions on d-dimensional unit spheres, and the distribution of $\psi$, a uniform distribution on a k-dimensional unit sphere. In short, final projections in the HSW are linear combinations of the k bottleneck projections, and the weights of the k projections are given by L random samples drawn from a uniform distribution on a k-dimensional unit sphere.
strength_and_weaknesses: Strength:

Theoretical properties of the HSW are derived in the paper, including its metricity, its link to SWD, max-SWD, approximation error of HSW, and computational complexity. Compared with the standard SW distance, the proposed HSW has the advantage of lower computational cost when both the data dimension and the number of final projections are much larger than the number of bottleneck projections k.

The proposed HSW is evaluated on a benchmark deep generative modelling experiments to compare it with other variants of SWDs. Experiment results show that models trained with HSW can produce images of higher qualities in terms of FID and IS scores. The HSW also demonstrated higher convergence rate with approximately the same computational costs than SWD.

Weakness:

My major concern is on the experiment side. The main context of the proposed work is to improve computational efficiency of the optimal transport-based distances, in particular sliced-based ones, but the proposed HSW is only compared with the standard SWD, ignoring most of the recent efforts which were also discussed in the paper. The proposed method is also only evaluated on a generative modelling experiment, but other applications of slice-based Wasserstein distances can be found in other related papers, e.g., colour transferring and sliced iterative normalising flows [1][2].

[1] Soheil Kolouri, et al. "Generalized Sliced Wasserstein Distances." NIPS, 2019.
[2] Biwei Dai, and Uros Seljak. "Sliced Iterative Normalizing Flows." ICML, 2021.
clarity,_quality,_novelty_and_reproducibility: The paper is well written and easy to read. The proposed method is novel and clearly explained.

Questions:
(1) How are the computational complexity and project complexity are computed? What are the units of those complexities as reported in Tables 1 and 2?
(2) The proposed HSW is constructed by recursively applying PRT and ORT to compared measures, is it possible to stack more PRTs and ORTs to construct SWD variants in the same way as in the HSW? Would they still be distance metrics? And what are their computational complexities compared to the HSW?
(3) What is the performance of the HSW when H>1?

summary_of_the_review: The paper can be improved if more comprehensive experiments are included to support the effectiveness of the proposed method.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes an extension of the Sliced Wasserstein (SW) distance, denoted as Hierarchical Sliced Wasserstein (HSW) distance. At its core, for $d$ dimensional samples and $L$ slices, HSW first chooses $k$ bottleneck projections and then applies $L$ linear projections on the $k$ bottleneck slices, leading to slicing complexity of $\mathcal{O}(k(d+L))$ compared to $\mathcal{O}(dL)$ of the SW distance. The need for such hierarchical slices comes from deep learning applications where the number of samples $n$ (in mini-batch processing) is often smaller than their dimensionality $d$, and the computational complexity of the SW distance is dominated by the projection complexity. The more interesting part of this paper is the definition of Overparameterized Radon (OR) transform and its combination with the Partial Radon (PR) transform that results in the proposed Hierarchical Radon transform used to show that the proposed HSW is indeed a metric. Lastly, the authors demonstrate the application of HSW and compare it with SW for generative modeling on CIFAR10, CelebA, and Tiny ImageNet. They show boosts over FID and IS for different numbers of slices $L$ while demonstrating that HSW is faster than SW.  
strength_and_weaknesses: ### Strengths: 

* The paper is well-written and well-motivated.
* The paper is theoretically sound, and the experiments support the authors' claims.
* While conceptually simple and algorithmically trivial to implement, the approach is well supported by the theory of the proposed Hierarchical Radon transform, rooting the simple algorithm into the solid mathematical ground.
* The ablation study in Table 2 is really great! 

### Weaknesses: 

I do not see any major flaws in this paper. However, below are some of the points that, in my opinion, could have improved the paper: 

* When defining the Max-HSW variation, the maximization could be performed on the $k$ bottleneck slices (I find this very interesting), on the $L$ linear combinations of the bottleneck slices, or jointly (as it is currently defined in the paper). It would have been exciting to see the effect of only maximizing over the $k$ bottleneck slices. Moreover, it seems that one should require the $k$ bottleneck slicers to be linearly independent; what enforces this constraint?

* I am not sure if I follow these sentences: "Since HGSW has more than one non-linear transform layer, it has the provision of using a more complex non-linear transform than the conventional Generalized sliced Wasserstein.  Compared to the neural network defining function of GRT, HGSW preserves the metricity." As far as I can see, if any of the projections (i.e., the $k$ bottleneck or the $L$ following slices) become nonlinear, then the metricity of HGSW would also depend on the defining functions and the injectivity of the (in this case) generalized hierarchical Radon transform. Could you please clarify this?

* Currently Propositions 1 and 2 could read as if $HRf$ and $HRg$ are equal for **some** $\theta_{1:k}$ and $\psi$ then $f=g$, which I am sure we agree that is not true. I think what the proposition is saying is if $HRf(\cdot,\theta_{1:k},\psi)=HRg(\cdot,\theta_{1:k},\psi)$ for $\forall \theta_{1:k}, \psi$ then $f=g$. Maybe rewording the propositions could increase the clarity. 

### Minor editorial: 

Typo - Page 3: "the set of absolutely integrable function on" should be "the set of absolutely integrable functions on"

clarity,_quality,_novelty_and_reproducibility: * The paper is well-written, and the concepts are crystal clear.

* The paper is of high quality. 

* The proposed concept and the resulting algorithm are very simple and practical. The Overparametrized Radon and the Hierarchical Radon transforms are novel and could be of interest to the community. 
summary_of_the_review: Overall, I think the paper is well-written, and it addresses a valid challenge for the application of sliced-Wasserstein distance in training neural networks when using small mini-batches. The proposed method is algorithmically simple, yet it is mathematically rigorous, and it provides a significant improvement over the SW distance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper introduces the Hierarchical Sliced Wasserstein (HSW) distance that is a variant over the Sliced Wasserstein (SW) distance.
In a nutshell, the HSW distance improves on the computational complexity of SW in cases where $d \gg n$ by lowering the burden related to the projections.
To do so, projections on subspaces of dimension $k$ is performed and the final $L$ projections are projections from this $k$-dimensional space to the real line.
Both properties of this HSW and experimental validation on generative modeling tasks are presented.
strength_and_weaknesses: * Strengths
    * The method is sounded.
    * The paper is well motivated. Notably, the introduction clearly states the contribution of the paper, and is easy to read despite the technicity of the proposition
* Weaknesses
    * The paper is already very dense (_eg._ parts of the experimental results discussed in the paper are only available as supplementary material) yet it raises several questions that would be worth investigating in the paper.

In more details, I really enjoyed reading the paper and believe the contribution is interesting.
However, I have the following remarks / questions:
* The paper is already dense, and I get that one has to make choices, but I believe an application of HRT on other sliced divergences would have helped illustrate the genericity of the proposition (though the matter is discussed in the paragraph "Applications of HRT").
* Do we have any intuition for a link between HSW and SW (apart from the links exhibited in Proposition 3 between HSW and Max-SW -- resp. SW and Max-HSW)?
    * When reading Proposition 3, it is unclear to me why Max-HSW would differ from Max-SW since, in spirit, they both correspond to taking the max over projections on a line. This is probably due to a misunderstanding on my side, but maybe adding a discussion on this point could help the reader better grasp the difference between those two.
    * This is also related to the discussion on "Distributions of final projecting directions in HRT", which concludes:
        > To our knowledge, the manifold $\mathcal{S}$ has not been explored sufficiently in previous works, which may be a potential direction of future research"
        * I believe providing informed thoughts on properties of this manifold would be a real plus for this paper.
* The section on the benefits of HSW when $d \gg n$ is not very convincing since all complexities are said to be "proportional to XXX". Either the constant is the same for all and this should be stated clearly or a quantitative study of the running times as a function of $L$ would be welcome.
    * This is also reflected in the experiments: could the "computational complexity" criterion be replaced by running times to make sure that in Table 1, for example (but this holds for other results too), each sub-group of methods indeed corresponds to cases where the HSW computation is cheaper and nothing is hidden in the $\mathcal{O}(\cdot)$ notations. The same applies to the "Projection complexity" criterion.


I have a few extra minor comments:
* "which has columns are" -> "which columns are"
* [Titouan et al., 2019] -> [Vayer et al., 2019]
* End of Section 3: the last sentence ends weirdly, probably a bad copy-paste
* In Figure 3, using markers could help identify paired methods (which HSW variant corresponds, in terms of computation, to which SW variant)
* "In the Table 2, we reports" (p. 8) -> report
clarity,_quality,_novelty_and_reproducibility: The paper is well-written, of good quality and the information provided in the paper should be sufficient to reproduce the experiments, I believe.
summary_of_the_review: The proposed method is very interesting and the paper is well-written.
I would appreciate more details in places (see previous section) and a comparison of complexity based on running times to make sure the comparison is fair.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper introduces an extension of the sliced wasserstein distance that has reduced complexity.  Authors analysed the theoretical properties of this novel distance by introducing extensions of the Radon transform. 
Experimental results confirm the usefulness of the proposed approaches but I may have been helpful to have an in-depth comparisons (see reviewers comment).

 Most reviewers agreed that the paper is interesting and relevant and the revised version of the paper added some experiments related to 
color transfer which improved the experimental part. However, the paper would benefit from further empirical evaluation
and comparison with plain SWD in other practical applications.
justification_for_why_not_higher_score: * lack of  large-scale/in-depth empirical evaluations
justification_for_why_not_lower_score: the paper proposes a novel and interesting contribution relevant to the ML community
Decision: Accept: poster