Heterogeneous Wasserstein Discrepancy for Incomparable Distributions
Authors: Mokhtar Z. Alaya
Gilles Gasso
Maxime Berar
Alain Rakotomamonjy
Venue: ICLR 2022 Submitted (2022)
Keywords: Optimal transport
Wasserstein distance
Incomprable distributions
Generative models

Abstract: Optimal Transport (OT) metrics allow for defining discrepancies between two probability measures. Wasserstein distance is for longer the celebrated OT-distance frequently-used in the literature, which seeks probability distributions to be supported on the $\text{\it same}$ metric space. Because of its high computational complexity, several approximate Wasserstein distances have been proposed based on entropy regularization or on slicing, and one-dimensional Wassserstein computation. In this paper, we propose a novel extension of Wasserstein distance to compare two incomparable distributions, that hinges on the idea of $\text{\it distributional slicing}$, embeddings, and on computing the closed-form Wassertein distance between the sliced distributions.  We provide a theoretical analysis of this new divergence, called $\text{\it heterogeneous Wasserstein discrepancy (HWD)}$, and we show that it preserves several interesting properties including rotation-invariance.  We show that  the embeddings involved in HWD can be  efficiently learned.  Finally, we provide a large set of experiments illustrating the behavior of HWD as a divergence in the context of generative modeling and in query framework.

Under review as a conference paper at ICLR 2022
HETEROGENEOUS WASSERSTEIN DISCREPANCY FOR INCOMPARABLE DISTRIBUTIONS
Anonymous authors Paper under double-blind review
ABSTRACT
Optimal Transport (OT) metrics allow for defining discrepancies between two probability measures. Wasserstein distance is for longer the celebrated OT-distance frequently-used in the literature, which seeks probability distributions to be sup- ported on the same metric space. Because of its high computational complexity, several approximate Wasserstein distances have been proposed based on entropy regularization or on slicing, and one-dimensional Wassserstein computation. In this paper, we propose a novel extension of Wasserstein distance to compare two incomparable distributions, that hinges the idea of distributional slicing, embed- dings, and on computing the glosed-form Wassertein distance between the sliced distributions. We provide theoretical analysis of this new divergence, called her- erogeneous Wasserstein discrepancy (HWD), and we show that it preserves several interesting properties including rotation-invariance We show that the embeddings involved in HWD can be efficiently learned. Finally, we provide a large set of experiments illustrating the behavior of HWD as divergence in the context of generative modeling and in query framework.
INTRODUCTION
Optimal Transport Transport-based data analysis has recently found widespread interest in machine learning community, since its significant usefulness to achieve many tasks arising from designing loss func- tions in supervised learning (Frogner et al.) 2015). unsupervised learning (Arjovsky et al.) (017). text classification (Kusner al., 2015). domain adaptation (Courty et al. 2017). generative models (Ar jovsky et al. 2017| Salimans et al. 20188, computer vision (Bonneel et al. 2011 Solomon et al. 2015) among many more applications (Kolouri et al. 2017 Peyré & Cuturi 2019). Optimal Transport (OT) attempts to match real-world entities through computing distances between distributions, and for that exploits prior geometric knowledge on the base spaces which the distributions are valued. Computing OT distance equals to finding the most cost-efficiency way to transport mass from source distribution to target distribution, and is often referred to as the
or Wasserstein
distance (Monge 1781] Kantorovich 1942. Villani 2009).
Matching distributions using Wasserstein distance relies on the assumption that their base spaces must be the same, that at least meaningful pairwise distance between the supports of these distributions can be computed. A variant of Wasserstein distance dealing with heterogeneous distributions and overcoming the lack of intrinsic correspondence between their base spaces is Gromov- Wasserstein (GW) distance (Sturm) 2006; Mémoli 2011). GW distance allows to learn an optimal transport-like plan by measuring how the similarity distances between pairs of supports within each ground space are closed. It is increasingly finding applications for learning problems in shape matching (Mémoli) 2011), graph partitioning and matching (Xu al., 2019), matching vocabulary sets between different languages (Alvarez-Man & Jaakkola, [2018), generative models (Bunne et al.) 2019). or matching weighted networks (Chowdhury & Mémoli] 2018). Due the heterogeneity of the distributions, GW distance uses only the relational aspects in each domain, such as the pairwise relationships to compare the two distributions. As a consequence, the main disadvantage of GW distance is its computational cost the associated optimization problem is a non-convex quadratic program (Peyré & Cuturi 2019), and as few as thousand samples can be computationally challenging. Based on the approach of regularized OT (Cuturi 2013). in which entropic penalty is added to the original objective function defining the Wasserstein OT problem, Peyré et al. (2016) propose an entropic version called entropic GW discrepancy, that leads to approximate GW distance. Another

---

Under review as a conference paper at ICLR 2022
SP-1
R
Sd-1
CENTER
8co
W (Ko,0,
S
R
But
LEFT
RIGHT
Figure 1: We measure the discrepancy between two distributions living respectively in RPP and R Our approach is based on generating random slicing projections distributions in each of the metric spaces Rº and Is through the mappings and vi of random projection vector sampled from an optimal distribution then compute ID- Wasserstein distance. It enables us learn the best projection mappings e and a and to optimize over the distributional part the generating projection distribution θ.
Rd. As each of the projected distribution results ID distribution, we
approach for scaling up the GW distance is Sliced Gromov- Wasserstein (SGW) discrepancy (Vayer et al. 2019), which leverages on random projections ID and closed-form solution of the ID-Gromov- Nerromov-Wassesttein
In this paper, we take different approach for measuring the discrepancy between two heteroge- neous distributions. Unlike GW distance that compares pairwise distances elements from each distribution, we consider method that embeds the metric measure spaces into a one-dimensional space and computes a Wasserstein distance between the two 1 DD-projected distributions. The key element of approach is learn two mappings that transform vectors from the unit-sphere of latent space to the unit-sphere of the metric space underlying the two distributions of interest, see Figure 1 In a nutshell, we learn to transform random direction, sampled under optimal (learned) distribution (optimality being made clear later), from a d-dimensional space to a random direction into the desired spaces. This approach has the benefit of avoiding an ad-hoc padding strategy (completion of 0 of the smaller dimension distributions to fit the high-dimensional one) as in SGW method (Vayer al. 2019). Another relevant feature of our approach that the two resulting 1D distributions are now compared through Wasserstein distance. This point, in conjunction, with other key aspect of the method, will lead to relevant discrepancy between two distributions, called heterogeneous Wasserstein discrepancy (H/WD). Although we lose some properties of distance, we show that HWD rotation-invarian that is robust enough to considered as loss for learning generative models between heterogeneous spaces. We also establish that HWD boils down to the recent distributional sliced Wasserstein distance (Nguyen et al. 2020) if the two distributions live in the same space and some mild constraints imposed the mappings.
In summary, our contributions are as follows:
we propose HWD, a novel slicing-based discrepancy for comparing two distributions living in different spaces. Our chosen formulation is based on comparing 1D projeced versions of the two distributions using a Wasserstein distance;
The projection operations are materialized by optimally mapping from one common space to the two spaces of interest. We provide a theoretical analysis of resulting discrepancy and exhibit its relevant properties;
Since the discrepancy involves several mappings that need to be optimized, we depict an alternate optimization algorithm for learning them;
Numerically, validate the benefits of HWD in terms of comparison between heteroge- neous distributions. We show that it can be used as loss for generative models or shape objects retrieval with better performance and robustness than SGW those tasks.
2

---

Under review as a conference paper at ICLR 2022
2 BACKGROUND OF OT DISTANCES
For the reader's convenience, we provide here a brief review of the notations and definitions, that will be frequently used throughout the paper. We start by introducing Wasserstein and Gromov- Wasserstein distances with their sliced versions SW and SGW, where we consider these distances in the specific case of Euclidean base spaces (R8 || II) and (R4, || II). We denote (XX) and ())) the respective sets of probability measures whose supports are con- tained on compact sets X' S I² and y S R". For r 2 1, we denote (,) the sub- set of measures in (X)) with finite r-th moment (r 2 1), i.e., (x) Jx dn(x)) for the collection of joint probability distributions with marginals μ and u. known as couplings, M(, v) = (+ E ( x y) AA C X, C CV,7(A x )) = ((A), 7X B) = (()).
{" ((x) so). For P. E (X) and E (V),, we write I( C P x ))
2.1 OT DISTANCES FOR НOMOGENEOUS DOMAINS
We here assume that the distributions μ and v lie in the same base space, for instance p q. Taking this into account, we can define the Wasserstein distance and its sliced variant.
Wasserstein distance The r-th Wasserstein distance is defined on P (X)) by
W)(,v)) (. inf || /xay1=
v1l'd1(2..)) :
-EIl(a.)) Xxxy
The quantity (,,,,,) 1/) describes the least amount effort to transform one distribution μ into another one v. Since the cost distance used between sample supports is the Euclidean one, the infimum in (I) attained (Villani 2009), and any probability 7 which realizes the minimum is called an optimal transport plan. In finite discrete setting, Problem (T) can be formulated as a linear program, that
is challenging to solve algorithmically as its computational cost is of order Onz log n) (Lee & Sidford (014). where is the number of sample supports.
Contrastingly, for the ID case (i.e. p 1) of continuous probability measures, the r-th Wasser- stein distance has a closed-form solution (Rachev & Rüschendori 1998), namely, Wr v) = (o. 1F (w)) pirical distributions, the ID- JD-Wasserttein distance simply calculated by sorting the supports of the distributions on the real line, resulting to a complexity of order On log This nice computational property motivates the use of sliced- Wasserstein (SW) distance (Rabin et al.. 2012] Bonneel et al.. 2015), where one calculates an (infinity) of 1D- ---Sassertteinn distances between linear projection pushforwards of distributions in question and then computes their average.
where F=1 and FT-1 are the quantile functions of and v. For em-
To precisely define SW distance, we consider the following notation. Let S--1 : {u E R ||u|| = 1} be the unit sphere in p dimension in norm, and for any vector 0 in SP-1 we define Po the orthogonal projection onto the real line RO = {aO E IR,, that is Pe(x)) = (0, x)), where (.-)) stands for the Euclidean inner-product. Let μi = Pa## the measure on the real line called
pushforward of u by Pa. that is (A) = μ(Pp (A)) for all Borel set A C IR. We may now define the SW distance.
Sliced Wasserstein distance The r-th order sliced Wasserstein distance hetween two probability distributions u.v px(x) is given by
SW, v) (12 _3
W,, (Ho, vo)o0)
where Ap is the area of the surface of 50-1 i.e., Ap function given as ((u) 5 gu-le-'dt. Thanks to its computational benefits and its valid metric property (Bonnotte, 2013), the SW distance has recently been used for OT-based deep generative modeling (Kolouri et al. 2019 Deshpande et al. 2019 Wu et al. 2019), Note that the normalized integral in (2) can be seen as the expectation for ~ oF the uniform surface measure on SP-1. that is SW, v) = (Egwgz-1 (Hg. ) Therefore, the SW distance can be casily approximated via Monte Carlo sampling scheme by drawing uniform random samples from g2-1.
T(p/2) with r
2/2
R R, the Gamma
3

---

Under review as a conference paper at ICLR 2022
(,, = K Ex=l (H vo.) where .I...... 0x s.d. Gp-1
and K is the number random
projections.
2.2 OT DISTANCES FOR HETEROGENEOUS DOMAINS
To get benefit from the advantages of OT in many machine learning applications involving heteroge- neous and incomparable domains (p # q). the Gromov-Wasserstein distance (Mémoli 201 stands for the basic OT distance dealing with this setting.
The r-th Sainov-Wasssesteinn distance between two probability distributions μ E (X) and E (D)) is defined by
Maanoo--assserseiin distance
(W, = inf (1) del. 1 SEtT(N..)
// X²
|| x'1l - 1ly v/
(fa=lllllnn((ts)ddbeee..)) (3)
2
x2
Note that GW, (1, v) is a valid metric endowing the collection of all isomorphism classes metric measure spaces of (x) x P,))), see Theorem 5 in (Mémoli 2011). The GW distance learns an optimal transport-like plan which transports samples from source metric space X' into target metric space V. by measuring how the similarity distances between pairs samples within each space are close. Furthermore, GW distance enjoys several geometric properties, particularly translation and rotation invariance. However, its major bottleneck consists in an expensive computational cost, since problem (3) non-convex and quadratic. A remedy to such heavy computational burden lies in entropic regularized GW discrepancy (Peyré et al. 2016). using Sinkhorn iterations algorithm (Cuturi 2013). This latter needs a large regularization parameter guarantee fast computation, which, unfortunately, entails poor approximation of the true GW distance value. Another approach to scale up the computation of GW distance is sliced-GW discrepancy (Vayer et al.) 2019). The definition of SGW shows ID-GW distances between projected pushforward of an artifact zero padding of distribution. We detail this representation in the following paragraph.
Sliced Gromov- Wasserstenn discrepancy Assume that < and let A be an artifact zero padding from X' onto Vi i.e. A(x) (x1,.... Tpp 0) RJ. The r-th order sliced Wasserreesse discrepancy between two probability distributions E P, (X') and v E P,()) is given by
Sg,a.,(u,u)
(9W: uo))
4
It is worthy to note that SGW is depending on the ad-hoc operator A, hence the rotation invariance lost. Vayer et al. (0119) propose variant of SGW that does not depend on the choice of A, called Rotation Invariant SGW (RI-SGW) for p 9, defined as the minimizer of SGW over the Stiefel manifold, see (Vayer et al., 2019 Equation 6). In this work. we are interested calculating an OT-based discrepancy between distributions over distinct domains using the slicing technique. Our approach is different from the SGW one many points, specifically (and most importantly) we use 1D- Wassesserntiin distance between the projected pushforward distributions and not 1D 1D-GW distance. In the next section, we detail the setup of our approach.
3 HETEROGENEOUS WASSERSTEIN DISCREPANCY
Despite the computational benefit of sliced-OT variant discrepancies, they have an unavoidable bottleneck corresponding to an intractable computation of the expectation with respect to uniform distribution of projections. Furthermore, the Monte Carlo sampling scheme can often generate an overwhelming number of irrelevant directions; hence, the larger number of sample projections, the more accurate approximation of sliced-OT values. Recently, Ercently,Nguyenn et al. (2020) have proposed the distributional-SW distance allowing to find an optimal distribution over expansion area of informative directions. This performs the projection efficiently by choosing an optimal number of important random projections needed capture the structure of distributions. Our approach for comparing distributions in heterogeneous domains follows a distributional slicing technique combined with OT metric measure embedding (Alaya et al. 2020
4

---

Under review as a conference paper at ICLR 2022
Let first introduce additional notations. Fix d 2 1 and consider two nonlinear mappings 6 gd-1 - 8P-1 and V Sd g9-1 For any constants Co. Co > O, we define the fol- lowing probability measure sets: Mc. = {o (P Egg,r-el(0(()) x(0)) < Co} and Mc. = {o E (( (g ( < Cv.. admissible constants the intersection sets Mc, n Mc. not empty. We hereafter denote M6.6 = Po Poco) #u and Pa.e = Py(a) #V the pushforwards of and v by projections over unit sphere Po(9) and Po(o), respectively.
. We say that Co, Cp are (Φ, +)-
Informal presentation While the distributions and are valued in different spaces, X C IP and Y C 2 any projected distributions will live in real line, enabling the computation distance (Figure T right). In order to generate random ID projections in each of the spaces, we map common random projection distribution from Sd into each of the projection spaces SP-1 and S7-1, through the mappings 6 and v (see Figure left). Hence, the main components of the heterogeneous Wasserstein discrepancy will be the distribution O E (Sd)))), and the two embeddings Φ and vi which will be wisely chosen. The resulting directions ((0) and (0) form the projections Po(o) and Po( (see Figure center) used to compute several ID- Do-Wasserstein distances.
ID-Wasserstein
3.1 DEFINITION AND PROPERTIES
Herein we state the formulation of the proposed discrepancy and exhibit its main theoretical properties.
Definition 1 The heterogeneous Wasserstein discrepancy (HWD) of order 2 1 between j (x) and u E P,y)) reads as
HWD,(H, = inf sup (Figee) (Mo,0, Mo.00] 6.v Mo Molls
$
(5)
HWD belongs to a family of projected OT works (Paty & Cuturi 2019 Rowland et al. 2019
Lin et al. 202T) with a particularity for seeking nonlinear projections minimizing sliced-OT variant. HWD further inherits the distributional slicing benefit by finding an optimal probability measure θ slices on the unit sphere gd-1 coupled with an optimum couple (Ø, v) of embeddings. Note that this optimal θ verifies the double conditions Eg.erell cos(e(0), ((0))) S Cs and Ee cos( tb (), (f")) I Cg. This gives that Co. Co I 1, hence the sets Mc. and Mc. belong to 11 = { E (S-) the set of all probability measures of the unit sphere gd-1 It is forced to
worthy note that for small regularizing (ó, -ddmmiisiee constants, the measure distribute more weights to directions that are far from each other in terms of their angles (Nguyen
al. )020).
Now, in order to guarantee the existence of (ó, v)) admiissbbe constants, we assume that the couple(ò, v) -embeddiis are approximately angle preserving.
Assumption (Approximately angle preserving property) For any couple (á. 1/) -embedddin assume that there exists two non-negative constants L&g and Tng. such that the following holds
(((()).((0)) < (6) 8')l and (vb((), ((8')) S (0,,6)))),,) for all 0, e
In Proposition] !
we deliver lower bounds of the regularizing (ø, -adddissiieee constants Co and Cg,, depending the dimension of the latent space d and on the levels (Lo, Lb) of approximately angle preserving property. These bounds ensure the non-emptiness of the sets Mc, and Mc..
Proposition 1
Let Assumption 7 holl and consider regularizing (ø, ----dmissibbee constants such (d/()
Ldd/2) Then the sets Mc. and Mc. contain the uniform that Co 2 (aT((d+1)/2) and Cyp 2 "aT((d+))2))
measure dd-1 and = - where (0I,... ,0,) forms any orthonormal basis in Rdd, Note that by Gautschi's inequality (Gautschi 1959) for the Gamma function, we have that Cs Le d
Le and
C
Proof of Proposition is presented in Appendix A.2 Together the admissible constants, the levels of angle preserving property, and the dimension d of the latent space form the hyperparameters set of
5

---

Under review as a conference paper at ICLR 2022
HWD problem. For settings of large d. the admissible constants could take smaller values, that force the measure & to focus on far-angle directions. However, for smaller d, we may lose the control on the distributional part, the set Mc tends to 1 the entire set of probability measure on S hence it boils down on a standard slicing approach that needs an expensive number of projections to get an accurate approximation. Next, give set of interesting theoretical properties characterizing HWD.
Proposition 2 For any 2 L. HWD satisfies the following properties:
(i) HWD,(u: v) is finite, that HWD, (p, v) S - (Mr(w) + M,(1)) where M,(-) the r-th moment of the given distribution, i.e. M,(μ)= = (Ix
(i) HWD,(u, is non-negative, symmetric and verifies HWD, n) O.
(iii) HWD,, v) has discrepancy equivalence given by
2 inf max Wr(Hg.0, vx.00 S HWD,(u, S inf max Wr(sa, Mo.0) 4.8 BEge-1
0.0 BEB--1
(iv) For p = q. HWD is upper bounded by the distributional sliced Wasserstein distance.
(v) HWD, is rotation invariant, namely, HWD, (R Qu) = HWD,[p, v), for any E O {R R R Ip] and Q Og = (Q E R :Q Ig), the orthogonal group of rotations of order p and respectively.
(vi) Let To and T3 be the translations from IP into Rº and from R into I2 with vectors and B, respectively. Then HWD, (Ta u,, To#t)= S -HW----WHH,HH--- (1,, u) + ||x]|| II)
Proof of Proposition 2 is given in Apprendix A.1 From property (i) HWD is finite provided that the distributions in question have a finite r-th moments. Note that the supremum over the probability measure sets Mc. and Mc. guarantees the property HWD, μ)) = 0. For p q. if the infimum over the couple (ø, -embedding in (iit) is realized in the identity mappings, then HWD verifies metric equivalence with respect to the max-sliced Wasserstein distance (Deshpande et al.) (2019). The property (v) highlights rotation invariance of HWD, which is well verified by the GW distance.
3.2 ALGORITHM
Computing HWD requires a resolution of an optimization problem as given in (5) In what follows, we propose an algorithm for computing an approximation of this discrepancy based on samples X X= (=x))<= from μ and samples Y { from At first, let us note that we have min-max optimization to solve; the minimization occuring over the embeddings & and & and the maximization over the distributions on the unit-sphere. This maximization problem is challenging due both the constraints and because we optimize over distributions. Similarly to Nguyen et al. (2020), we approximate the problem by replacing the constraints with regularization terms and by replacing the optimization over distributions by an optimization over push-forward of the uniform probability
measure d by a Borel measurable function f Sd-1 - 1d-1 Hence, assuming that we have drawn from a uniform distribution K directions {0x] k= the numerical approximation of HWD obtained by solving the following problem:
K
min max {Ia del. 0.0
Σ
W; (((()))) (T "(((w)))
K
+ min Ao L2
Σ ((0(000"~(0000) + ([(00)]<(((00)))
A.Ke
+ min Aa
def.
((f(0.)) (0lf0O))T 0 0v) Σ ([F(0)))([[(()))))) 02 0x)
where the first term in the optimization is related to the sliced Wasserstein, the second term is related to the regularization term associated to Eg (d)(), II) and Eg.er (v) ((())) (0))) and the third term is the preseevre regularization term. Note that the min term with respect to is due to the fact that we want those regularizers be small. Two hyperparameters d and X

---

Under review as a conference paper at ICLR 2022
Algorithm 1 COMPUTING HETEROGENEOUS WASSERSTEIN DISCREPANCY (SEE (5)
Input: Source and target samples: (X, ju) and (Y, v); order r; the set of random direction
(0x MRJRR=i T number of global iterations; N number of iterations for each of the alternte scheme;
2: Output: HWD
3: function COMPUTE LOSSES(X, Y, ([+()+)] +[f(0)))
4:
compute the average ID- Wasserstein L1 between X ((f( and Y TT [fx())
5:
compute the inner-pur unner-product penalty L2
6: compute the angle-preeerving penalty L
7:
end function
8: for t = 1,... . do
9:
fix Φ and v
10:
for i 1, 1. N do
compute (fx( and [[({+)]]
12:
L1, L,, La + Compute Losses (X, Y, ([S(0=)] (())))
L L1 + L2 + La
14:
[ { 7& V.
15:
end for
16:
fix f
17:
for
= 1, .N. do
18:
compute (fx( and [0xx]
19:
L1, L2, La & Compute Losses XXYY (00000))0)).))))))))
20:
L L1 L2 La
21:
Φ - 7/ VL
+ 3 7k VL
23:
end for
end for
25:
HWD < compute the average over {0:) of closed-form 1D Wasserstein between
X xTo(((Bx) and (T(()(()))
26:
Return: HWD
control the impact of these two regularization terms. In practice, 6, vi and f are parametrized as deep neural networks and the min-max problem is solved by an alternating optimization scheme; (a) optimizing over f with zb and & fixed then (b) optimizing over uf and ó with f fixed. Some details of the algorithms are provided in Algorithm [
Regarding computational complexity, if we assume that the mapping f. Φ, v are already trained, that we have K projections, and that @ (0x)) [f() are precomputed, then the computation of HWD (line 25 of Algorithm [T) is in O (n log n + np n4)), where n is the number of samples in X and When taking into account the full optimization process, then the complexity depends on number of times we compute the full objective function we are optimizing. Each evaluation requires the computation of the sum in L1 which is O(K (n log n + np + nq)) and the two regularization terms L2 and L3 require both O (p + q 2d)). Note that in terms of computational complexity, SGW OKKn log n) whereas HWD is O(TN K'n log n). with x N being the global number of objective function evaluations. Hence, complexity is in favor of SGW. However, in practice, because we optimize over the distribution of the random projections, we usually need less slices than SGW and thus depending on the problem, TNK K. can be of the same magnitude than the number of slices involved in SGW (similar findings have been highlighted for Sliced Wasserstein distance (Nguyen et al. 2020)).
should note that
NUMERICAL EXPERIMENTS
In this section, we analyze HWD, exhibit its rotation-invariant property, and compare its performance with SGW in generative model context.
Translation and Rotation We have used two simple datasets for showing the behavior of HWD with respect to translation and rotation. For translation, we consider two 2D Gaussian distributions one being fixed, the other with varying mean. For rotation, use two 2D spirals from Scikit-Leearn
7

---

Under review as a conference paper at ICLR 2022
Figure 2: Examples of distance computation between (left) woo-translating Gaussian distri- butions. (right) two spirals.
Figure 3: Examples of target distribu- tions for generative models (left) 3D 4-mode. (right) 2D 5-mode.
library, one being fixed and the other being rotated from 0 to π T/2. For these two cases, we have drawn 500 samples, used 100 random directions for SGW and RI-SGW. For our HWD, have used only 10 slices and T = 50, N 5 iterations for each of the altemnat optimization. The results we obtain are depicted in Figure From the first panel, we remark that both SGW and RI-SGW are indeed insensitive to translation while HWD captures this translation, which is also verified by property (vi) in Proposition For the spiral problem, as expected HWD and RI-SGW are indeed rotation-invariant while SGW not.
Generative models For checking whether our distribution discrepancy behaves appropriately, we have used it a loss function generative model. Our task here is to build model able to generate a distribution defined on a space having a different dimensionality from the target distribution space. As such, we have considered the same toy problems in Bunne al. (2019) and investigated two situations: generating 2D distributions from 3D data and the other way around. The 3D target distribution is a Gaussian mixture model with four modes while the 2D ones are 5-mode. Our generative model is composed of fully-connected neural network with ReLU activation functions. We have considered 8000 samples in the target distributions and batch size of 300. For both HWD and SGW, we have run the algorithm for 30000 iterations with Adam optimizer, stepsize of 0.001 and default 3 parameters. For the 4-mode problem, the generator a ML.P with layers while for the 5-mode, the problem is more complex, it has 3 layers. In each case, have 256 units the first layer and then 128. For the hyperparameters, we have set Àc depending the problem. Note that for SGW, have also added fn-nrrm regularizer output of the generator in order to avoid them to drift (see Figures 8 and | in Appendix (C), as the loss manilattionnnnariant Examples of generated distributions are depicted in Figure 4 We remark that our HWD is able to produce visually correct distributions whereas SGW struggles in generating the modes and its 3D 5-mode squeezed its third dimension.
and A = 5 or A = 50
the
Scalability We consider the non-rigid shape world dataset (Bronstein et al. 2006) which consists of 148 three-dimensional shapes from 12 classes. We draw randomly n {100, 250, 500, 1000, 1500, 2000} vertices {a; E 13 Ji=ı on each shape and use them to measure the similarity between a pair of shapes {ar E [R3 }= and {リ) E R31 F reports the average time to compute SGW and HWD. As expected GW exhibits a slow behavior while the computational burden of HWD on par with SGW.
single core such a similarity for 100 pairs of shapes using respectively GW,
Classification under various transformations This experiment, whose details provided in Appendix B.2 aims evaluate the bustness of SGW and HWD (the computationally efficient methods) different transformations terms of classification accuracy. To that purpose we employ the Shape Retrieval Contest (SHREC'2010) correspondence dataset, see Broostein et al. (2010) It includes high resolution (10K-50K) triangular meshes. The shapes are of 3 classes (see Figure i0 Appendix[Ci with 9 different transformations and the null shape (no transformation). Each transformation is applied up to five strength levels (weak to strong). Along with the null shape, consider all strengths of the "isometry". "topology". "scale". "shotnoise" transformations leading to 63 samples. We perform a 1- NN classification. Obtained performances over 10 runs depicted
0115
SGW
Figure 6: Classification perfor- mance under transformations.
8

---

Under review as a conference paper at ICLR 2022
Seat 2000
Bestio 200B
Figure 4: Examples of generated distributions across iterations (10, 10000, 20000, and 30000) for two targets.Fron From top to bottom (first-row) HWD for the 4-mode. (second-row) SGW for the 4-mode (third-row) HWD for 3D 5-mode. (fourth-row) SGW for 5-mode. For each row, the last panel shows the evolution of the loss over the 30000 iterations.
SGW
HMD
Burnns
Number muntes mach s7Rce
Figure 5: Computation time with respect to n, the number of vertices on each shape. (Left-panel) Instances of 3D objects. (Right-panel) Running time.
in Figure 6 They highlight the ability of HWD be robust perturbations. HWD achieves slightly better mean classification accuracy than SGW with a competitive computation time (see FigureB) Notice that GW and RISGW unable run under reasonable time-budget constraint.
CONCLUSION
We introduce in this paper HWD novel OT-based discrepancy between distributions lying different spaces, It takes computational benefits from distributional slicing technique, which amounts to find an optimal number of random projections needed to capture the structure of data distributions. Another feature of this discrepancy consists in projecting the distributions in question through a learning of embeddings enjoying the same latent space. We showed nice geometrical property verified ination-invariance. We illustrated through extensive
by the proposed discrepancy, specifically experiments the applicability of this discrepancy on generative modeling and shape objects retrieval. We argue that the implementation part faces the standard deep learning bottleneck of tuning the model's 's hyperparameters. A future extension line of this work is to deliver theoretical guarantees regarding the regularizing parameters, both of distributional and angle preserving properties.

---

Under review as a conference paper at ICLR 2022
REFERENCES
M. Z. Alaya, M. Bérar, G. Gasso, and A. Rakotomamonjy. Theoretical guarantees for bridging metric measure embedding and optimal transport, 2020.
D. Alvarez-Melis and TT. Jaakkola. Kromov-Wasseree alignment of word embedding spaces. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 1881-1890, Association for Computational Linguistics, 2018.
M. Arjovsky. S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 214-22142 223, International Convention Centre, Sydney, Australia, 2017. PMLR.
N. Bonneel, M. van de Panne, S. Paris, and W. Heidrich. Displacement interpolation using lagrangian mass transport. ACM Trans. Graph., 15:11:15: 2011.
N. Bonneel, J. Rabin, G. Peyré, and H. Pfister. Sliced and Radon Wasserstein barycenters of measures. 51(1), 2015.
N. Bonnotte. Unidimensional and Evolution Methods for Optimal Transportation. Theses, Université Paris Sud Paris XI: Scuola normale superiore (Pise, Italie), December 2013.
A. Bronstein, M. Bronstein, U. Castellani, B. Falcidieno, A. Fusiello, A. Godil, L. Guibas, I. Kokkinos, Z. Lian, M. Ovsjanikov, G. Patane, M. Spagnuolo, and R. Toldo. SHREC 2010: robust large-scale shape retrieval benchmark. Eurographics Workshop on 3D Object Retrieval(2010), Norrköping, -1, 2010-05-02 2010.
A. M Bronstein, M. M. Bronstein, and R. Kimmel. Efficient computation of isometry-invariann distances between surfaces. SIAM Journal Scientific Computing, 28(5):1812-1884 2006.
C. Bunne, Alvarez-Melis, A. Krause, and Jegelka. Learning generative models across incompa- rable spaces. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 851-861, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
S. Chowdhury and Mémoli. The Gromoy-Wasse Wasserstein distance between networks and stable network invariants. CoRR, Abs/1808.04337, 2018.
N. Courty, R. Flamary, Tuia, and A. Rakotomamonjy. Optimal transport for domain adaptation. IEEE transactions on pattern analysis and machine intelligence, 39(9):1833-186) 2017.
M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In C. J. C. Burges, I.. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Informa- fion Processing Systems 26, pp. 2292-2300. Curran Associates, Inc., 2013.
I. Deshpande, Y.-T. Hu, R. Sun, A. Pyrros. N. Siddiqui, S. Koyejo, Z. Zhao, D. Forsyth, and A. G. Schwing. Max-sliced Wasserstein distance and its use for gans. In 2019 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 10640-10648, 2019.
R. Flamary, N. Courty, A. Gramfort, M. 7. Alaya, A. Boisbunon, S. Chambon, I. Chapel, A. Corenflos, K. Fatras, N. Fournier, L. Gautheron, N. T.H. Gayraud, H. Janati, A. Rakotomamonjy, Redko, A. Rolet, A. Schutz, V. Seguy, D. J. Sutherland, R. Tavenard, A. Tong, and T. Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8 2021.
C. Frogner, C. Zhang, H. Mobahi, M. Araya, and T. A. Poggio. Learning with Wasserstein loss. In C. Cortes, N. D. Lawrence, Information Processing Systems 28, pp. 2053-2061. Curran Associates, Inc., 2015.
Lee, M. Sugiyama, and R. Garnett (eds.), Advances Neural
W. Gautschi. Some elementary inequalities relating to the gamma and incomplete gamma function. Journal of Mathematics and Physics, 38(1-)::77-81, 1959.
L. Kantorovich. On the transfer of masses (in russian). Doklady Akademii Nauk, 2:227-229, 1942.
10

---

and applications to Under review as a conference paper at ICLR 2022
S. Kolouri, S. R. Park, M. Thorpe, D. Slepcev, and G. K. Rohde. Optimal mass transport: Signal processing and machine-led leannin applications. IEEE Signal Processing Magazine, 34(4):43-55 July 2017.
S. Kolouri, P. E. Pope, C. E. Martin, and G. K. Rohde. Sliced Wasserstein auto-encoders. In International Conference on Learning Representations, 2019.
M. Kusner, Y. Sun, N. Kolkin, and K. Weinberger. From word embeddings to document distances. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learming Research, pp. 957-966, Lille, France, 07-09 Jul 2015. PMLR.
Y. T. Lee and A. Sidford. Path finding methods for linear programming: Solving linear programs in O(vrank) iterations and faster algorithms for maximum flow. In Proceedings of the 2014 IEEE 55th Anmual Symposium on Foundations of Computer Science, FOCS '14, pp. 424 433, Washington, DC, USA, 2014, IEEE Computer Society.
N. Lerner Course Integration Theory. Springer Basel, 2014.
T. Lin, Z. Zheng, E. Chen, M. Cuturi, and M. Jordan. On projection robust optimal transport: Sample complexity and model misspecification. Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings The 24th International Conference Artificial Intelligence and Statistics, volume 130 Proceedings of Machine Learning Research, pp. 262-270. PMLR, 13-15 Apr 2021.
F. Mémoli. Cromov-Wassersiee distances and the metric approach to object matching. Foundations of Computational Mathematics, 1144):117-487 2011.
G. Monge, Mémoire théotic des déblais des remblais. Histoire de l'Académie Royale des Sciences, pp. 666-704, 1781.
K. Nguyen, N. Ho, T. Pham, and H. Bui. Distributional generative modeling, 2020.
F.P. Paty and M. Cuturi. Subspace robust Wasserstein distances. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.). Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5072-5081, Long Beach, California, USA, 2019. PMLR.
G. Peyré. M. Cuturi, and J. Solomon. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, pp. 2664-2672. JMLR.org, 2016.
averaging of kernel and distance matrices.
G. Peyré and M. Cuturi. Computational optimal transport. Foundations and Trends@ in Machine Learning, 1(5-6))355-6677 2019.
J. Rabin, G. Peyré, J. Delon, and M. Bernot. Wasserstein barycenter and its application to texture mixing. In A. M. Bruckstein, B. M. Haar Romeny, A. M. Bronstein, and M. M. Bronstein (eds.), Scale Space and Variational Methods in Computer Vision, pp. 435-446, Berlin, Heidelberg. 2012. Springer Berlin Heidelberg.
S.T. Rachev and L. Rüschendorf. Mass Transportation Problems: Volume Theory, Mass Trans- portation Problems. Springer, 1998.
M. Rowland, J. Hron, Y. Tang, K. Choromanski, T. Sarlos, and A. Weller. Orthogonal estimation of Wasserstein distances. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Eieety-Seconde International Conference Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 186-195. PMLR, 16-18 Apr 2019.
T. Salimans, H. Zhang, A. A.Rafford, and D. Metaxas. Improving GANs using optimal transport. In International Conference Learning Representations, 2018.
J. Solomon, F. de Goes, G. Peyré, M. Cuturi, A. Butscher, A. Nguyen, T. Du, and L. Guibas. Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. Graph., 34(4):66:1 1003:6661166:1111 2015.
11

---

Under review as a conference paper at ICLR 2022
K. T. Sturm. On the geometry of metric measure spaces. ii Acta Math., 196(1::133-177, 2006.
T. Vayer, L. Chapel, R. Flamary, R. Tavenard, and N. Courty. Fused Gromoy- -asoov--eesssteenn distance for structured objects: theoretical foundations and mathematical properties. CoRR, (lss/1811.022 2018.
Vayer, R. Flamary, N. Courty, R. Tavenard, and Chapel. Sliced Noomov-Wassersteinn In H. Wallach, H. Larochelle, A. Beygelzimer, F. Alché-Buc, E. Fox, and R. Garnett (eds.), Advances Neural Information Processing Systems 32, pp. 14736-14736. Curran Associates, Inc., 2019.
C. Villani. Optimal Transport: Old and New, volume 338 of Grundlehren der mathematischen Wissenschaften. Springer Berlin Heidelberg. 2009.
J. Wu, Z. Huang, D. Acharya, W. Li, Thoma, D. P. Paudel, and L. V. Gool. Sliced Wasserstein generative models, 2019.
H. Xu, D. Luo, and L. Carin, Scalable Gromov-Wasserstein learning for graph partitioning and matching. In Advances in Neural Information Processing Systems 32: Annual Conference
Neural Information Processing Systems 2019, NewrIPS 2019, 8- December 2019, Vancouver, BC, Canada, pp. 3046-3056, 2019.
12

---

Under review as a conference paper at ICLR 2022
A PROOFS
A. 1
PROOF OF PROPOSITION
We use the following result:
Lemma
[Theorem 3 in (Nguyen al. 2020i] For uniform measure σd-1 on the unit sphere Sd-1
we have
r(d/2)
110, 1 (0))o
vTT((d+1)/2
Hence,
(Ascumption
L$ 88-1
(0)
g x80-1
(Lemmnl)
LdI(d/2)
VTI((d 1)/2)
Therefore, as long the (Ø, -admiissibee constants Co VFI((d+11/2) and C Lgd(d/2)
LaI(d/2)
(TT+((1)/2))
we have d MMc. O Acc. Now using a Gautschi's inequality (Gautschi, 1959) for the Gamma T(d/2)
function, it yields that ((++1)2) 2 v=(d+1)/2 2 1/d. Let Eiz1 à 50.- where (f1,...,0) 0d)
form an orthonormal basis Rd. We then have
Eg,0-~ [k)())
E (10((00)) ((0))
(Assumption)
L
Σ
2
d
(0L,
Lub 611
d
IshIsa
Iskldd
Therefore we get the lower bounds for the (ø, addmissiib constants Co and Cp given in Proposi- tion that guarantee gd-1, ,0 Mc, Mc..
A.2 PROOF OF PROPOSITION 2
Let us first state the two following lemmas: Lemma@ an integration result using push-forward measures; it relates integrals with respect to measure and its push-forward under measurable map f X' > V. Lemma proves that the admissible set couplings between the embedded measures are exactly the embedded of the admissible couplings between the original measures.
Lemma 2 Lerner (2014) 61] Let f S + T be a measurable mapping, let n be measurable measure on S, and let g be measurable function on T. Then Jy gdf = Js(9 o fddy
Lemma 3 [Lemma 6 in Paty & Cuturi [2099] I For all o, v and E (X), E PV), one has 1o u, ww {(ó @ #Y s.t. y M[ w)}, where & & tb X x y - X y such that (ob 8 (1a v) = (0(x), (by)) for all x, y E X X.
HWD, ni) is finite. In one hand, we assume that μ (X) and (P)),, hence its r-th moments are finite, i.e., M,(u) (Jxx d)(a)) 1/r < oo and M, (v) = (Jy ( 1/r co. In the other hand, the following holds for all parameter 0 E sd-1 and a couple (Ø, embeddingss
inf (T vg.0) *EII( (1.)))
|u n' d''dx(u, RXR
(Lemma inf 10(0)== (0) wl (x,,) rETl(M))
Jxxy
2 inl 7ET((IN) XXX (10(0) TT|" (0(0) w/" (1),))
x1 ( Tx du(x)) / [2()]] 21" dv(v)
-1 inf rEll(u.))
13

---

Under review as a conference paper at ICLR 2022
where we use the facts that (s - t)" I 2s' + +t"), Vs, Vs, R4 and that any y transport plan has marginals i on d' and V/ on V. By Cauchy- Schwarz inequality, we get
11 / [100)))1bl| -2- (M, + MT(1)). Then, (Ee- (WT k)) 1/r S 2 Finally, one has that HOWD, S 22 (M.(p) + M,(v)).
(1 = -2- (/x (0(0)))1):))))))))))
MF(U)) S 2 (M.()) + M,(w)).
(it) Non-negativtty and symmetry. Together the non-negativity, symmetry of Wasserstein distance and the decoupling property of iterated infima (or principle of the iterated infima) yield the non- negativity and symmetry of the distributional sliced sub-embedding distance.
(ii) HWD, (1,, ui) = O. Let & and ø' two embeddings for projecting the same distribution J.. Without loss of generality, we suppose that the corresponding (o, o') aadmmisbee constants C² S Co. hence Mc.. S Mc.. Using the fact that sup(A n B) sup A A sup B, (with a A 6) min(a, b)), se have, straightforwardly.
HOWD inf 0. Be.
sup
(MT (or
# #) (RoLe(W) (or.0)
S inf 0.0
sup .EA.C
sup BElloN
inf inf + &
sup Be
(M
sup BeAlley
< inf
sup Hc.Mo.
[Lse (M
sup Ne-Mow
S inf sup & Oc.Nos (Egne (T $
0.
(iti) One has (2) inf maxpega-1 Wr Up,0) S HWD, v) S iinfew maxges"-1 Wr Wr Po.0) S max 1 W. (1o.0, vv.e) we find that
Since Mcs n Mc. C M. and
( (M.,o,.,
sup BE- nMc
sup 0..41
max WT (o.)) 1/r aega-1
max 0E34-1
W.(ms,o.
which entails that HWD,, v) S inf maxgest-1 W. Vo.0). Moreover, since the ()) à and Cv 2 Eg o hence ē = Σi_ foo. Mc. 0
admissible constants Co and Cv satisfy Co 2 Uy
Mcg, where we set 0₃ = argmaxpesa- W, (. U).0). We then obtain
HWWD(W, 2 inf (Ea (H.,o))))))))) $ 0.
WT (M 7
inf
0.1
1/r
inf Wr (1 k1000) 0.v'
(
1/r inf max W vg.0).
2. 0es4
14

---

Under review as a conference paper at ICLR 2022
(iv) For p p= q, HWD is upper bound by the distributional Wasserstein distance (DSW). Let us first
recall the DSW distance: let C > 0 and set Mc = =f ((8 1) Egg www.wllll...... (0)l S C}.
(FaLo Uo)) 7
(,, = sup
BE.
We have that the case of a identity couple of embeddings, Φ Id, 1 = Id, the probability measure set Mc., Mc. then it is trivial that HWD,,(,, - (H, v),
(v) Rotation invariance. Note that (R# Po(o) # (R# (Pa(o) R)# and for
all x RP, using the adjoint operator R" (R" = RRR )) (Po(o) R)(x) (0(0), R(x))
(R* (6(0)))) (1) Then, (R#u)ø0
(o()))()) Hu. Analogously, one has
(Q#V)v.0 = (PQrov(0)) Moreover,
Mc. = () 0 (l(00)))(((0))).mm)))))))))))))) ((')))
=1 E (1 E (( o (0), (R* . ())))
=oRros'
Then we have similarly Mcs Coroo
This implies
(Q#w)o.))) $ EEne (PP porow()) (obr((())t1)))))) [Hvl]]
HRW, QHV) = inf 0.1 Ne.
sup
= inf
sup Mos
(Eae (WT (Mo. 7
inf
sup
0.1 Ne,
= innf
sup
Egno (4
0.10 a GE
nc
= inf
sup
(Eone W (
VQ-
0.1 θe Me R n caros
Eg~o ( 7
inf =f v/ = Q on ee Mc n.
sup
= (H,
(vi) Translation quasi-invariant We have
(Tat inf sup a. tc, nollo
[Wr (Ta (Tot)))0)))
By Lemmas and WT (Ta#t)
we have
/ |u uo--ol'dl o('dr(u,
inf (enn(T
inf rEU((PsO) To (P (v)) / |u - dl"d)(u,e)
R2
inf (Poo) o Ta(x) Pu(e) (T)(y)
rell(H..) XXX /
inf >ETT(uN)) JxxY (P)ro)(x)) - (w)) ((P (a) (wo0)))cre
I (,(inf inf (p(o (z)
< 22"-1
+ (a)o((a) Poron (B))
(Ell(HH.)) XxY
2-'1 inf
(x) - Pule + (||a)) + 11811))
(Ell(pm) xxx
15

---

Under review as a conference paper at ICLR 2022
Thanks to Minkowski inequality,
(Ta#t)))1)
sup B. Mc,
inf vEtTimm) / ((Po10)()) (oo00()))P
2"
sup
(Ewe
Xxxx
+ 2" (I|a|] + 1111
sup N.Ate
(0(80-1))
2--1 sup GE, n.M
Ee-e W (Mose) +2a=1([aa1 11.11).
Therefore, we get
Tott) < (,W 2 (( + [|3])).
B
IMPLEMENTATION
This section graphically describes the learning procedure in Algorithm details not exposed in the main body of the paper.
1
It also provides the training
B. LEARNING SCHEME
We present in Figure the updated graphics of our approach, highlighting the main components the distributional part is ensured by first deep neural network is each of the mappings. As each of the networks should be learned, we included the part the loss functions associated with each network (blue fonts correspond to minimization, whereas red fonts correspond to maximization, Algorithm section).
De. ([](>)))
[[[000]] TT0)² -[ Ee.e v[S(O+)] [(((x))
SP-1
RP
Parten Prymo
Sd-1
Wilpess
W Wolngnee
1/r
Σ
K
W, Wx[x
R
S9-1
RV q
Panken
Payna
ELN' o[f(Oa)] o(f(Ow) [( Ex.e (dlf(0x))
olf(0w)) [ol((o))][l(((w))
02)
Figure 7: The implemented approach. Both the distributional and mappings parts are achieved by deep neural networks, A number K of projections is used to compute ID-Wasserstein distances.
B.2 TRAINING DETAILS
Our experimental evaluations on shape datasets for scalability contrast GW. SGW and HWD. Re- garding classification under isometry transformations, additionnally consider RI-SGW. Used
16

---

Under review as a conference paper at ICLR 2022
hyper-parametent for those experiments detailed below. Notice that SGW, RI-SGW and HWD rely on K, the number of projections sampled uniformly over the unit sphere. This may vary from method to another.
1. SGW: K.
2. RI-SGW: ARI-SGW. the learning rate and T, the maximal number of iterations for solving over the Stiefeld manifold.
3. HWD: beyond K and the latent space dimension d, it requires the parametrization of Φ, s and f as deep neural networks and their optimizers. For solving the min- max problem by an alternating optimization scheme use N inner loops and T number of epochs.
For SGW and RI-SGW we use the code made available by their authors and cite the related reference Vayer et al. (018)) as they require. We use POT toolbox Flamary et (202T) to compute GW distance.
Scalability This experiment measures the average running time to compute OT-based distance between two pairs of shapes made of 3D-vertices. 100 pairs of shapes considered and varies in {100, 250, 500, 1000, 1500, 2000}.
We choose Ksaw 1000
default value).
For HWD. the mapping function f is designed as a deep network with dense hidden layers of size 50. Regarding both & and v/, they have also the same architecture as f (with adapted input and output layers) but the hidden layers are 10-dimensional. Adam optimizers with default parameters are selected train them. Finally we consider KHWD 10, d 5, T 50, N Notice also that the regularization parameters Ac and A are set to 1.
default values.
The used ground cost distance for GW distance is the geodesic distance.
Classification under transformations invariance For this experiment, we consider the same set of hhyer-parametert as for Scalability evaluation on shape datasets. Besides, the supplementary com- petitor RI-SGW was trained by setting KRI-SGW TRI-SGW = 500. Notice that due to the high-resolution of the meshes (more than 19K three- dimensional vertices), RI-SGW and GW were not able to produce the pairwise -irriseedisstnce matrix used INN classification after several hours.
1000 Ksaw 1000, ARI-SGW 0.01,
C ADDITIONAL EXPERIMENTAL RESULTS
Figure 8: Comparing (top) HWD and (bottom) SGW on generating 2D distributions from 3D target.
17

---

Under review as a conference paper at ICLR 2022
teviton
Reneow IreSe
Reyaee 20099
Realee 36930
ICOOE
20000
Figure 9; Comparing (top) HWD and (bottom) SGW on generating 3D distributions from 2D target.
2onetr2 Iseety
NeMPY Beways
Bevety:
boeets
benety
bonery bewary
tomeery
beeaay
homery
tamerry
Isneey
Figure 10: Instances of the shape dataset with null and isometry transformations. The classes are respectively human, dog and horse. For the experiments of Figure 6 we also consider the "topology", "scale", "shotnoise" transformations that respectively amount to deform, to upscale and to add noise to the shapes of each class.
18


Reviews:
[{"review_id": "UL9EM2V7qL6", "reviewer": "Reviewer_xwxk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ Strengths:\n\nThe authors propose a new variant of optimal transport for distributions supported in different spaces.\n\n+ Weaknesses:\n\nIt seems that the contribution is quite incremental. It combines the approach in Alaya et al., 2020 to deal with distributions supported in different spaces via embedding for optimal transport, and the distributional sliced Wasserstein (Nguyen et al., 2020) to project into 1d-dimensional space to compute Wasserstein (instead of standard Wasserstein in some latent space in Alaya at al., 2020).\n\n+ Detailed comments:\n\n1. It seems that the main problem is that supports of distributions are living in different spaces. In case, one can learn the embedding as in Alaya et al., 2020 (e.g, about \\phi, \\theta embedding) -- which is also used as the main part of the proposed approach, the remaining problem is the optimal transport between distributions supported in some \"latent\" space. The latter part is the application of distributional sliced Wasserstein. Am I missing something?\n\n2. As in the setting, distributions are supported in different spaces. So, even the dimension of those spaces are equal, they are still unaligned (e.g., different basic coordinates). So, for the 1d-projection, I wonder why the Wasserstein is favored than the Gromov-Wasserstein to align for those 1d-projected supports. (Imagine that the \"arrow\" object points to the positive infinity in 1d-space, but in other 1d-space, the \"arrow\" object points to the negative infinity in another 1d-space. Could you comment for such situations?)\n\n3. For the Definition (5) for the proposed heterogeneous Wasserstein discrepancy (HWD), it seems that it is highly non-convex, and more \"complicated\" than the Gromov-Wasserstein (GW) in Equation (1)? E.g., HWD requires to optimize 2 embedding functions (\\phi, \\theta)? Could the authors comment why HWD is \"intuitively\" easier to solve than GW? \n\n4. For complexity, why T=50 and N=1 are used? (especially N=1?) It seems that Algorithm 1 is alternating optimization?\n\n5. For experiments about the translation (in Figure 2), is translation-invariant a good or bad property? (for distributions supported in different spaces)\n\n6. For Figure 4, it seems \"abrupt\" for iteration 10K and iteration 20K, it is better in case the authors show more figures in that range (at least in the supplementary).\n\n7. What are the stopping conditions for GW and RISGW in experiments? \n\n8. In Figure 5, for time complexity, HWD is much faster than GW and is also faster than SGW when there are more than 1K meshes per each shape. Recall that the complexity of SGW is O(nlogn), it is unclear why HWD can be even faster? Am I missing something (HWD is highly non-convex, and requires to optimize two embedding functions together with the distribution for distributionally sliced-Wasserstein).\n\n", "summary_of_the_paper": "The authors propose a variant of Wasserstein for distributions supported on different Euclidean spaces (e.g., different dimensions). The main ideas are to combine the embedding (for distributions supported in different spaces -- Alaya et al. 2020) and distributional sliced Wasserstein (Nguyen et al., 2020) to generate random slicing projections into 1d-space, and leverage the 1d-Wasserstein for the comparison. The authors apply the proposed method for generating modeling and in query framework. ", "summary_of_the_review": "It seems that the contribution is quite incremental (e.g., using embedding approach in Alaya et al. 2020 for distributions supported in different spaces to combine with distributional sliced-Wasserstein in Nguyen et al., 2020 to solve the Wasserstein in 1d-projected space).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "M9RR3KmXI8I", "reviewer": "Reviewer_rgFL", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Here are my comments on the paper:\n\n(1) The novelty of the paper is indeed limited. The HWD is a direct application of the idea of [1] Nguyen et al. [2020]. The formulation as well as the theoretical results are also direct from this work. Unless the authors can convince me in the rebuttal that they have something fundamentally new in their paper, the paper does not appear novel to me.\n\n(2) Definition 1 is basically distributional sliced Wasserstein in [1] by projecting $\\mu$ and $\\nu$ into the same unite sphere. Furthermore, it seems to me that Proposition 1 also follows directly from Appendix B in [1]. The authors need to explain the novelty in their results.\n\n(3) I have trouble understanding the implications of results in Proposition 2. The authors may need to explain further the meaning of each result in the rebuttal.\n\n(4) The experiments are also mostly with toy examples, which limit the scope of the method. Do the authors also have the experimental results for real data?\n\n\n\n\nReference:\n\n[1] Nguyen et al. [2020]. Distributional sliced Wasserstein distance and applications to deep generative model. ICLR, 2021.", "summary_of_the_paper": "In the paper, the authors proposed heterogeneous Wasserstein discrepancy (HWD) to compare incomparable distributions. The main idea of HWD is via distributional slicing, which had been employed in the work of Nguyen et al. [2020].", "summary_of_the_review": "In my opinion, the contribution of the paper is limited as it is a direct extension of [1]. Both the formulation of HWD and its theoretical results do not appear to be novel.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6_T4qjs1FUi", "reviewer": "Reviewer_MjvX", "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": "The heterogeneous Wasserstein discrepancy as been proposed as a substitute to the classical Gromov-Wasserstein distance, that suffers from a high computational cost. Therefore, HWD is a computationally interesting tool to compare probability measures supported in spaces of different dimension. In particular, HWD is constructed in such a way that it is sensitive to translations whereas others methods based on slicing (such as Sliced Gromov-Wasserstein) are not.\n\nNevertheless, I find that the present paper could benefit from more explanations, insights and justifications.\nTo begin with, the Gromov-Wasserstein distance behaves fundamentally differently than the proposed HWD in the sense that it compares pairs of supports' points of distribution $\\mu$ with pairs of supports' points of distribution $\\nu$, whereas HWD compares directly the -projected- measures. Therefore, more comparison between GW and HWD, not only in terms of running time, but also theoretically and in terms of distance between shapes for example (which shapes are similar under GW, and which ones under HWD) is important in my opinion. Another point, in [Alaya et al., 2020], the proposed robust Wasserstein distance for measures in different spaces is defined in such a way to look for \"the worst possible OT cost over low-distortion embeddings\". A precise justification of the chosen formulation of the problem in this paper would be appreciated.\n\nAdditionally, it seems that the choice of $d$, the dimension of the latent space, is crucial, as large $d$ \"focus on far-angles directions\" and smaller $d$ \"may lose the control on the distributional part\". In particular, very little is said about how to properly choose $d$, and how restrictive actually are the sets $M_{C_\\phi}$ and $M_{C_\\psi}$; or equivalently, how restrictive is the angle preserving property on $\\phi$ and $\\psi$.\n\nIn addition, when defining the HWD, I am not sure that the compactness of the support of the measures is required, is it? Moreover, do $HWD_r(\\mu,\\nu)=0$ implies that $\\mu=\\nu$? And if not, in which case scenario this could occur, and what are the implications?\n\nComputationally speaking, the convergence of the algorithm towards global optimizers is not guaranteed, and some discussion on that matter could be added.\n\nMinor comments : At the end of page 13, in the first line of the last equation, the projection operator is missing for $\\psi(\\theta)$.", "summary_of_the_paper": "This paper introduces the so-called Heterogeneous Wasserstein Discrepancy (HWD) between two probability measures supported on Euclidean spaces of different dimensions, a case scenario appearing in several applications. The HWD is built on ideas from the sliced Wasserstein distance and measure embedding : the two distributions are projected into a one-dimensional space, in which the classical Wasserstein distance (closed-form in 1D) is computed. Moreover, an algorithm to compute such a divergence is presented, and its usefulness is illustrated on synthetic examples, validated on real-world data and compared to standard others methods.", "summary_of_the_review": "The HWD is a novel discrepancy for distributions on heterogeneous spaces, based on slicing and embeddings, and in this sense, is not very original. That being said, it is faster to compute than the traditional Gromov-Wasserstein and its approximations; and HWD provides convincing results as a discrepancy in generative models. Nevertheless, I think that the present paper lacks of justifications on (i) how this discrepancy behaves, (ii) the formulation of the problem, (iii) the choice of the hyperparameter $d$, (iv) the role played by the sets of constraint $M_{C_\\phi}$ and $M_{C_\\psi}$.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The aim of this paper is to propose a novel "GW"-like discrepancy function between probability measures living in different spaces (here restricted to be Euclidean, with a squared euclidean distance as the base metric). While interesting (notably the idea of learning distinct maps mapping a random direction in a latent space onto two spaces) there are a few issues with presentation, incremental nature of work and importantly a few shortcomings in the empirical evaluation as detailed by reviewers. Hopefully these can be used to improve the draft for a future version.
Decision: Reject