Hierarchical Sliced Wasserstein Distance
Authors: Khai Nguyen
Tongzheng Ren
Huy Nguyen
Litu Rout
Tan Minh Nguyen
Nhat Ho
Venue: ICLR 2023 poster (2023)
Keywords: Sliced Wasserstein
Radon Transform
Optimal Transport
Generative Models

Abstract: Sliced Wasserstein (SW) distance has been widely used in different application scenarios since it can be scaled to a large number of supports without suffering from the curse of dimensionality. The value of sliced Wasserstein distance is the average of transportation cost between one-dimensional representations (projections) of original measures that are obtained by Radon Transform (RT). Despite its efficiency in the number of supports, estimating the sliced Wasserstein requires a relatively large number of projections in high-dimensional settings. Therefore, for applications where the number of supports is relatively small compared with the dimension, e.g., several deep learning applications where the mini-batch approaches are utilized, the complexities from matrix multiplication of Radon Transform become the main computational bottleneck. To address this issue, we propose to derive projections by linearly and randomly combining a smaller number of projections which are named bottleneck projections. We explain the usage of these projections by introducing Hierarchical Radon Transform (HRT) which is constructed by applying  Radon Transform variants recursively. We then formulate the approach into a new metric between measures, named Hierarchical Sliced Wasserstein (HSW) distance. By proving the injectivity of HRT, we derive the metricity of HSW. Moreover, we investigate the theoretical properties of HSW including its connection to SW variants and its computational and sample complexities. Finally, we compare the computational cost and generative quality of HSW with the conventional SW on the task of deep generative modeling using various benchmark datasets including CIFAR10, CelebA, and Tiny ImageNet.

Published as a conference paper at ICLR 2023
HIERARCHICAL SLICED WASSERSTEIN DISTANCE
Khai Nguyen
Tongzheng Ren
Department of Statistics and Data Sciences
Department of Computer Science The University of Texas at Austin Austin, TX 78712
The University of Texas at Austin
Austin, TX 78712
Khainbeutexas.ed.
tongzheng@ wteaas edu
Huy Nguyen
Litu Rout
Department of Statisties and Data Sciences The University of Texas at Austin Austin, TX 78712
Department of Electrical and Computer Engineering The University of Texas at Austin Austin, TX 78712
huynm@utexas.ce
Tan Nguyen
Nhat Ho
Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095
Department of Statistics and Data Sciences The University of Texas at Austin Austin, TX 78712
tanmnguyen8 9eucla......... edu
minhnhat eeteaaattueeess....mmm edu
ABSTRACT
Sliced Wasserstein (SW) distance has been widely used in different application sce- narios since it can be sealed to large number of supports without suffering from the curse of dimensionality. The value of sliced Wasserstein distance is the average of transportation cost between one-dimensional representations (projections) of origi- nal measures that are obtained by Radon Transform (RT). Despite its efficiency in the number of supports, estimating the sliced Wasserstein requires relatively large number of projections in high dithemimeniionl settings. Therefore, for applications where the number of supports is relatively small compared with the dimension, e.g., several deep learning applications where the mini-batch approaches are utilized, the complexities from matrix multiplication of Radon Transform become the main computational bottleneck. To address this issue, propose derive projections by linearly and randomly combining a smaller number of projections which are named bottleneck projections. We explain the usage of these projections by intro- ducing Hierarchical Radon Transform (HRT) which is constructed by applying Radon Transform variants recursively. We then formulate the approach into new metric between measures, named Hierarchical Sliced Wasserstein (HSW) distance. By proving the injectivity of HRT, derive the metricity of HSW. Moreover, we investigate the thcoretical properties of HSW including its connection to SW variants and its computational and sample complexities. Finally, we compare the computational cost and generative quality of HSW with the conventional SW on the task of deep generative modeling using various benchmark datasets including CIFAR10, CelebA, and Tiny ImageNe(")
INTRODUCTION
Peyré & Cuturi 2020) has been widely used in applications, such as generative modeling on images (Arjovsky al. 2017 Toistikhin et al. 2018 litu Rout et al. 2022), domain adaptation to transfer knowlede ledge from source to target domains (Courty et al.
Wasserstein distance (Villani 2008
2017
Bhushan Damodaran et al. 2018), clustering problems (Ho et al. 2017). and various other
'Code for experiments in the paper is published at the following link https //gi thub.
Austin-bate Sci Pance-Grrup/HS/

---

Published as a conference paper at ICLR 2023
applications (Le et al. Wasserstein distance in applications, prior works have alluded to the concerns surrounding the high computational complexity of that distance. When the probability measures have most supports, the computational complexity of Wasserstein distance scales with the order of On log n) (Pele & Werman 2009). Additionally, it suffers from the curse of dimensionality, i.e., its sample complexity (the bounding gap of the distance between probability measure and the empirical measures from its random samples) is of the order of On 1ld) (Fournier & Guillin 2015), where n. is the sample size and dl is the number of dimensions.
2021 Xu et al. 2021 Yang et al. 2020). Despite the increasing importance of
Over the years, numerous attempts have been made to improve the computational and sample complexities of the Wasserstein distance. One primal line of research focuses on using entropic regularization (Cuturi) 2013). This variant is known as entropic regularized optimal transport (or in short entropic regularized Wasserstein). By using the entropic version, one can approximate the Wasserstein distance with the computational complexities (n²)) (Altschuler et al. 2017 Lin et al. 2019b 2020) (up to some polynomial orders of approximation errors). Furthermore, the sample
complexity of the entropic version had also been shown be at the order of (nn11/2 (Mena &
Weed 2019), which indicates that it does not suffer from the curse of dimensionality.
Another line of work builds upon the closed-form solution of optimal transport in one dimension. A notable distance metric along this direction is sliced Wasserstein (SW) distance (Bonneel et al. 2015). SW is defined between two probability measures that have supports belonging to a vector space. e.g, R. As defined in (Bonneel et al. 2015). SW is written as the expectation of one die-dimesioona Wasserstein distance between two projected measures over the uniform distribution on the unit sphere. Due to the intractability of the expectation, Monte Carlo samples from the uniform distribution over the unit sphere are used to approximate SW distance. The number of samples is often called the number of projections that is denoted L. On the computational side, the projecting directions matrix of size d x L is sampled and then multiplied by the two data matrices of size n x resulting in two matrices of size n L that represent L -iedimmesioonl projected probability measures. Thereafter, -in-dimensional Wasserstein distances are computed between the two corresponding projected measures with the same projecting direction. Finally, the average of those distances yields an approximation of the value of the sliced Wasserstein distance.
Prior works (Kolouri et al. 2018a Sa number of projections T. should be large enough compared to the dimension d for a good performance of the SW. Despite the large L, SW has lots of benefits in practice. It can be computed in O(n logz n) time, with the statistical rate (n/122 that does not suffer from the curse of dimensionality, while becoming more memory efficien" compared with the vanilla Wasserstein distance. For these reasons. has been successfully applied in several applications. such as (deep) generative modeling (Wu) ett al., 2019; Kolouri et al.) 2018a;; Nguyen & Ho (022a), domain adaptation (Lee et al. 2019p. and clustering (Kolouri et al. 2018b). Nevertheless, it also suffers from certain limitations in, e.g.. deep learning applications where the mini-batch approaches (Fatras et al.) (020) are utilized. Here, the number of supports n is often much smaller than the number of dimensions. Therefore, the computational complexity of solving L one-dimensional Wasserstein distance, { log, n) is small compared to the computational complexity of matrix multiplication O (Ldn). This indicates that almost all computation is for the projection step. The situation is ubiquitous since there several deep learning applications involving processing high-dimensional data, including images (Genevay al. 2018 Nguyen & Ho 2022b), videos (Wu et al. 2019), and text (Schmitz et al. 2018).
Deshpande et al. 2018 2019, Nguyen al. 2021a a b) show that the
Motivated by the low-rank decomposition of matrices, we propose a more efficient approach to project original measures to their one-dimensional projected measures. In particular, two original measures are first projected into k one-dimensional projected measures via Radon transform where k L. For convenience, we call these projected measures as bottleneck projections. Then, new L one-dimensional projected measures are created as random linear combinations of the bottleneck projections. The linear mixing step can be seen as applying Radon transform on the joint distribution of k one-dimensional projected measures. From the computational point of view, the projecting step consists of two consecutive matrix multiplications. The first multiplication is between the data matrix of size x d and the bottleneck projecting directions matrix of size d x k. and the second multiplication is between the bottleneck projecting matrix and the linear mixing matrix of size k x L. Columns of both the bottleneck projecting directions matrix and the linear mixing matrix are sampled
SS does need store the cost matrix between supports.
2

---

Published as a conference paper at ICLR 2023
randomly from the uniform distribution over the corresponding unit-hypersphere. For the same value of L, we show that the bottleneck projection approach is faster than the conventional approach when the values of L and d are large.
Contribution: In summary, our main contributions are two-fold:
1. We formulate the usage of bottleneck projections into a novel integral transform, Hierarchi- cal Radon Transform (HRT) which is the compasition of Partial Radon Transform (Liang & Munson 1997) (PRT) and Overparameterized Radon Transform (ORT). By using HRT, we derive new sliced Wasserstein variant, named Mierarchical sliced Wasserstein distance (HSW). By showing that HRT is injective, we prove that HSW a valid metric the space of probability measures. Furthermore, projection complexity of the proposed HSW distance. Finally, we derive the connection between HSW and other sliced Wasserstein variants, and the sample complexity of HSW.
discuss the computational complexity and the
2. We design experiments focusing on comparing HSW to the conventional SW in generative modeling on standard image datasets, including CIFARIO, 10, CelebA, and Tiny ImageNet. We show that for approximately the same amount of computation, HSW provides better generative performance than SW and helps generative models converge faster. In addition, we compare generated images qualitatively reinforce the favorable quality of HSW.
Organization. The remainder of the paper is organized as follows. We first provide background about Radon Transform, Partial Radon Transform, and sliced Wasserstein distance in Section 2 In Section 3 we propose Overparameterized Radon Transform, Hierarchical Radon Transform, Hierarchical sliced Wasserstein distance, and analyze their relevant theoretical properties. Section F contains the application of HSW to generative models, qualitative results, and quantitative results on standard benchmarks. We then draw concluding remarks in Section 5 Finally, we defer the proofs of key results, supplementary materials, and discussion related works to Appendices.
Notation. For n N. we denote by [n] the set (1,2....,, n.). For any d 2 S := {o Rd ||0||2 = 1} denotes the d dimensional unit sphere, and U((d11) is the uniform measure over $d-1, We denote the set of absolutely integrable functions on Rd as L, (R*) == {f: Rd - R fge (f()]dd < )o). For
denote the set of all probability measures Ed that have finite p-moments (P.))) For m 2 1, we denote f as the product measure of m random variables that follow while A Amm indicates the Cartesian product of m sets A. The Dirac delta function is denoted by 5. For vector X E Rddm, X := (I11 Tmm) Px denotes the empirical measures
m _i=1 8(x= ...). For any two sequences 0, and b,,, the notation a, (b,,) means that on < Cbn for all n 2 1, where C' some universal constant.
BACKGROUND
We first review the definition of the Radon Transform. We then review the sliced Wasserstein distance, and discuss its limitation in high-dimensional setting with relatively small number of supports.
Definition 1 (Radon Transform (Helgason 201 The Radon Transform R L, LR(RR) -
L, (IR x $d-1) is defined as: (Rf)(1,)) = Jn f(z)o(1- (x, )dr. Note that, the Radon Transform
defines a linear bijection.
Sliced Wasserstein distance: From the definition of the Radon Transform, we can define the sliced Wasserstein distance as follows.
Definition 2 (Sliced Wasserstein Distance (Bonneel et al. 2015)). For any p 2 and dimension d 2 1, the sliced Wasserstein-p distance between two probability measures E (P)(d)) and E (Rd) is given by:
SW (H, (Be-e1ss-1 (RR
where fo()),(()) are the probability density functions of μ. v respectively, and Wo(,vv) iiffret(u.)) ||||- gll & Cuturi 2019). With slightly abuse of notation, use Wa Wp(Hi,) and W Wplsps fa Jo) interchangeably.
the Wasserstein distance of order p Villanii 2008 Peyre
3

---

Published as a conference paper at ICLR 2023
I 2
lef
2 x-e
K frr Aiiinn so0 Kinaaa
è d g
Fr RR
X e gen
Pb
WHIRA -g) (R66)) (ND
WHIRLY oo (RI)
Y 2
gua fix fix
WARLL Pec (RAAG REID
R
y=y-8
Figure 1: The Monte Carlo estimation conventional sliced Wasserstein distance with L projections.
The main benefit of sliced Wasserstein is that the one-dimensional Wasserstein distance W, ((Rf)((, (Rf))()))) has closed-form (Jo I (a))())))))))))))))))) ((R())(..)) (=) where F (1 (2) is the inverse cumulative distribution function of the random variable that has the density (R, (similarly for F (() We denote the one-dimensional pushfor- ward measures with the density (R.fu((: 8) as 8tj..
Sliced Wasserstein distance between discrete measures: In several applications, such as deep generative modeling (Deshpande et al. 20188] Nguyen & Ho 2022b). domain adaptation (Lee et al.) 2019), point cloud reconstruction (Nguyen et al. 2021c] 2023a), sliced Wasserstein distance had been used for discrete measures. Let two measures and y that have the pdfs (x) = Ei=1 a,5(x - vi), fv) = 1 ΣØ= 3,ō(y Vi) (a,, Bg > 0 j), and a given projecting direction O E Sd the corresponding Radon Transform are (Z, 0) E. a,,(2 0 x.) and (R.f)(z, 0) m Σラ= B5 T oy)). Since the expectation in Definition is intractable, Monte Carlo estimation is used with L projecting directions .1.....01 1)
1 T. Σ WB (()
SW (W,,,
We denote X as the matrix of size X d which has being supports of μ., [x1,.... In. [T,]T Y as the matrix of size m x d which has rows being supports of v, [yn....., of size d L. which has columns being sampled projecting directions (0,,..., 0z). The supports of the Radon Transform measures from μ and are the results of matrix multiplication X = X O (with the shape X L) and Y Y- θ (with the shape x L). Columns of X and Y are supports of projected measures. Therefore. L one- dieeeenniiooal Wasserstein distances are computed by evaluating the quantile functions which are based on sorting columns. visualization given Figure !
Umm] ] and Q as the matrix
Computational and projection complexities of sliced Wasserstein distance: Without the loss of generality, we assume that 2 m, the time complexity of sliced Wasserstein O(Lnn Ln log, n) where Ldn is because of matrix multiplication (X +) and Ln log, is because of the sorting algorithm. The projection complexity of SW is the memory complexity for storing the projecting directions θ which is ((Ld). We would like to remark that, the value of number of projections L should be comparable to the number of dimension for a good performance in applications (Deshpande et al. 2018 Nguyen et al.) 20
Computational issuse of sliced Wasserstein when d > n: In deep learning applications (Deshpande al. 2018 Lee al.) 2019: Kolouri al. 2018a) 8a) where mini-bater approaches are used, the number of dimension d is normally much larger than the number of supports n,, e.g., d = 8192 and n = 128. Therefore, log, n < d that leads to the fact that the main computation of sliced Wasserstein is for doing projecting measures O (Ldr). To the best of our knowledge, prior works have not adequately addressed this limitation of sliced Wasserstein.
HIERARCHICAL SLICED WASSERSTEIN DISTANCE
In this section, we propose efficient way to improve the projecting step of sliced Wasserstein distance. In particular, we first project measures into a relatively small number of projections (k), named boutleneck projections (k < L.). After that, J. projections created by random linear
4

---

Published as a conference paper at ICLR 2023
combination of the bottleneck projections. To explain the usage of the bottleneck projections, first introduce Hierarchical Radon Transform (HRT) in Section We then define the Hierarchical Sliced Wasserstein (HSW) distance and investigate its theoretical properties in Section 3.2 We show that the usage of bottleneck projections appears an efficient estimation of HSW.
3.1 HIERARCHICAL RADON TRANSFORM
To define the Hierarchical Randon Transform, we first need to review an extension of Radon Transform which is Partial Radon Transform (PRT). After that, we propose novel extension of Radon Transform which is named Overparameterized Radon Transform (ORT).
Definition 3 (Partial Radon Transform (Liang & Munson, 1997g). The Partial Radon Transform (PRT) PR: T. (R24 x RR2) - Ln (TR x Sú, x k22) is defined as: (P,. 0, = =fue, f(x, y)8(1 (r, 0)) Given a fixed y, the Partial Radon Transform is the Radon Transform of f(-.)).
Definition 4 (Overparameterized Radon Transform). The Overparameterized Radon Transform (ORT) OR: IL (Bd) Li (R &((d-100k) is defined as:
k 8(t, (z, 0.) da,
{ f(x)(
(ORf)(tia, = JA
II
(3)
1=1
where t1sk == (li,...., 4x) E Ro* and 01. == (0I...., 0s) E (8u-1)S*.
Definition 4 is called "overparameterized"" since the dimension of the transformed function's argu- ments is higher than the original dimension. Our motivation for ORT comes from the success of overparametrization in deep neural networks (Allen- Zhu et al. 2019).
Proposition The Overparameterized Radon Transform (ORT) injective, i.e., for any functions f.g EELL L'' (RR)), (ORf)( 01:k) (ORg)) (1:k) Vti:k, 01:k implies that f = 9.
Since ORT is an extension RT, the injectivity of ORT is derived from the injectivity of RT. The proof of Proposition D iis in Appendix C.1
We now define the Hierarchical Radon Transform (HRT).
Definition 5 (Hierarchical Radon Transform). Hierarchical Radon Transform (HRT) HR (RR") + L1 (R x S(d-1)0k x 1)-
1) is defined as:
(H, A.n. (8) J f(x)) (V- (0, 0:) dr.
(4)
where u E R. 1/ (v.......u tha) E sh and 01.6 = (0I,..., 0k) E (Id-1)
Definition is called "hicrarchical" since it is the composition of Partial Radon Transform and Over- parameterized Radon Transform. We can verify that (HR,) (v, 014 e- = (PR(OR))) (v, 0 v) (we refer the reader Appendix for the derivation). To the best of our knowledge, ORT and HRT have not been proposed in the literature.
Proposition 2. The Hierarchical Radon Transform (HRT) is injective, i..., for any functions f.g e L (IR),, (v, 0 v = (H, 0 v) Yv, 0 y implies that f g.
Since HRT is the composition of PRT and ORT, the injectivity of HRT is derived from the injectivity of ORT and PRT. The proof of Proposition i]s in Appendix C.2
Hierarchical Radon Transform of discrete measures: Let f(x) = - a,6(x - 2z), we have ΣT_, a, (o- + TTT 2;). where is the matrix columns of which are 0y Here, 01.k are bottleneck projection directions, vb is the mixing direction, The ④ is the final projecting direction, 0.. x.,.... 03 xr, for any j [k] are the bottleneck projections, and eb T TTOT Iz...., / TT,, xx, is the final projection. We consider that the bottleneck projections
(HR (1.4, - E agd (u- (
the spanning set of subspace that has the rank at most lc and the final projection belongs to that subspace. Based on the linearity of Gaussian distributions, we provide the
result of HRT multivariate Gaussian and mixture of multivariate Gaussians in Appendix B
5

---

Published as a conference paper at ICLR 2023
Applications of Hierarchical Radon Transform: In this paper, focus showing the benefit of the HRT in the sliced Wasserstein settings. However, similar to the Radon Transform, the HRT can also be applied to multiple other upplications such sliced Gromov Wasserstein (Vayer et al.) 2019), sliced mutual information Goldfeld & Greenewald] (2021), sliced score matching (sliced Fisher divergence) Song al. (2020), sliced Cramer distance (Kolouri al. (0T9a), and other tasks that need to project probability measures.
3.2 HIERARCHICAL SLICED WASSERSTEIN DISTANCE
By using Hierarchical Radon Transform, we define novel variant of sliced Wasserstein distance which is named Hierarchical Sliced Wasserstein (HSW) distance.
Definition 6. For any p 2 1, k 1, and dimension d 2 1, the hierarchical sliced Wasserstein distance of order p between two probubility measures μa E (RR()) and E (R)( is given by:
HSW (,S,, v) (Bone. WP (HHRfw(s v), (1 01.8 +))) (($ and U((--)).
(5)
where .1....,0 0g
Properties of hierarchical sliced Wasserstein distance: First, we have the following result for the metricity of HSW.
Theorem 1. For any p 2 1 and k 2 L, the hierarchical sliced Wasserstein HSW, p.k is metric on the space of probability measures on R.d.
Our next result establishes the connection between the HSW, max hierarchical sliced Wasserstein (Max-HSW) (see Definition in Appendix B), max sliced Wasserstein (Max-SW) SW) (see Definition in Appendix [). and Wasserstein distance. We refer the reader to Appendix B for more theoretical properties of the Max-HSW The role of Max-HSW is to connect HSW with Max-SW that further allows us to derive the sample complexity of HSW.
Proof of Theorem is given in Appendix
Proposition 3. For any p and k 2 L, we find that
(a) S.SWW,kl S E Maxx-11S,,,slu, S Max-SW, S WW(u,v), (b) SW,(,,)) S Max-SW,(1,,) S Max-HISpp,s(u..) where we define
Max-HSW H., O...... E84 WESt-1
W, ((HR))))) O1a (HRRf)))
max
(H..S max W, (R) 0E84-1
as max hierarchical sliced p- Wassersttein, and max sliced p- D-Wasserstein, respectively.
Proof of Proposition is given Appendix C.4 Given the bounds Proposition B] we demonstrate that the hierarchical sliced Wasserstein does not suffer from the curse of dimensionality for the inference purpose, namely, the sample complexity for the empirical distribution from i.i.d. samples to approximate their underlying distribution is at the order of 1o(n11/2 where n is the sample size. Proposition 4. Assume that P is a probability measure supported on compact set of Rd. Let X1, X2...., X,, of these data. Then, for any 2 1, there exists a universal constant C. > 0 such that
v be i.i.d. samples from and denote P, - ōx, as the empirical measure
EHHSWp.k p. P)] S Ok Ck.((d logogn//m
where the outer expectation is taken with respect to the data X1, X2....,
Proof of Proposition is given in Appendix C.5
Monte Carlo estimation: Similar SW, the expectation in Definition 6 is intractable. Therefore, Monte Carlo samples WI...., vL ~ u($*=1) (by abuse of notations) and 01,1,..., .......... Og.1...., O2.I ~ U($d-1) are used to approximate the HSW, which leads to
the following approximation:
HSS ()) = HL
WB ((HRf,)( OLa,n 1h), (HRfa) (1 bt))
(6)
1=1

---

Published as a conference paper at ICLR 2023
I g
21 #
X-6-9
Pg GC22
é g
yeur
X guot
WalieRAale thin PORRLI 450 WAlL (HOR whll wy wyreee (VORLA 26.
BSW pain
Y ged
ArL
M08t
2!
9-r.0.9
Figure 2: The Monte Carlo estimation of hierarchical sliced Wasserstein distance (HSW) with H 1, bottleneck projections, and final projections.
Computational and projection complexities on discrete measures: It is clear that the time complexity of the Monte Carlo estimation of HSW with discrete probability measures of n supports is (H + H Lkn + Ln log, nt). The projection complexity of HSW is OH + kL). For a fast computational complexity and low projection complexity, we simply choose H 1. In this case, the computational complexity is Okdn + Lkn + Ln loga n.) and the projection complexity is Odd + kL). Recall that h < L, which implies the estimation of HSW is faster and more efficient in memory than the estimation of SW. This fast estimator is unbiased, though its variance might be high.
Benefit of HSW when d >> nt For the same computation complexity, HSW can have higher number of final projections L, than SW. For example, when d = 8119 and n = 128 (the setting that we will use in experiments), SW with T. 100 has the computational complexity proportion to 104.94 x 10t and the projection complexity proportion to 0.82 x 10 In the same setting of d and n, HSW with H L, 50 and 500 has the computational complexity proportion to 89.45 x 10 and the projection complexity proportion to 0.66 x 10
Implementation of HSW on discrete measures: The slicing process of HSW contains H matrices of size d x k in the first level and matrix of size k x L in the second level. The projected measures are obtained by carrying out matrix multiplication between the support matrices with the projection matrices in the two layers in turn. When H = 1, we observe the composition of projection matrices in the two layers as a two-layer neural network with lincar activation. However, the weights of the neural network have constraint (spherical constraint) and are sampled instead of being optimized. In the paper, since we focus on the efficiency of the estimation, we consider only settings where H 1. A visualization of the process when H 1 is given in Figure 2
Beyond single hierarchy with standard Radon transform: In HRT, PRT is applied on the arguments (fi...., tx)) By applying many PRTs subsets of arguments e.g., (t).t)...... (tx-1, tt,) and then applying PRT again on the arguments of the output function, we derive a more hierarchical version of HRT. Similarly, we could also apply ORT the arguments multiple times make the transform hicrarchical. Despite the hierarchy. Hierarchical Sliced Wasserstein distance still uses linear projections. By changing from Radon Transform variants Generalized Radon Transform (Beylkin) 1984) variants, we easily extend Hierarchical Radon Transform to Hierarchical Generalized Radon Transform (HGRT). Furthermore, we derive the Hierarchical Generalized Sliced Wasserstein (HGSW) distance. 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 (GSW) (Kolouri et al., 2019b). Compared to the neural network defining function of GRT (Kolouri ctt al. (019b)), HGSW preserves the metricity, i.c., HGSW satisfies the identity property due to the injectivity of HGRT with detining functions that satisfy constraints H1-H4 in (Kolouri al. 2019b). Since the current set defining functions e.g., circular functions and homogeneous polynomials with defer the investigation of HGSW and finding
an odd degree are not scalable in high-dimension, more scalable function for future work.
Distributions of final projecting directions in HRT: We recall that the final projecting directions of HSW are Vi O,..., Vi O where θ = (f1x). 01. ~ (Sd-)) and vi...,, 1h. ~ (S--). clear that the final projecting directions are distributed uniformly from the manifold = {a
dd-1 | x ====0 >k= Tt 9r, (vi...., 3 E 1 62 E 1 Vi = 1.... k}. Therefore, HSW can be special manifold. This is
considered as the sliced Wasserstein with the projecting directions different from the conventional unit hyper-sphere. To our knowledge, the manifold S has not been explored sufficiently in previous works, which may be a potential direction of future research.
7

---

Published as a conference paper at ICLR 2023
Table I: Summary FID scores, IS scores, computational complexity, memory complexity, computational time in millisecond (ms) of different estimations of SW and HSW on CIFARIO (32x32), CelebA (64x64), and Tiny ImageNet (64x64),
Method
Com (j)
Proj ())
Time (
CIFARIO
ColebA
Tiny ImageNet
FID (U)
(T
FID (1)
FID (1)
15 (1)
GBS (Dai Seijak 2021]
66.5
57.3
SW (L=100)
101.95
0.82
51.62:13.69
5.74
17,541188
96.03=3.17
5.38:10.29
HSW (k-70, L-2000)
93.11
0.71
47.644:5.20
5.98:0.22
17.59 12
89.77-3.56
5.83:-00311
SW (L=1000)
1049.47
8.19
42.26:13.52
6.30:20119
17.35 56
84.67=3.93
5.98:00117
HSW (km400) L=6000)
732.01
5.68
41.80=1.008
6.38=0.15
15.89:2.19
82.52 4.40
6.00:00.19
SW (L=10000)
10494,72
81.92
1.3
38.60.12.23
6.54
16.054
84.37_3.68
6.06:1.0211
HSW (K-3000, 1-18000
10073.85
78,58
38.22-44.6
6.57-0032
+
80.69 5.87
6.07+00.25
CIFARLO
Celebb
Tiny Imageher
24r L-10ce
FRCL-1000
DM L-3300
vise (ow 70000
leae burts 1-0900
HIS (o071) -ITE0
20-20006 L-000)
HGM 1--00000- L0000)
10-1000----11000 2-20001
T1e Score
F10
Fprchs
on
Epochs
Figure 3: The FID scores over epochs of different training losses on datasets. We observe that HSW helps the generative models converge faster.
On the choices of and in HSW: We consider the HSW as an alternative option for applications that use the SW. For given value of L in the SW, we can choose faster setting of HSW by selecting
S Ld based on the analysis of their computational complexities. Similarly, the HSW with Le
T.4-d
final projections can be faster than the SW with L1 projections by choosing k I Lid-(La L1) log, d+L2 Later, we use this rule for the choices of & the experiments while comparing HSW with SW.
4 EXPERIMENTS
In this section, we compare HSW with SW on benchmark datasets: CIFARIO (with image size 32x32) (Krizhevsky et al. 2009). CelebA (with image size 64x64), and Tiny ImageNet (with image size 64x64) (Le & Yang 2015). To this end, we consider deep generative modeling with the standard framework of the sliced Wasserstein generator (Deshpande et al.] 2018 Nguyen et al.) 2021a] Deshpande et al. 2019 Nguyen & Ho 2022b Nadjahi et al. 2021). We provide a detailed discussion of this framework inc luduning training losses and their interpretation in Appendix I..] The SW variants are used in the feature space with dimension d = 8192 and the mini-batch size 128 for all datasets. The main evaluation metrics are FID score (Heusel et al. 2017) and Inception score (IS) (Salimans) eet al. 20166.. We do not report the IS score on CelebA since it poorly captures the perceptual quality of face images (Heusel al. 2017). The detailed settings about architectures, hyper-parameters, and evaluation of FID and IS are provided in Appendix F
Our experiments aim to answer the following questions: (1) For approximately the same computation, is the HSW comparable in terms of perceptual quality while achieving better convergence speed? (2) For the same number of final projections L and a relatively low number of bottleneck projections k < L. how is the performance of the HSW compared to the SW? (3) For fixed value of bottleneck projections k, does increasing the number of final projections improve the performance of the HSW? (4) For approximately the same computation, does reducing the value of k and raising the value of lead to better result? After running each experiment 5 times, we report the mean and the standard deviation of evaluation metrics.
The HSW is usually better than the SW with a lower computation: We report the FID scores, IS scores, the computational complexity (x 10%), and the projection complexity (00) for the SW with L E {100, 1000, 10000} and the HSW with (k: L) = {(70, 2000), (400, 6000). (3000, 18000)) respectively in T The computational complexities and the projection complexities computed based on the big O notation analysis of SW and HSW in previous sections. According to the table, the HSW usually yields comparable FID and IS scores while having lower computational complexity
8

---

Published as a conference paper at ICLR 2023
Table 2: FID scores, scores, computational complexity, and memory complexity for ablation studies of A and of the SW on CIFARIO (32x32), CelebA (64x64), and Tiny ImageNet (64x64).
CIFARIO
ColebA
Tiny ImageNet
Method
Com (L)
Proj (L)
FID (
IS (t)
FID ())
FID ())
IS (?)
SW (L=1000)
1049.47
8.19
42.26113.52
6.3011019
17.35:12.56
84,67133.3
5,9810,17
HSW (k=500, 1==1000)
589.18
4.59
43.58++401
6.25++031
17.50+2.225
89.02+2.32
5,92+0.19
HSW (k=500, L=4000)
783.87
6.09
41.8514.42
6.36110.23
16.80.11.23
86.57.13.80
5.94:10.45
HISW 400 6=000)
732.01
5.68
41 41.8011.88
6.38.10.15
15.89112.19
82.52.14.40
6.0010.19
HSW [k=100, 1.=50000)
789.65
5.81
44.70++.119
6.09+00115
17.41+2.12
89.01+2.73
5.90+0.21
and a lower projection complexity on benchmark datasets. We show random generated images
on CIFARIO 10 in Figure 5 in Appendix D.2, on CelebA in Figure 6 in Appendix D.2 and on Tiny
ImageNet in Figure 7 in Appendix D.2 as qualitative comparison. Those generated images are
consistent with the quantitative scores in Table
The HSW leads to faster convergence than the SW with a lower computation: We plot the FID scores over training epochs of the SW and the HSW with the same setting as in Table I in Figure 3 We observe that FII scores from models trained by the HSW (with better computation) reduce faster than ones trained from the SW. The same phenomenon happens with the IS scores in Figure _ in Appendix D.2 where IS scores from the HSW increase earlier. The reason that the HSW has higher number of final projections than the SW, hence, it is a more discriminative signal than the SW:
Ablation studies on k and L in the HSW: In the Table 2 report the additional FID scores, IS scores, the computational complexity (x 10%). and the projection complexity (x 10%) for the HSW with (k, L) = (500, 1000), (500, 4000), (100, 50000)}. First, we see that given & = 5000, increasing L from 1000 to 4000 improves the generative performance on all three datasets. Moreover, we observe that the HSW with the same number of final projections as the SW (I. = 1000) gives comparable scores while the complexities are only about half of the complexities of the SW. When decreasing & from 500 to 400 and increasing L from 4000 to 6000, the generative performance of the HSW is enhanced and the complexities are also lighter. However, choosing a too-small & and a too-large L does not lead to a better result. For example, the HSW with k 100, L = 50000 has high complexities compared to k 500, L = 4000 and k 400, L 6000, however, its FID scores and IS scores are worse. The reason is because of the linearity of the HRT. In particular, the k bottleneck projections form a subspace that has rank at most A: and the J. final projections still lie in that subspace. This fact suggests that the value of & should be also chosen to be sufficiently large compared to the true rank of the supports. In practice, data often lie on a low dimensional manifold, hence, & can be chosen to be much smaller than d and L can be chosen to be large for good estimation of discrepancy. This is an interpretable advantage of the HSW compared to the SW since it can separate between the assumption of the ranking of supports and the estimation of the discrepancy between measures.
Max hierarchical slieed Wasserstein: We also compare Max-HSW (see Definition 7 in Appendix B)
with the conventional Max-SW in generative modeling Table Appendix [D.2] We observe that the overparameterization from HRT could also improve the optimization of finding good projections. We would like to recall that the Max-HSW is the generalization of the Max-SW, namely, Max-HSW with & = 1 is equivalent to the Max-SW. Therefore, the performance of the Max-HSW is at least the same as the Max-SW.
5 CONCLUSION
In this paper, we proposed a hierarchical approach to efficiently estimate the Wasserstein distance with provable benefits in terms of computation and memory. It formed final projections by combining linearly and randomly from a smaller set of bottleneck projections. We justified the main idea by introducing Hierarchical Radon Transform (HRT) and hierarchical sliced Wasserstein distance (HSW). We proved the injectivity of the HRT, the metricity of the HSW, and investigated its theoretical properties including computational complexity, sample complexity, projection complexity, and its connection to other sliced Wasserstein variants. Finally, we conducted experiments on deep generative modeling where the main computational burden due the projection was highlighted. In this setting, HSW performed favorably in both generative quality and computational efficiency.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
NH acknowledges support from the NSF IFML 2019844 and the NSF AI Institute for Foundations of Machine Learning.
REFERENCES
Zeyuan Allen-Zhut Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances neural information processing systems, 32, 2019.
Jason Altschuler, Jonathan Niles- Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In Advances in Neural Information Processing Systems, pp. 1964-1974, 2017.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223, 2017.
Yikun Bai, Bernard Schmitzer, Mathew Thorpe, and Soheil Kolouri. Sliced optimal partial transport. arXiv preprint arXiv:2212.08044) 2022.
Gregory Beylkin. The inversion problem and applications of the generalized Radon transform. Communications on pure and applied mathematics, 37(5):579-599, 1984.
Bharath Bhushan Damodaran, Benjamin Kellenberger, Rémi Flamary, Devis Tuia, and Nicolas Courty. Deepjdot: Deep joint distribution optimal transport for unsupervised domain adaptation. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 447-463, 2018
Clément Bonet, Nicolas Courty, François Septier, and Lucas Drumetz. Sliced Secced-Wassee Wasserstein gradient flows. arXiv preprint arXiv:21 10972, 2021.
Clément Bonet, Paul Berg, Nicolas Courty, François Septier, Lucas Drumetz, and Minh-Tan Pham. Spherical sliced wasserstein. arXiv preprint arXiv:2206.088 08780, 2022.
Nicolas Bonneel and David Cocurjolly. Spot: sliced partial optimal transport. ACM Transactions Graphics (TOG), 38(4) 4): 1-33, 2019.
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Plister. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 1(51):22-45, 2015.
Xiongjie Chen, Yongxin Yang, and Yunpeng Li. Augmented sliced Wasserstein distances. Interna- tional Conference on Learning Representations, 2022.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, pp. 3730-3739, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, pp. 2292-2300. 2013.
Biwei Dai and Uros Seljak. Sliced iterative normalizing flows. In International Conference on Machine Learning, pp. 2352-2322222 2364. PMLR, 2021.
Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing. Generative modeling using the sliced Wasserstein distance. Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 3483-3491, 2018.
Ishan Deshpande, Tuan-Ting Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander G Schwing. Max-sliced Wasserstein distance and its use for GANs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10648-10656 2019.
10

---

Published as a conference paper at ICLR 2023
Kilian Fatras, Younes Zine, Rémi Flamary, Rémi Gribonval, and Nicolas Courty. Learning with minibatch Wasserstein: asymptotic and gradient properties. In AISTATS 20nd-23nd International Conference Artificial Intelligence and Statistics, volume 108, pp. 1-20, 2020.
N. Fournier and A. Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162:707-738, 2015.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with Sinkhorn divergences. In International Conference Artificial Intelligence and Statistics, pp. 1608 1617.
PMLR, 2018.
Ziv Goldfeld and Kristjan Greenewald. Sliced mutual information: A scalable measure of statistical dependence. Advances in Neural Information Processing Systems, 34, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Sigurdur Helgason. The Radon transform r. In Integral Geometry and Radon Transforms, pp- 1-62. Springer, 2011.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge to local Nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-6637, 2017.
Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung. Multilevel clustering via Wasserstein means. In International Conference Machine Learning, pp. 1501-1509, 2017.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6998. 2014.
Lev Borisovich Klebanov, Viktor Beneš, and Ivan Saxl. N-distances and their applications. Charles University in Prague, the Karolinum Press Prague, Czech Republic, 2005.
Soheil Kolouri, Phillip E Pope, Charles Martin, and Gustavo K Rohde. Sliced Wasserstein auto-encoders. In International Conference on Learning Representations, 2018a.
Soheil Kolouri, Gustavo K Rohde, and Heiko Hoffmann. Sliced Wasserstein distance for learning Gaussian mixture models. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3427-3436, 2b.
Soheil Kolouri, Nicholas A Ketz, Andrea Soltoggio, and Praveen K Pilly. Sliced cramer synaptic consolidation for preserving deeply learned representations. In International Conference on Learning Representations, 2019a.
Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized sliced Wasserstein distances. In Advances in Neural Information Processing Systems, pp. 261-272, 2019b.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
Trung Le, Tuan Nguyen, Nhat Ho, Hung Bui, and Dinh Phung. Lamda: Label matching deep domain adaptation. In International Conference Machine Learning, pp. 6043-6054. PMLR, 2021.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 707):3, 2015.
Chen- Muen-Yuuuo Lee, Tanmay Batra, Mohammad Haris Baig, and Daniel Ulbricht. Sliced Wasserstein discrepancy for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 10285-10295, 2019.
Jose Lezama, Wei Chen, and Qiang Qiu. Run-sort-rerun. Escaping batch size limitations in sliced Wasserstein generative models. In International Conference on Machine Learning, pp. 6275-6285. PMLR, 2021.
11

---

Published as a conference paper at ICLR 2023
Zhi-Pei Liang and David C Munson. processing, 6(10):1467-1455) 1469, 1997.
Partial Radon transforms. IEEE transactions image
T. Lin, N. Ho, and M. Jordan. On the efficiency of the Sinkhorn and Greenkhorn algorithms and their acceleration for optimal transport. ArXiv Preprint: 1906.01437, 2019a.
T. Lin, N. Ho, X. Chen, M. Cuturi, and M. I. Jordan. Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm. In NeurlPS, pp. 5368- 2020.
Tianyi Lin, Nhat Ho, and Michael Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. International Conference on Machine Learning, pp. 3982-3991, 2019b.
litu Rout, Alexander Korotin, and Evgeny Burnaev. Generative modeling with optimal transport maps. In International Conference on Learning Representations, 2022.
Antoine Liutkus, Umut Simsekli, Szymon Majewski, Alain Durmus, and Fabian-Robert Stöter. Slised-Wasserstin flows: Nonparametric generative modeling via optimal transport and diffusions. In International Conference on Machine Learning, pp. 4104-4113, PMLR, 2019.
Gonzalo Mena and Jonathan Weed. Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem. In Advances Neural Information Processing Systems, 2019.
Navid Naderializadeh, Joseph Comer, Reed Andrews, Heiko Hoffmann, and Soheil Kolouri. Pooling by sliced Wasserstsstttnin embedding. Advances in Neural Information Processing Systems, 34, 2021.
Kimia Nadjahi, Alain Durmus, Umut Simsekli, and Roland Badeau. Asymptotic guarantees for learning generative models with the Siiced-Wasserseee distance. In Advances in Neural Information Processing Systems, pp. 250-260, 2019.
Kimia Nadjahi, Valentin De Bortoli, Alain Durmus, Roland Badcau, and Umut Şimşekli. Approxi- mate Bayesian computation with the sliced- Srreed-Wasseer Wasserstein distance. ICASSP 2020-2033 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5470-5474. IEEE, 2020.
Kimia Nadjahi, Alain Durmus, Pierre E Jacob, Roland Badcau, and Umut Simsekli. Fast approxima- tion of the Sitred-Wasserstcin distance using concentration of random projections. Advances in Neural Information Processing Systems, 34, 2021.
Khai Nguyen and Nhat Ho. Amortized projection optimization for sliced Wasserstein generative models. Advances in Neural Information Processing Systems, 2022a.
Khai Nguyen and Nhat Ho. Revisiting sliced wasserstein on images: From vectorization to convolu- tion. Advances in Neural Information Processing Systems, 2022b.
Khai Nguyen, Nhat Ho, Tung Pham, and Hung Bui. Distributional to generative modeling. International Conference on Learning Representations, 2021a.
and applications
Khai Nguyen, Son Nguyen, Nhat Ho, Tung Pham, and Hung Bui. Improving relational regularized autoencoders with spherical sliced fused Gromov- Wasserstein. In International Conference Learning Representations, 2021b.
Khai Nguyen, Dang Nguyen, Quoc Nguyen, Tung Pham. Hung Bui, Dinh Phung, Trung Le, and Nhat Ho. On transportation of mini-batches: A hicrarchical approach. In Proceedings of the 39th International Conference on Machine Learning, 2022a.
Khai Nguyen, Dang Nguyen, Tung Pham, and Nhat Ho. Improving mini-batch optimal transport via partial transportation. In Proceedings of the 39th International Conference on Machine Learning, 2022b.
Khai Nguyen, Dang Nguyen, and Nhat Ho. Self-attention amortized distributional projection optimization for sliced Wasserstein plint-cloud reconstruction. arXiv preprint arXiv:2301.04791, 2023a.
12

---

Published as a conference paper at ICLR 2023
Khai Nguyen, Tongzheng Ren, and Nhat Ho. Markovian sliced Wasserstein distances: Beyond independent projections. arXiv preprint arXiv:2301.03749 2023b.
T. Nguyen, Q.-h. Pham, T. Le. T. Pham, N. Ho, and B.-S. Hua. Point-set distances for learning representations of 3D point clouds. ICCV, 2021c.
Sloan Nietert, Ziv Goldfeld, Ritwik Sadhu, and Kengo Kato. Statistical, robustness, and computational guarantees for sliced wasserstein distances. Advances in Neural Information Processing Systems, 2022.
Ofir Pele and Michael Werman. Fast and robust earth mover's distances. In 2009 IEEE 12th International Conference on Computer Vision, pp. 460-467. IEEE, September 2009.
Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, ((5-6):355-60)) 607, 2019.
Gabriel Peyré and Marco Cuturi. Computational optimal transport, 2020.
Alain Rakotomamonjy and Ralaivola Liva. Differentially private sliced Wasserstein distance. In International Conference Machine Learning, pp. 8810-8820. PMLR, 2021.
Mark Rowland, Jiri Hron, Yunhao Tang, Krzysztof Choromanski, Tamas Sarlos, and Adrian Weller. Orthogonal estimation of W Wasserstein distances. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 186-195. PMLR, 2019.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. Advances in Neural Information Processing Systems, 29, 2016.
Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving GANs using optimal transport. In International Conference on Learning Representations, 2018.
Morgan A Schmitz, Matthieu Heitz,, Nicolas Bonneel, Fred Ngole, David Coeurjolly. Marco Cuturi, Gabriel Peyré, and Jean-Luc Starck. Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learning. SIAM Journal on Imaging Sciences, 11(1):6436678 2018.
Yang Song. Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. Uncertainty Artificial Intelligence, pp. 574-584. PMLR, 2020.
llya Tolstikhin, Olivier Bousquet, Sylvain Gelly, and Bernhard Schoelkopf. Wasserstein auto- encoders. In International Conference on Learning Representations, 2018.
Titouan Vayer, Rémi Flamary, Nicolas Courty, Romain Tavenard, and Laetitia Chapel. Sliced Cromov-Wasserstein. Advances in Neural Information Processing Systems, 32, 2019.
Cédric Villani. Optimal transport: Old and New. Springer, 2008.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.
Jiqing Wu, Zhiwu Huang, Dinesh Acharya, Wen Li, Janine Thoma, Danda Pani Paudel, and Luc Van Gool. Sliced Wasserstein generative models. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3713-3722, 2019.
Jiaqi Xi and Jonathan Niles-Weed. Distributional convergence of the sliced wasserstein process. Advances in Neural Information Processing Systems, 2022.
Jingjing Xu, Hao Zhou, Chun Gan, Zaixiang Zheng, and Lei Li. Vocabulary learning via optimal transport for neural machine translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 7361-7373, 2021.
13

---

Published as a conference paper at ICLR 2023
Karren Dai Yang. Karthik Damodaran, Saradha Venkatachalapathyy Ali C Soylemezoglu, GV Shiv- ashankar, and Caroline Uhler. Predicting cell lineages using autoencoders and optimal transport. PLoS computational biology, 16(4):e 2020.
Mingxuan Yi and Song Liu. Sliced Wasserstein variational inference. In Fourth Symposium on Advances in Approximate Bayesian Inference, 2021.
14

---

Published as a conference paper at ICLR 2023
Supplement to "Hierarchical Sliced Wasserstein Distance"
In this supplement, we first discuss some related works in Appendix A We then present some additional materials including hierarchical Radon transform on multivariate Gaussian and mixture of multivariate Gaussians, max sliced Wasserstein distance, max hierarchical sliced Wasserstein (Max-HSW) distance, their computation, and their theoretical properties in Appendix B After that, collect proofs for key results in the paper in Appendix C In Appendix D we include the detailed training objectives of our generative modeling framework and some additional experiments including convergence in IS scores of generative models, generated images, and the comparison between the Max-HSW and the Max-SW. Moreover, we report experimental settings including parameter choices and neural network architectures in Appendix
A MORE RELATED WORKS
On the theoretical side, statistical properties of sliced Wasserstein distance in learning generative models are investigated in (Nadjahi et al. 2019). Distributional convergence of the Sliced Wasserstein
process is derived in Xi & Niles- Weed 2022). Statistical, robustness, and computational guarantees for sliced Wasserstein distances are shown in (Nietert et al., 2022). A differential private version of the SWis is proposed in (Rakotomamoniy & Liva 2021).
On the methodological side, authors in (gguyen et al. 202 la b) replace uniform distribution on the projecting directions on the unit hyper-sphere SW with an estimated distribution that puts high probabilities for discriminative directions. Spherical sliced Wasserstein which is sliced Wasserstein
variant on the hyper-sphere is introduced in (Bonet al.) 2022). Dependent projecting directions
are utilized in (Nguyen et al. (2023b). Sliced partial optimal transport is proposed in (Bonneel &
Coeurjolly | et al.j (022) A fast biased approximation of the SW is proposed in (Nadjahi al. 2021). The Augmented SW is introduced (Chen et al. 2022). A sliced Wasserstein variant between measures over tensors is defined in (Nguyen & Ho 2022b). Estimating Wasserstein distance with one-dimensional transportation plans from orthogonal projecting directions is used in (Row eet al. [ 2019). The SW is used in generative frameworks such as sliced iterative normalizing flows (Dai Seljak (021) and fine-tuning pre-trained model (Lezama et al., (02T). The SW gradient flows are investigated in (Liutkus et al. 2019 Bonet et al., 2021). The SW is used for set representations
in NNaderializadeh et 2021T. Variational inference using the SW is carried out in (Yi & Liu 2021).
Similarly, the SW is used for approximate Bayesian computation in (Nadjahi et al. 2020).
B ADDITIONAL MATERIALS
Hierarchical Radon Transform as the composition of Partial Radon Transform and Over- parametrized Radon Transform: From the definitions of ORT (Definition 4 and PRT (Definition we have:
k
k
/
(PR(OR,)))), Oz.k 1b)
f(x)
II
5(t (x. dz))
Σ
take
dt
JRY
JB
1=1
i=1
Sea JRU
/ [(x)
II 8(4 (x., 0,))8
Σ
drdt
J JRL
/ f(x)
II
6(t (x, 0.))
v Σ
tekss
dtdl
i=1
b Σ
1 f(x)6
(x, 0i14ss dr
v
B
= (HR ()),
where the second and the third equality are due to the Fubini's theorem.
Monte Carlo approximation error of HSW: We have the following proposition for the Monte Carlo approximation emor:
15

---

Published as a conference paper at ICLR 2023
Proposition 5. Given p 1, > 1, and u.v E Pp(RR)), we have the following error of Monte Carlo
estimation for HSW:
E B (. HSW
p. (4
Var [W7 (HHRff)); (HRR.)), 01:k, sb)
VHT.
(7)
The proof given in Appendix C.6 From the proposition, that the error reduces proportionally to the square root of H and the square root of L. Therefore, increasing H and I. could lead to better performance.
Hierarchical Radon Transform of Multivariate Gaussian and Mixture of Multivariate Gaus- sians: Similar to the result of Radon Transform for Multivariate Gaussian and Mixture of Mul- tivariate Gaussians (Kolouri et al., 2018b), given projecting direction e = (01:k); b, the one dimensional projected distributions from Gaussian and mixture of Gaussians with the HRT are also Gaussian and a mixture of Gaussians respectively. These results are directly ob- tained from the linearity of Gaussian distributions. In more detail, let f == (u, E), we have (HRJ((, Ossee 16) = Ni TT, μl, ub (06).. Similarly, let f = = - W,N(u, E,), we have (H:,f(; O1sk, 16) Σ w,N( @ 14, 1h o TE,O)).
Max sliced Wasserstein distance: We first review the definition of max sliced Wasserstein distance (Max-SW) (Deshpande al., 2019).
Definition 7. For any p 2 1 and dimension d 2 1, the max sliced Wasserstein-p distance between two probability measures μ. (RR) and v E (TR()) is given by:
Max-SW,(1, v) max W, (:Rf))( (Rf.(()))
DES4
Max-SW is also a valid metric between probability measures (Deshpande et al. 2019). The benefit of Max-SW is that it uses only one projecting direction instead of 7. projecting directions as SW. Therefore, its projection complexity is only ((d) compared to O(Ld) of SW. However, Max-SW requires an iterative optimization procedure to find the max projecting direction on the unit hyper- sphere e.g., projected gradient asscent (Kolouri et al. 2019b). We summarize the projected gradient ascent of the Max-SW in Algorithm
Algorithm 1 Max sliced Wasserstein distance
Input: Probability measures: (a, v, learning rate max number of iterations T. Initialize 0
while not converge or reach T do
0 17 VoW, (R)
8
|10112
end while
Return: 0, W, (IRF)))))
Max hierarchical sliced Wasserstein distance: We now define the max hierarchical sliced Wasser- stein distance.
Definition 8. For any p 2 1, 2 1 and dimension d 2 1, the max hierarchical sliced Wasserstein-p ) is given by: Wp ((HRf))- 11.. v), (HRff)) 01k +))
distance between two probability measures (RR))) and v E Pp(Rdd)
Max-HSW,.. p. Max-HSSp.e(H..
max
0.....0.ES Edd P.sS
Similar the idea of max sliced Wasserstein, Max-HSW improves the projection complexity of HSW by avoiding using Monte Carlo samples for projecting directions and mixing directions. In particular, Max-HSW finds the best set of bottleneck projections f i.k and the best mixing direction vb in terms of maximizing the discrepancy between two interested measures.
Remark 1. We have that when lo the max hierarchical sliced Wasserstein distance reverts into the max sliced Wasserstein distance.
Max-HSW, p.1 (1, Max-SW,
This is due the fact that v E g0 (1).
16

---

Published as a conference paper at ICLR 2023
In Max-HSW, we do not enforee any linear independence constraint over & bottleneck projection directions. However, that kind of constraint can be done by forcing the l vectors to be orthogonal. Formally, we could project & vectors into the Stiefel manifold by performing the Sraam-Shhiie process. We can only do maximization over k bottleneck vectors and take the expectation over the linear mixing vectors. We denote this variant Semi Max hierarchical sliced Wasserstein distance.
Definition 9. For any p 2 1, k 2 1 and dimension d 2 1, the max hierarchical sliced Wasserstein-p ) is given by:
distance between two probability measures μs pp (TR.) and v E (P((R)))
SemiMax HSW,HWWWW...... p.S,p,,,,,))
max
(Eenee WE ((HR B1sk v), (HRL)) 01s +)))
81 EB4
The optimization can be done by stochastic gradient ascent that utilizes Monte Carlo samples ........ 4hr, from (SS--1).
Computation of max hierarchical sliced Wasserstein distance: Similar to the Max-SW, WSW can be computed via the projected gradient ascent algorithm. In practice, the gradient of 0z= and eb can be computed by using backpropagation (chain rule) since the hierarchical Radon Transform can be seen as a two-layer neural network. We summarize the projected gradient ascent of the Max-HSW in Algorithm 2
Algorithm 2 Max hierarchical sliced Wasserstein distance
Input: Probability measures: (l, v, learning rate 7), max number of iterations T.
Initialize 0
while 1s ; vé not converge or reach 7 do
e + 17 W. ((HR)f)(( 01u sb), (HRRf)) 01.k v))
e
|
for = 1 to l: do
8, 0 7. Vo, W, ((HRfu)) 01k (7
0,
T0.12
end for end while Return: 01.k b. Wi ((HRfa)( (H.R)) v))
Properties of max hierarchical sliced Wasserstein distance: We first have the following result for the metricity of Max-HSW.
Theorem 2. For any p 2 1 and 2 1, the hierarchical sliced Wasserstein Max-HSW ) is metric on the space of probability measures on Rd.
Proof of Theorem 2 is given in Appendix C.7 We establish the connection between the HSW, max hierarchical sliced Wasserstein (Max-HS W), max sliced Wasserstein (Max-SW), and Wasserstein distance in Proposition The proof is given in Appendix C.4
We demonstrate that the max hicrarchical sliced Wasserstein does not suffer from the curse of dimensionality for the inference purpose, namely, the sample complexity for the empirical distribution from i.i.d. samples to approximate their underlying distribution is at the order of
Proposition 6. Assume that P is probability measure that has supports on compact set of Let X1, X2...., X,, be i...d. samples from and we denote P., E 8x, as the empirical measure on data samples. Then, for any p Z 1 and k 2 1, there exists universal constant C. >> O such that
E|Max- HSW p.w.p..... (Pn, P)] Cky (d + 1) 1) n/n,
where the outer expectation is taken with respect to the data X1, Xi,.,,...,
Proof of Proposition 6 is similar to the proof of Proposition We refer the reader to Appendix C.5
Hierarchical Generalized Sliced Wasserstein distance: We first define the Overparameterizze Generalized Radon Transform, Partial Generalized Radon Transform, and Hierarchical Generalized Radon Transform. We recall two injective defining functions in (Kolouri et al., 2019b) which are the circular function (z,
| 0|12 for Rdd 0 E gd-1 (hyper-parameter R+) and the
17

---

Published as a conference paper at ICLR 2023
homogeneous polynomials with odd degree g(x, = jaa==m 8ax where (a1,..... (......, .dd,)
N |al Eee 0g x" I zp". The summation in the polynomial defining function iterates over all possible iulti-indices a such that |a| = m with m denotes the degree of the polynomial and 0 E gd.-1
Definition 10 (Partial Generalized Radon Transform). Given the defining function g(x, f) Fd G2g - R. the Partial Generalized Radon Transform (PGRT) PR L1 (R x R
L1 (TR Sg x (R))) is defined
()) = / f(z, v)ō(t - g(z, d).
(8)
Definition 11 (Overparameterizeed Generalized Radon Transform). Given the defining function g( 0) _2 x Ωg + I. the Overparameterized Radon Transform (OGRT) OR LI(R)) 7 Li (Rok x g(d-1)ok) is defined as:
(OgR.) 01:k) / f(x) JBd
8(1 0.),,r))xx, II
(9)
1=1
where tisk == (fi,...,fa) 1x) E R and Pl: == (0)....., 0&) E (50-1)sk.
Definition 12 (Hierarchical Generalized Radon Transform). Given the defining functions I1 (æ. 0) Rd x S2g IR and 92(x,, 1/) I& x Sh - R. Hierarchical Generalized Radon Transform (HGRT)
HGR (IR") L1 (R Doak S2p) is defined as:
(HGRf)(u, O wb = [rc [xx) -92lle (z. (2, (s),,,)),.) +)) dx,
(10)
where R, db Syy and 01.
The injectivity of PGRT, OGRT, and HGRT follow the injectivity of GRT, i.c., the proof technique is similar the case of ORT and HRT. We refer the reader the previous work (Kolouri et al.) (009b) for more information. The benefit HGRT that it can create a much stronger non-linearity by stacking multiple injective ones.
Definition 13. For any p 2 1, k 2 1, and dimension d 2 1, the hierarchical generalized sliced Wasserstein distance of order p between two probability measures μ E Pp (RR) and (P((()))) is given by;
HGSW p.k (p, (Eo... WE (HGR)f)) v), (HGRR() O1.k v))
(11)
where .1....y ,, Og U(2g)) and up ~ U(2.)) The proof technique for the metricity of HGSW the same HSW which is based on the metricity of the Wasserstein distance, the injectivity of HGRT, and the Minkowski inequality.
Distributional Hierarchical Sliced Wasserstein distance: In HSW, projecting directions drawn from the uniform distribution which might not be the best choice in some settings. We could replace it with some other distributions, e.g., Von Mises Fisher (Nguyen al. 2021b or implicit distribution (Nguyen et al. 2021a).
Definition 14. For any p 2 1, k 2 and dimension d 2 1, the distributional hierarchical sliced Wasserstein distance of order p between two probability measures μ E (B.) and PR(())) is given by:
DHSW (H,
(Eerwoog* woon WP (HHRf))(; 0na, v), (HR ()))²
sup (0003/--)),02T(8--1
(12)
where I(S (T(S*-1)) is a family of distributions over the unit-hypersphere The metricity of DHSW requires the continuity condition of [(gd-1) and r(gk-1), i.e.. they have supports all the unit mnit-hypersphere to guarantee the injectivity of the HRT. We refer the reader to previous
works Nguyen al. 2021a b) for more details.
18

---

Published as a conference paper at ICLR 2023
Augmented approaches for HSW: Authors in (Chen et al. 2022) propose to augment measures to higher dimensions for better linear separation. We extend the framework to our hierarchical transform approach. We first define the Spatial Hierarchical Radon transform.
Definition 15 (Spatial Hierarchical Radon Transform). Given injective mapping 9
R
Rd (d' 2 d). Spatial Hierarchical Radon Transform (SHRT) SHR
(,(") -
L, [R -1) ) is defined as:
(SHR,f)M,,0..s 16) Jee [(0)8 E Eig()), dr,
(13)
where v R. (v : 1b)) sk-1, 1 and 01.6 (01.....0.)) 0c) E (S 18d'-1)04
can further extend the SHRT to hierarchical spatial Radon Transform (HSRT) by using the augmenting mappings twice.
Definition 16 (Hierarchical Spatial Radon Transform). Given injective mapping 91 IR 4 Rd
(d' 2 d) and R + I (K's 2 k), Hierarchical Spatial Radon Transform (SHRT) SHR.
L1 (RR) + L1 R x gid' 1188k x Sk )) is defined as:
(HSRF)) 11ck, 1) { f(z) (v
(4) (x)))) dx,
(14)
where E R. db (v1....,,1)) E sk' and 01.k- (......, 02) E
From the above two transforms, could derive the Augmented Hierarchical sliced Wasserstein (AHSW) distance and Hierarchical Augmented sliced Wasserstein (HASW) distance respectively. We skip the definitions of AHSW and HASW here since they are straightforward from the definition of HSW. The injectivity of SHRT and HSRT and the metricity of augmented distances can be proven based on the injectivity of augmenting mappings Φ1 and 92- We refer the reader the previous work Chen et al. (2022 for more details.
C PROOFS
In this appendix, we provide proofs for key results in the main text and in Appendix B
C. PROOF OF PROPOSITION II
Let us consider functions f.g E L (IR)) such that
(ORJ) 014.) = (ORg) 01:k),
It is clear from the Definition that
[(L f(x) 5 [
(x) dx [ g(x) II 8 (t: (I, dr.
i=1
i=1
Taking the integral of both sides the above equation with respect to (k 1) variables 12,...,,Aa. get
k
JooU- / f(x)
II 6(4 (x, 0.)), ...di = - / ((x) II 8(4 - (x, 0z) dz)d22 dla-
Rd
1=1
Next, by applying the Fubini's 's theorem, have
k III 8(1 - (x, 0:) 0:) dx.
J f(x)((1) 01))
II
8(4 - (x, 0.)))d. = J g(a)0((1 - (x, (0z) (1)
i= JR
i=2
Note that for any i k f ot4 (I, d.) = fx 8(s;)ds; = L. As result,
by using change of variables 8, = 4 (z, 0,), we have
f f(z)o(t1 - 01) (p,
ffc f(x)((t) (x, 01))dz
or equivalently, (t) 01) = Rg(ti, 0,). Recall that the Radon transform R is injective. Thus, obtain that f= g. which completes the proof.
19

---

Published as a conference paper at ICLR 2023
C.2 PROOF OF PROPOSITION 2
Let us consider arbitrary functions f.g E IL' (R24) satisfying
(HR,f)(v,0sx) v) = (Higg) 01.k.
where R, E and 01: (S4-1)0k It can be seen from the beginning of Appendix that (HR f1sk 1h) (PR(OR,))(, th, (13e) and (H, 01se, v) = (P)(ORg))(; vh 01.)). Therefore, we get
(PR(OR))((, v, 01:k) (PR(ORg))(; bp, 01x)-
Since Partial Radon Transform is injective, obtain h hyg or equivalenty, (OR (1kk) = (ORg)( 01:4),
which leads to f f- due to the injectivity of Overparametrized Radon Transform. Hence, we reach the conclusion of the proposition.
C.3 PROOF OF THEOREM I
To prove that the hierarchical sliced Wasserstein HSW,, (t.().) is metric on the space of all proba- bility measure on Rd for any p, k 2 we need to verify four following criteria:
Symmetry: For any p, k 2 1, it is obvious that HSW,,&(u v) HSW p)) for any probability measures 1t and v.
Non-negativity: The non non-negativity of HSW (.))))) comes directly from the non-negativity of the Wasserstein metric.
Identity: For any P.k 2 1, it is clear that when = v, we have HSWp,e(H, v) = 0. Now, assume that H HSW (1,, v) 0, then (p,(HR(fp)( 01:k. 1b). (HRfs)) fis v)) for almost all & E sk1 02.k E (8d-1)ask, By applying the identity property of the Wasserstein distance, we have (HRf,)) (-. fI:k. (b) (HLRff))) (. 2b) for almost all ab E g fI E 18d-1)0* Since the Hierarchical Radon Transform injective, we obtain fp = fu. which implies that μ = v.
Triangle Inequality: For any probability measures f1, P2, M3, we find that
H HSW P.A. 9. Mz) (Eo WT ((HR)) (1,0 01.k 1), (HR O1.k. +)))
s (Eera (WF ((HR) (-, w) (HR 01:k, v))
+ WE (HHRf))) 01kks v), (RR (- 0 01 b)))
< (Eo WT ((HR (1 01.k v), (HR fra) (, P1.k. +)))
(B WT (HHRfaa)( (1s0 v), (HR (1x,, v)) 1
H.SW,.( p2) + HSW, p.a. (12, 14a)
where the first inequality is due to the triangle inequality of Wasserstein metric, namely, we have
Wp ((HRf (-. v)), (HR 01k )) S Wp (( +) (HR 01sks +)) + W, ((HR)fp))) 0z:k. v), (MR (. B 1)),
while the second inequality is an application of the Minkowski inequality for integrals. Hence, the hierarchical sliced Wasserstein HSW p.a (t.)) is metric on the space of all probability measures on Rdd for any p, k 1.
C.4 PROOF OF PROPOSITION
The proof of this proposition is direct from the definition of the hierarchical sliced Wasserstein distance, the sliced Wasserstein distance, the max hierarchical sliced Wasserstein distance, and the max sliced Wasserstein distance. Here, provide the proof for the completeness.
20

---

Published as a conference paper at ICLR 2023
(a) We start with
HSW p.A (1, (Ro W (H:RI))(;,0sss (HRR))) +)))
S
max
W ((, (HR (HHR, O1kk: 16))
0 01...,0 E85 WE8tt11
M..xHSSWp.(HH.P)
Subsequently, we have
Max-HSW (,,
max
Wp ((HR)))) 01:k (HR(()), .0. 15))
O1 E3d WESK-1
f inf (xEll(uun) JREWRS
T x T "1" di (2,
max
8 E34-1 WESA-1
max 8 0 f EBM
inf rEll(uuP) Rd xBd
Σ E0 (o v) dr(Ø,y)
WESK
f xdd
max 8,..... O E34-1 WESA-1
inf (Ell(H,))
11&/110
Σ 0J (x 8) dz(x,))
1=1
max
inf TETT(MN)) JR
0J (x v) dr(a.))
6 M18d-
j=1
kP 1 x - 0Tyl" dt dπ(x,)) 3
inf (ETT(MM)) RaxRR I
S max
8E54-1
k max
inf FETT(A.) S 10xx OT oTy dr dr((, 4) W, (0tHu 01v)
0E34-1
=
k max 8E84-1
k max BESI-1
Wp ((R)ff(( (R)))
= k Max-SW (p,
Finally, by applying the Cauchy-Schwarte inequality, get
inf =EII(,.))) / 10T 1 -1 2)
(HX.))
max 0egd
max 888d-1
inf xET((),))) RA {
|10||p11 y/ Pd (2, v)
inf nEll(H.)) xdxdd
|011||00- yll'd=((:1 v)
(p,
Putting the above results together, we obtain the conclusion of the proposition.
(b) Firstly, it is obvious that
SW, v) = WW))))
S max W, (R)
BE3--1
21

---

Published as a conference paper at ICLR 2023
Subsequently, let 0j 0" = arg max
W₂ (). and s (1,0,.....)
gk-1. Then, for any 04 E Sd-1, we have
Max-HSW P.A. (14, v)
max
W ((HR)))(() 01:k 4) (H 01:k. eb))
B E8.
WEB
2 w ((HR)) 02,00....... ....... 0z. )) (HRFf)) 02 . v
( | 10 0 dr(ss v) inf
W (R. (R)
Since the above result holds for all arbitrary 8f gd-1, we obtain Max-HSW (1,
max W, ((Rf)) (R),)) = (ax-SWp(14,)) BEg"
which completes the proof.
C.5 PROOF OF PROPOSITION 4
For the ease of the presentation, we denote θ TRd the compact set of the probability measure P. The result of Proposition 3 indicates that we have
EIHSW p.A (Pr P)] I [k: Max-SW,(Pa..
where we define
Max-SW, P):=
max 8ES
= max W BES/-1
Therefore, the conclusion of the proposition follows long demonstrate that
MaMax-SW (Pr, P)] Cv(d+ 1) log, n/n
where C' is some universal constant and the outer expectation taken with respect to the data. We first start with the property of the closed-form expression of Wasserstein distance in one dimension, which leads to the following equations:
[ F ( Fo (u)
Max-SWi Max-SWP (Wn,Pn.P)
max
Be
(FTb(() - Fo du
max
BER
[Fn,(x)) - Fo(x))
max
0ER<:110 | $1
< diam(O)
max aER<: S
[F),((x)) Fo(x))
where we denote Fn,, and Fo as the cumulative distributions of the two fosh-forward distributions OtP, and OiP.
Direct calculation indicates that
max 0ER9:119 $1
- Fo(x)]
sup Pb P(B)). BeB
where we denote the of half-spaces {a Rd AT 3) for all Rd such that ||@]| S 1. From Wainwright (2019), it is known that the Vapnik- Sonnik-Chervoneniis (VC) dimension of B is at most + Therefore, arrive at
32 (d+ + logz + 1) + log2 (8/6)
sup Pa P(B) S BEB
with probability at least - 5. Collecting the above results, we finally obtain that
E MMM P)] C n/n,
where C' is some universal constant. As consequence, the conclusion of the proposition follows.
22

---

Published as a conference paper at ICLR 2023
C.6 PROOF OF PROPOSITION 5
Using the Holder's inequality, have:
E|
HSW (H, H.W. (,,
HSW E p, - p. p. (u)))))))))
H
w ((HRff)) 010 BIsK,, 2i),
(HR.)) 01:kitr 4/2)
HL
EB WP 01:. ())
L WT ((HRf)) (HRR)) ( Will)
Var
ILL
h=11=
1
Var [W7 ((HR))(( 01as 4), (H +))]
VHL
which completes the proof.
C.7 PROOF OF THEOREM 2
Symmetry: For any 2 1, it is clear that Max-HSW,(a. (4,,) v/) = Max-HSW,(14, μ)) for any probability
measures μ and
The non-negativity of Max-HSW, p. (t. (s.)) comes directly from the non-negativity of the Wasserstein metric.
Non-negativity:
Existence of the max directions: The unit hyperspheres S and @ are compact and we have W, ((HRf))( 01., v), (HRff))( 01.0 v)) is continuous in terms of 01.; and vb. Therefore, there exists
0i 80
arg max 0 Oy EBd W-E8--1
W, ((HRfu(( (HRRu));
Identity: For any p 2 and k it is clear that when μ v, then Max-HSW, (H,
When Max-HSW, (u, v) = 0, we have WpHRRffW( 01.k. v), (HRRf)(, 0n,, v)) = 0 for almost all v E gk-1 One E (8d-1)8k, Applying the identity property of the Wasserstein distance, we have (HRfa)(- 01 e) (HRff) f1:k: 1)) almost all eé E Sk-1, 100-1.0pp. 01.k E 1)k Since the Hierarchical Radon Transform is injective, we obtain V.
Triangle Inequality: For any probability measures μl, P2, p3, we find that
Max-HSW p, p3)
max
Wo ((HR )s 01s, v) (HR.f)a)( 01R, v))
PI.... 18 WEBt-1
W, ((HRf (. 0T v*), (HR (eeefwn)(::) (T,0 v)))
S W, ((HRfm)) 07 (HH, (1 (1))))
+ Wp (HRfuu)) Hi )²), (HRR (. 8i ))))
max
W, ((HR) 01.0 +), (HRffaa) 01sks +))
0r.....AEES 02E8d EBd
-
max
W, (p P 1), (HR 0r:k v))
Max-HSW P.A (pi, u2) Max-HSW, u3)
where the first equality is due to the existence of the directions, the first inequality is due to the triangle inequality with Wasserstein metric, and the second inequality is an application of the definition of maxima.
23

---

Published as a conference paper at ICLR 2023
D DEEP GENERATIVE MODELS
In this section, we first discuss the way we train generative models in our experiments with sliced Wasserstein variants. We then provide additional experimental results including convergence speed of the SW and the HSW in IS score, generated images from the SW and the HSW, and comparison between the Max-SW and the Max-HSW.
D.1 TRAINING DETAIL.
In short, we follow the generative framework from Deshpande et al. (2018). The model distribution is parameterized as (z(x)) E ((R)) where (z) GoHfo. 14g := (0, 122), and Go is Resnet He et al.] (216))-tpp neural network. The detail of the neural networks is given in Appendix FF Previous works suggest to discriminator images is not given (unknown). We denote the discriminator as a composite function Da, Da. where Dg, Rd + Ed' and Da, Rd' + R. In particular, Dø, transforms original images to their latent features. After that, D3, maps their features maps to their corresponding discriminative scores. We denote the data distribution is Mdata our objectives are:
type of ground metric learning since the true metric between
min E
X @m datu: ~ 9m D(D FPx, P9ott))P))
min (Bar [min(0, -1 + D3 (Da (1)))) + Bz-nn [min(0) -1 DD (G,, 91.92
where m 2 1 is the mini-batch size and ()::,) is the (Max-)SW distance or (MS distance.
Relation to m co-mini-batel energy distance: The objective for training the generator seen as type of m-mini-batt bbach energy distance Klebanov al. (2005); Salimans et al. (2018) with sliced Wasserstein variants kernel. Moreover, it is also known as mini-batch optimal transport Fatras et al. (2020): Nguyen et al. (222a b).
D.2 ADDITIONAL RESULTS
Convergence of generative models from SW and HSW in IS scores: We plot the IS scores over training epochs of the SW and the HSW with the same setting as in Table Figure We observe that IS scores from models trained by the HSW (with better computation) increase faster than ones trained from the SW. We would like to recall that reason is that the HSW has higher number of final projections than the SW, hence, it has more discriminative signal than the SW.
Radom generated images: We show randomly generated images from CIFAR1O, CelebA, and Tiny Imagenet from the SW and the HSW generative models in Figure S 7 From these images, observe that increasing I enhance the performance of the SW, and increasing both and k yield better images for the HSW. Also, the qualitative comparison from generated images between the SW
and the HSW is consistent with the FID scores and IS scores in Table
Comparison between the Max-HSW and the Max-SW is the generalization of the Max-SW since MaX-HSW with k = 1 is equivalent to the Max-SW. Therefore, the performance of MaX-HSW is least the same as the Max-SW. To find out the benefit of k >> in Max-HSW we run Max-HSW with & E {1, 10, 100, 1000). the slice learning rate n E {0.001, 0.01, 0.1). and the maximum number of iteration T {1, 10, 1003. We report the best FID scores and IS scores in Table 3 We observe that Max-HSW l: > 1 gives a better FID score than the Max-SW on CelebA dataset. The reason might be due to the overparametrization of the Max-HSW that leads to better final slice. However, on CIFARIO 10 and Tiny ImageNet, the Max-HSW k does not show any improvement compared to the HSX-HSW k = (Max-SW). This might be because the projected gradient ascent does not work well in multiplayer structure like in HRT. We will leave the investigation about optimization of the Max-HSW in future works since the Max-H MaX-HSW has the potential explain partially adversarial training frameworks.
We would like recall that Max-HSW
E COLOR TRANSFER VIA GRADIENT FLOW
In the color transfer setting, we are interested in transferring the color palette of a source image to the color palette of target image. Formally, we denote the color palette of the source image
24

---

Published as a conference paper at ICLR 2023
CIFARI0
Tiny ImageNet
5.0
15 Score
Score
SW L=1000
SW L=1000
SW L=10000
SW L=10000
HSW (k=70
HSW (k=700==0000)
(K=4000--6000)
(K=400,L-6000)
HSW (K-3000_L=18000)
4.0
HSW (K=3000,--18000)
400
300
Epochs
Epochs
Figure 4: The IS epochs of different training losses datasets. We observe that HSW helps the generative models converge faster.
SW (L=100)
SW (L=1000)
SW (L= 10000)
HSW (k=70,L=2000)
HSW (k=400,L=6000)
HSW (k=3000,1=18000))
Figure 5: Random generated images of the SW and the HSW on CIFAR10.
Table FID scores and scores the Max-SW and the Max-HSWW of on CIFARIO (32x32), CelebA (64x64), and Tiny ImageNet (64x64).
CIFAR10
CelebA
Tiny ImageNet
Method
FID (1)
IS (t)
FID (4)
FID (L)
IS (t)
Max-SW (Max-HSW k=1)
43.6742.34
6.49+t011
17.17+1.72
82.47+5.73 82.47-15.73
6.03+t0.22
Max-HIWW
43.67.12.4
6.4910.11
15.92.1.87
6.03-10.52
.. Vn.) ... of size (RGB) in turn with n 1. We would like to note that, the orders of points X and Y are corresponding to the pixels in empirical measures X and respectively. We now move Px to Py under the following gradient flow: (t) = Dx Py) with D chosen distance, e.g., SW and HSW. We simply the Euler scheme to solve this gradient flow with iterations. Since color is represented by three values in the set (O...., .0.5),,55), we round values in X(T) the closest values in (O.... 255} obtain the final color palette.
and the target image X (#1....,, TT)) and Y (V1
images. We denote Px = Ex= 6m; and Py
Σn &y.
25

---

Published as a conference paper at ICLR 2023
SW (L=
SW (L= 1000)
SW (L=10000)
HSW (k=70,L=2000)
HSW (k=400,L=6000)
HSW (k=3000,1=18000)
Figure 6: Random generated images of the SW and the HSW CelebA
SW (L=100)
SW (L=1000)
SW (L=11000) 10000)
HSW (k=70,L=2000)
HSW (k=400,L=6000)
HSW (k=3000,L=18000
Figure 7: Random generated images of the SW and the HSW on Tiny ImageNet.
In our experiments, we compress original images to 3000 colors by using K-Means before doing color transfer. In this case, n 3000 is much larger than d 3, hence, using HSW does not give any computational benefits compared to SW. Namely, computing one-dimension Wasserstein distances becomes the main computation. However, HSW could provide the dependency between final projection directions since they are created from the same set of bottleneck projection directions.
In Figure we compare SW, generalized sliced Wasserstein (GSW) Kolouui et al. 2019b), HSW, and hicrarchical generalized sliced Wasserstein (HGSW) which is straightforward extension of HSW by replacing the Radon Transform variants by Generalized Radon Transform variants. All the distances are computed with the order 2 (p- 2) and we use the number of iterations T = 10000 with the step size 0.1 for the Euler scheme. For GSW and HGSW, we use the polynomial of degree as the defining function. For SW and GSW, set the number of projections L = 3. For HSW and HGSW, we set the number of bottleneck projections k = 10 and the number of final projections L = In the figure, we report the computational time and the Wasserstein-2 distance between the corresponding color palette and the color palette the target image. We observe that HSW gives better Wasserstein-2 scores than SW in both two shown images while the computation time is comparable. Similarly, the same
26

---

Published as a conference paper at ICLR 2023
EPICK 26 WiL
bww. 2672
Ofarci di MiA V,
Figure 8: Color transfered images and color palette with SW, HSW, GSW, and HGSW gradient flows. The computational time and Wasserstein-2 scores between corresponding color palate and the color palette of the target images are given next to name of the distances.
phenomenon happens in the of GSW and HGSW. Comparing non-linear projecting and linear projecting, non-linear variants cost about four times more computation while their Wasserstein-2 scores are higher. However, it is worth noting that better Wasserstein-2 score is not necessarily better since a non-linear transform creates a different flavor. Overall, the hierarchical approach in HSW and HGSW induces different gradient flows compared to SW and GSW which may yield some potential benefits.
F ADDITIONAL EXPERIMENTAL SETTINGS
Additional settings: For all datasets, the number of training iterations is set to 50000. We update the generator Go for each 5 iterations using (Max-)SW and (Max-) HHSW. Moreover, we update D a, and Dz,, the discriminator) every iterations. The mini-batch size m is set 128 in all datasets. We set the learning rate for Go. D2 and D3, 0.0002. The optimizer that
is Adam (Kingma Ba 2014) with parameters (11, 82) = (0, 0.9) (slightly abuse of notations). For SW HSW, we use p 2 (the order of Wasserstein distance).
FID scores and IS scores: We use 50000 random samples from trained models for computing the FID scores and the Inception scores. evaluating FID scores, we use all training samples for computing statistics of d
Neural networks: We present the architectures of our generative networks and the discriminative networks on CIFARIO, CelebA, and Tiny ImageNet as follow..
CIFAR10:
Gsi E (~ (NO, + 4 x 256 256(Dense,linear) - ResBlock up 256 -
ResBlock up 256 + ResBlock up 256 + BN, ReLU, + 3 x 3 conv, 3 Tanh.
-Da; x [1 1-1111323300 322x22x3
ResBlock down 128 - ResBlock down 128
ResBlock down 128 + ResBlock 128 - ResBlock 128.
Dz.: (Spectral normalization).
128x8x8
ReLU
Global sum pooling (128)
We the calculation from http://gsthbb.oomm//nniiiiinnnng
27

---

Published as a conference paper at ICLR 2023
CelebA and Tiny ImageNet:
Gs: R (~ ((.. + 4 x 4 x 256(Dense)linear) + ResBlock up 256 +
ResBlock up 256 + ResBlock up 256 + ResBlock up 256
BN, ReLU,
3 x 3 conv, 3 Tanh.
-Da;: E [-1, 11111x22322x
ResBlock down 128 ResBlock down 128 + ResBlock 128 - ResBlock 128.
ResBlock down 128
- DDg: I E 1 (Spectral normalization).
ReLU
7 Global sum pooling
7
28


Reviews:
[{"review_id": "pxMscYw8nB", "reviewer": "Reviewer_EUsv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "", "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.  ", "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. \n\n", "strength_and_weaknesses": "### Strengths: \n\n* The paper is well-written and well-motivated.\n* The paper is theoretically sound, and the experiments support the authors' claims.\n* 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.\n* The ablation study in Table 2 is really great! \n\n### Weaknesses: \n\nI 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: \n\n* 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?\n\n* 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?\n\n* 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. \n\n### Minor editorial: \n\nTypo - Page 3: \"the set of absolutely integrable function on\" should be \"the set of absolutely integrable functions on\"\n", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "a-0SRzkamSY", "reviewer": "Reviewer_CrfW", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "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.", "summary_of_the_review": "The paper can be improved if more comprehensive experiments are included to support the effectiveness of the proposed method.", "strength_and_weaknesses": "Strength:\n\nTheoretical 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.\n\nThe 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.\n\nWeakness:\n\nMy 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].\n\n[1] Soheil Kolouri, et al. \"Generalized Sliced Wasserstein Distances.\" NIPS, 2019.\n[2] Biwei Dai, and Uros Seljak. \"Sliced Iterative Normalizing Flows.\" ICML, 2021.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Z3hEPjHfB8", "reviewer": "Reviewer_XSPt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "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). \n\nHSWDs 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.", "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.", "strength_and_weaknesses": "### Strength ###\n- HWD: novel variant of sliced Wasserstein distance based on a hierarchal Radon transform.\n- HWD is a proper distance in the space of probability measures.\n- Equivalence between HWD, SWD, and Max-SWD.\n- Numerical experiments on generative modeling with HWD.\n\n### Weaknesses ###\n- 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. \n- 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).", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0ENVSDdyppn", "reviewer": "Reviewer_YGxc", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper introduces the Hierarchical Sliced Wasserstein (HSW) distance that is a variant over the Sliced Wasserstein (SW) distance.\nIn 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.\nTo 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.\nBoth properties of this HSW and experimental validation on generative modeling tasks are presented.", "summary_of_the_review": "The proposed method is very interesting and the paper is well-written.\nI 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.", "strength_and_weaknesses": "* Strengths\n    * The method is sounded.\n    * 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\n* Weaknesses\n    * 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.\n\nIn more details, I really enjoyed reading the paper and believe the contribution is interesting.\nHowever, I have the following remarks / questions:\n* 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\").\n* 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)?\n    * 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.\n    * This is also related to the discussion on \"Distributions of final projecting directions in HRT\", which concludes:\n        > To our knowledge, the manifold $\\mathcal{S}$ has not been explored sufficiently in previous works, which may be a potential direction of future research\"\n        * I believe providing informed thoughts on properties of this manifold would be a real plus for this paper.\n* 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.\n    * 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.\n\n\nI have a few extra minor comments:\n* \"which has columns are\" -> \"which columns are\"\n* [Titouan et al., 2019] -> [Vayer et al., 2019]\n* End of Section 3: the last sentence ends weirdly, probably a bad copy-paste\n* In Figure 3, using markers could help identify paired methods (which HSW variant corresponds, in terms of computation, to which SW variant)\n* \"In the Table 2, we reports\" (p. 8) -> report", "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:

Decision: Accept: poster