Markovian Sliced Wasserstein Distances: Beyond Independent Projections
Authors: Khai Nguyen
Tongzheng Ren
Nhat Ho
Venue: NeurIPS 2023 poster (2023)
Keywords: Sliced Wasserstein
Generative Models
Optimal Transport
TL;DR: We propose Markovian sliced Wasserstein, a family metrics on the space of probability measures that impose the first-order Markov structure on projecting directions.

Abstract: Sliced Wasserstein (SW) distance suffers from redundant projections due to independent uniform random projecting directions. To partially overcome the issue, max K sliced Wasserstein  (Max-K-SW) distance ($K\geq 1$), seeks the best discriminative orthogonal projecting directions. Despite being able to reduce the number of projections, the metricity of the Max-K-SW cannot be guaranteed in practice due to the non-optimality of the optimization. Moreover,  the orthogonality constraint is also computationally expensive and might not be effective. To address the problem, we introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes a first-order Markov structure on projecting directions. We discuss various members of the MSW by specifying the Markov structure including the prior distribution, the transition distribution, and the burning and thinning technique. Moreover, we investigate the theoretical properties of  MSW including topological properties (metricity, weak convergence, and connection to other distances), statistical properties (sample complexity, and Monte Carlo estimation error), and computational properties (computational complexity and memory complexity). Finally, we compare MSW distances with previous SW variants in various applications such as gradient flows, color transfer, and deep generative modeling to demonstrate the favorable performance of the MSW.

Markovian Sliced Wasserstein Distances: Beyond Independent Projections
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 Austin Austin, TX 78712
khainbdutexas edu
tongzhengdutexas.c edd edu
Nhat Ho
Department of Statistics and Data Sciences The University of Texas at Austin Austin, TX 78712
minhnhat@utexas.cm edu
Abstract
Sliced Wasserstein (SW) distance suffers from redundant projections due to inde- pendent uniform random projecting directions. To partially overcome the issue, max K sliced Wasserstein (Max-K-SW) distance (K 2 1), seeks the best dis- criminative orthogonal projecting directions. Despite being able reduce the number of projections, the metricity of the Max-K-SW cannot be guaranteed in practice due the non-optimality of the optimization. Moreover, the orthogonality constraint is also computationally expensive and might not be effective. To address the problem, we introduce a new family of SW distances, named Markovian sliced Wasserstein (MSW) distance, which imposes first-order Markov structure on projecting directions. discuss various members the MSW by specifying the Markov structure including the prior distribution, the transition distribution, and the burning and thinning technique. Moreover, we investigate the theoretical prop- erties of MSW including topological properties (metricity, weak convergence, and connection to other distances), statistical properties (sample complexity. and Monte Carlo estimation error), and computational properties (computational complexity and memory complexity). Finally, we compare MSW distances with previous SW variants in various applications such gradient flows, color transfer, and deep generative modeling to demonstrate the favorable performance of the MSW
Introduction
Sliced Wasserstein (SW) 7 distance has been well-known as great alternative statistical distance for Wasserstein distance [57 49). In short, SW takes the average of Wasserstein distances between corresponding pairs of one-dimensional projected measures as the distance between the two original measures. Hence, the SW has low computational complexity compared to the conventional Wasserstein distance due to the closed-form solution of optimal transport in one dimension. When the probability measures have most supports, the computational complexity of the SW is only On l).... This complexity much lower than the computational complexity O( log n) of Wasserstein distance and the complexity O(n²)
35 33 of entropic Wasserstein 11 (Sinkhorn
'Code for this paper is published at httts:://githuu.coo//U com/UTT Austin- Aatti--Da------a------aaaa-- Datt--aattt-SSeeeeee... Sicience-Group//Ke
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

divergence). Moreover, the memory complexity of the SW is ((n) which is lower than (n²)) ((n²)(mr of the Wasserstein (Sinkhorn) distance. The reason is that SW does not need store the cost matrix between supports which cost (n²)). An additional appealing property of the SW is that it does
not suffer from the curse of dimensionality, namely, its sample complexity is ((n-1/2) 40 46
compared to On 1/4) 19 of the Wasserstein distance (d is the number of dimensions).
Due to the scalability, the SW has been applied to almost all applications where the Wasserstein distance is used. For example, we refer to some applications of the SW which are generative model-
ing [60 15 27 42 domain adaptation (30], clustering (28). approximate Bayesian computation (3), gradient flows 37 []. and variational inference [61]. Moreover, there are many attempts to improve the SW. The generalized sliced Wasserstein (GSW) distance that uses non-linear projection pro- posed in [26]. Distributional sliced Wasserstein distance is proposed in 44 45] by replacing the uniform distribution on the projecting directions in SW with an estimated distribution that puts high probabilities for discriminative directions. Spherical sliced Wasserstein which is defined between distributions that have their supports on the hyper-sphere is introduced in 4. A sliced Wasserstein variant between probability measures over images with convolution is defined in 43
Despite having lot of improvements, one common property in previous variants of the SW is that they use independent projecting directions that are sampled from a distribution over a space of projecting direction e.g., the unit-hypersphere. Those projecting directions are further utilized project two interested measures to corresponding pairs of one-dimensional measures. Due to the independence, practitioners have reported that many projections do not have the power to discriminative between two input probability measures 26 15). Moreover, having a lot of projections leads to redundancy and losing computation for uninformative pairs of projected measures. This problem is known as the projection complexity limitation of the SW.
To partially address the issue, the max sliced Wasserstein (Max-SW) distance is introduced in [14. Max-SW seeks the best projecting direction that can maximize the projected Wasserstein distance. Since the Max-SW contains constraint optimization problem, the projected subgradient ascent algorithm is performed. Since the algorithm only guarantees to obtain local maximum [46), the performance of empirical estimation Max-SW is not stable in practice 42] since the metricity of Max-SW can be only obtained at the global optimum. Another approach is to force the orthogo- nality between projecting directions. In particular, K-sliced Wasserstein orthogonal projecting directions. Moreover, to generalize the Max-SW and the K-SW, max-K K sliced Wasserstein
50 (K-SW) uses K > 1
distance (K > 1) appears in [2] to find the best K projecting directions that are orthogonal to each other via the projected sub-gradient ascent algorithm. Nevertheless, the orthogonality constraint computationally expensive and might not be good in terms of reflecting discrepancy between general measures. Moreover, Max-K-SW also suffers from the non-optimality problem which leads to losing the metricity property in practice.
To avoid the independency and to satisfy the requirement of creating informative projecting directions efficiently, we propose to impose a sequential structure on projecting directions. Namely, we choose a new projecting direction based on the previously chosen directions. For having more efficiency in computation, we consider firiiddeffrstorreee first-order Markovian structure the paper which means that a projecting direction can be sampled by using only the previous direction. For the first projecting direction, it can follow any types of distributions on the unit-hypersphere that were used in the literature e.g.. uniform distribution 7 and von Mises-Fisher distribution [23 45 to guarantee the metricity. For the transition distribution on the second projecting direction and later, we propose two types of family which are orthogonal-basse based transition and input-awared transition. For the orthogonal- transition, we choose the projecting direction uniformly on the unit hypersphere such that it is orthogonal to the previous direction. In contrast to the previous transition which does not use the information from the two input measures, the anput-awared transition uses the aub-gradient with respect to the previous projecting direction of the corresponding projected Wasserstein distance between the two measures to design the transition. In particular, the projected sub- mub-gradient update is used to create the new projecting direction. Moreover, we further improve the computational time and computational memory by introducing the burning and thinning technique to reduce the number of random projecting directions.
Contribution. summary, our contributions are two-fold:
1. We propose a novel family of distances on the space of probability measures, named Markovian sliced Wasserstein (MSW) distances. MSW considers first-order Markovian
2

---

structure on random projecting directions. Moreover, we derive three variants of MSW that use two different types of conditional transition distributions: orthogonal- based and input-awared. We investigate the theoretical properties of MSW including topological properties (metricity, weak convergence, and connection to other distances), statistical properties (sample complexity, and Monte Carlo estimation error), and computational properties (computational complexity and memory complexity). Moreover, we introduce a burning and thinning approach to further reduce computational and memory complexity, and we discuss the properties of the resulting distances.
2. We conduct experiments to compare MSW with SW, Max-SW, K-SW, and Max-K-SW in various applications, namely, gradient flows, color transfer, and deep generative models on standard image datasets: CIFARIO and CelebA. We show that the input-awared MSW can yield better qualitative and quantitative performance while consuming less computation than previous distances in gradient flows and color transfer, and comparable computation in deep generative modeling. Finally, we investigate the role of sypee-pprameters of distances e.g.. the number of projections, the number time-steps, and so on, in applications.
Organization. We first provide background for Wasserstein distance, sliced Wasserstein distance, and max sliced Wasserstein distance in Section 2] In Section 3] we propose Markovian sliced Wasserstein distances and derive their theoretical properties. Section 4 contains the comparison of MSW to previous SW variants in gradient flows, color transfer, and deep generative modeling. We then conclude the paper in Section Finally, we defer the proof's of key results in the paper and supplementary materials to Appendices.
Notation. For 2 1, (PR()) is the set of all probability measures on Rd that have finite moments. For any d 2 2. we denote U($ is the uniform measure over the unit hyper-sphere Sd-1 = {0 E Rd ||0113 = 1}. For any two sequences a, and b, the notation a,, = O(b,.) means that an Cb, for all 1, where C' is some universal constant. We denote Ofp is the push-forward measures of through the function f Rd + I that is f(x) = Ox..
2 Background
We start with reviewing the background on Wasserstein distance, sliced Wasserstein distances, their computation techniques, and their limitations.
Wasserstein distance. Given two probability measures ja E (R) and E PP(())) the Wasser- stein distance [57 48) between f and v is:
/
(), inf
| yli
(I)
=) RRd
where IT(,, v) is set of all couplings that have marginals are and respectively. The computational complexity and memory complexity of Wasserstein distance are O(n log n) and O(n²) turn when and v have at most supports. When d = the Wasserstein distance can be computed with closed form: WT v) So (+) - (=) where Fç. and F, are the cumulative distribution function (CDF) of μ and respectively.
Sliced Wasserstein distance. By randomly projecting two interested high dishndimensional measures to corresponding pairs of dineeinnnsional measures, sliced Wasserstein (SW) distance can exploit the closed-form benefit of Wasserstein distance in dimension. The definition of sliced Wasserstein distance between two probability measures μ E pp (IR") and v E p (R2) is:
SW v) E (2(O0t, (Ot),
Monte Carlo samples are often used to approximate the intractable expectation unbiasedly:
1 Σ 0:10), L
SW W.(,v) v)
(3)
where .I...., Or, are drawn randomly from U($d-1). When μ and are discrete measures that have most n supports in d dimension, the computational complexity of SW ( In log, n + I.dn) and the memory complexity for storing the projecting directions and the projected supports is (LL(+n))
3

---

Here, log, n is for sorting L sets of projected supports and Ld is for projecting supports to L sets of scalars.
Max sliced Wasserstein distance. To select the best discriminative projecting direction, the max sliced Wasserstein (Max-SW) distance [4] between ja E (T((R)) and E Pp (R() is introduced as follows:
Max-SWp(H,t))
Wp Wp(OHu, 6ES4-1
(4)
Computing Max-SW requires solving the constrained optimization problem. In practice, the projected
sub-graud gradient ascent algorithm with T > 1 iterations is often used to obtain a surrogate projecting
direction Or for the global optimum. Hence, the empirical Max-SW distance is Max-SW p(1,, v) WrrOrtu. 0 The detail of the projected sub-gradient ascent algorithm is given in Algorithm in Appendix A.1 The computational complexity of Max-SW is O n log, n2 + Tdn) and the memory complexity of Max-SW is (d + n)) is worth noting that the projected sub-ge gradieddiennt ascent can only yield local maximum [6]. Therefore, the empirical Max-SW might not be distance even when T oC since the metricity of Max-SW can be only obtained at the global maximum.
K-sliced Wasserstein distance. The authors in (50] propose to estimate the sliced Wasserstein distance based orthogonal projecting directions. We refer to the distance K-sliced Wasserstein distance (K-SW). The definition of K-SW between two probability measures E Pp(RR) and
E (P( is:
[ K Σ
K
K-SW = E
Wp 0.tee)
(5)
where the expectation with respect to (01...., 0k) ~ (R*)) with (x(Rd) = ((11...,, K0.
0 Vi,j S K} the Stiefel manifold. The expectation can be approximated with Monte Carlo samples (0it,..,0xxi)[_ from ((V((R))) In the orig- inal paper, T, is set to 1. To sample from the uniform distribution over the Stiefel manifold (RR)) it requires using the Erra-- orthogonality process which has the computa- tional complexity O(K2d) (quadratic in K). Therefore, the total computational complexity of K-SW O(LK n log, n + LK + LK3d) and the memory complexity of K-SW is O (d++)) +n)). More detail related to K-SW including Gram-Smith process and sampling uniformly from the Stiefel manifold is given in Appendix A.I A.I
Max K sliced Wasserstein distance. To generalize both Max-SW and K-SW, Max K sliced
Wasserstein introduced in 122 Its definition between μ E PP( and E (RR) is:
max (ax-K-SW"(H,D)) (6.....,9x (
Σ K
Wg(0O.t,, O.to)
(6)
Similar to Max-SW, a projected sub- aab-ggrddent ascent algorithm with T > iterations used to approximate MaX-K-SW. We refer the reader to Algorithm 4 in Appendix I for greater detail. Since the projecting operator to the Stiefel manifold is the Gram-Smith process, the computational complexity of Max-K-SW is O(T log, n TKTn dn + dK) The memory complexity of Max- K-SW is O(K(d + n)). Similar to Max-SW, the metricity of Max-K-SW is only obtained at the global optimum, hence, the empirical estimation might not be stable. Moreover, the orthogonality constraint is also computationally expensive i.c., quadratic in terms of the number of orthogonal projections K.
3 Markovian Sliced Wasserstein distances
We first define Markovian sliced Wasserstein (MSW) distance and discuss its theoretical properties including topological properties, statistical properties, and computational properties in Section 3.1 In Section 3.2 we discuss some choices in designing the Markov chain including the prior distribution and the transition distribution. Finally, we discuss the burning and thinning variant of MSW which can reduce the computational and memory complexity in Section 3.3

---

3.1 Definitions, Topological, Statistical, and Computational Properties
We first start with a general definition of Markovian sliced Wasserstein distance in Definition | Definition For any p 2 1, 2 1, and dimension d 2 1, the Markovian sliced Wasserstein of order p between two probability measures μ EPp(R.) and (P)().) ) is:
T
1
MSW P p.T ((0 (
E
W (0,tu, 0:
T
where is the number of time steps, the expectation is under the projecting distribution OuT ~ (01:)) with (00:r) = o 0r) = o1 II ((0,00())))) and o (01), a (0e(0(--1) E P( for allt=1....,
The first projecting direction 0, follows the distribution a (01) with a (01) to be any distribu- tions on the unit hyper-sphere, e.g., the uniform distribution, von Mises-Fisher distribution, and so on. By designing the transition distribution 0f ((((()-))), we can obtain various variants of MSW. is worth noting that the MSW can be rewritten as the average of T expectation of one- dimensional Wasserstein distance, MSW p v) + Ei= (0,) (OeHj, 0ctr)), how- ever, of (0,) = /IT (01) (0 (.r=))df....d........ dd0.- are not the same for 1 1..... T. Moreover, sampling directly from (8e) is intractable, hence, using the definition of the MSW in Definition is more reasonable in terms of approximating the expectation using Monte Carlo samples.
Monte Carlo estimation. Similar SW, we also need use Monte Carlo samples to approximate the expectation in [ We first samples 011...., 0i ~ (8, (i--)) for t ......T and = 1............ ...... L. After that, we can form an unbiased empirical estimation of MSW as follows: MSW p, v) +. Σt E.T Wp(Outu, 0urdv).
......,,,, 0L1 01 (01) for L 2 1, then we samples
Before going to the specific design of those distributions, we first discuss the empirical estimation of MSW, and investigate its theoretical properties including topological properties, statistical properties, and computational properties.
Topological Properties. We first state the following assumption: A1. In MSW, the prior distribution T1 (01) is supported all the unit-hypersphere there exists transition distribution as (,(0)()-11 being supported on all the unit-hypersphere The assumption A1 is easy to satisfy and it holds for all later choices of the prior distribution and transition distribution. We now consider the metricity properties of the Markovian sliced Wasserstein distance.
Theorem 1 (Metricity). For any p 2 1, TOTZ 221 1, and dimension d > 1. if Al holds, Markovian sliced Wasserstein MSW,, (:--) is a valid metric on the space of probability measures Pp (RR), namely, satisfies the (i) non negativiiy,, (ii) symmetry, (iii) triangle inequality, and (iv) identity.
The proof of Theorem T is in Appendix B.I
Next, we show that the convergence in MSW implies the weak convergence of probability measures and the reverse also holds.
Theorem 2 (Weak Convergence). For any p 2 T 2 1, and dimension d 2 1, if holds, the convergence of probubility measures in Pp(RR) under the Markovian sliced Wasserstein distance MSWp.((s.) implies weak convergence of probability measures and vice versa.
Theorem means that for any sequence of probability measures (μR)KEN and in Py (Rd)), M.S.PT(Jus pT (a) = if and only if for any continuous and bounded function f: RRd + R, limg->too J f dua f dj.. The proof of Theorem 2 is in Appendix B.2 Next, we discuss the
limg-x MSW
connection of MSW to previous sliced Wasserstein variants.
Proposition 1. For any 2 1 and dimension d 2 1, (i) For any T 2 and v Pp (IR.), MSW p. (H.V) S Max-SW, S Wo(me)). (ii) ITT = 1 and the prior 01 (01) = (Sd-1), MSW,.T(M, SW,(H.V)
The proof of Proposition D is in Appendix B.3
Statistical Properties We investigate the sample complexity (empirical estimation rate) of the MSW.
5

---

Proposition 2 (Sample Complexity). Let X2......... Xn be i.idd samples from the proba- billity measure μ being supported on compact set of R We denote the empirical measure Nn = - >i= òx, Then, for any p 2 1 and T 2 1, there exists universal constant C'> 0 such that E[MSW (. p)] S CV(d+ 1og n/n, where the outer expectation is taken with respect to the data X1, X2.........
The proof Proposition is is in Appendix B.4 The proposition suggests that MSW does not suffer from the curse of dimensionality, Next, we investigate the MSW's Monte Carlo approximation error.
Proposition 3 (Monte Carlo error). For any 2 1, T 2 1. dimension d 2 1, and u.v E (P))))),
we have: E. MSW (,,, - MSW p.r S variance is with respect to or (01,....,00 0r)
1 Var TVT.
E WP (0/2/4, Octu)]
where the
The proof of Proposition is in Appendix B.5 From the above proposition, we know that increasing the number of projections L reduces the approximation error.
Computational Properties. When μl and are two discrete probability measures in Pp (R)) that have at most n supports, the computational complexity for the Monte Carlo approximation of MSW is On log2 n--7 Ldn) where O log n) is for computation of T one-dimensional Wasserstein distances and ( Ldn) is the projecting complexity for TL projections from d dimension to 1 dimension. The memory complexity of MSW is O(T + n)) for storing the projecting directions and the projections.
3.2 Specific Choices of Projecting Distributions
Designing the projecting distribution o of1...... ,,r) is the central task in using MSW since it controls the projecting behavior. For each choice of the o (f1,...,,8p 0r). we obtain a variant of MSW. Since we impose the first order Markov structure a (fI,...., 0r) = an (0,) IT= ae (0,(0))))) there are two types of distributions that we need to choose: the prior distribution on (61) and the transition distribution o, (6, (0,0) for all t= 2...,
Prior distribution. The most simple choice of 01 (0,) when we know nothing about probability measures that want to compare is the uniform distribution over the unit hypersphere U((d-1), 1). Moreover, the metricity of MSW is guaranteed regardless of the transition distribution with this choice. Therefore, the uniform distribution is the choice that It is worth noting that we could also use a distribution that is estimated from two interested probability measures 44 however, this approach costs more computation.
in our experiments in the paper.
Transition distribution. We discuss some specific choices of the transition distributions o, (0, 00 1). Detailed algorithms for computing MSW with specific transitions are given in Appendix A.3
Orthogonal- based transition. Motivated by the orthogonality constraint in Max-K-SW K-SW and K-SW, we can design a transition distribution that gives us an orthogonal projecting direction to the previous one. In particular, given a previous projecting direction 0,-1, we want to have 6, such that (0., 0 1)
namely, we want to sample from the subsphere Sd-1 == (0: E gd,' 6 0). To the best of our knowledge, there is no explicit form of distribution (known pdf) that is defined on that set. However, we can still sample from the uniform distribution over that set: U(S) since that distribution can be constructed by pushing the uniform distribution over the whole unit hypersphere
(0--1,0:) 0c-1) where u((=11) through the projection operator: Proje,., (0.) Proiga-1 (0- (
Projga-1 (0) = Tol is the normalizing operator. In a greater detail, we first sample 0f (Sd-11) and then set 0, Proje._, (8)). Therefore, we have o, (8, = (( = Proje_,, (Sd-1).
Input-awared fransition. The above two transition distributions do not take into account the informa- tion of the two probability measures and y that we want to compare. Hence, it could be inefficient to explore good projecting directions by comparing y and Motivated by the projected sub-gradient ascent [9] update in finding the "max" projecting direction, we could design the transition distri- 6 600.-111....)) where J denotes the Dirac Delta function and the transition function f(0,-1|n, |y, uu, v) = Projga-1 (0.-1+ + V, Wp (0.-141, 0--1bv)) with v) > 0 the stepsize hyperparameter. As the current choice is deterministic transition, it requires the prior
bution as follows: (0,(00)))))

---

distribution to have supports on all gd-1 to obtain the metricity for MSW. A choice to guarantee the metricity regardless of the prior distribution is the von Mises-Fisher (vMF) distribution (33] namely, 0r (0) v = f(0,-1|9 1t, k)). The details about the vMF distribution including its probability density function, its sampling procedure, and its properties are given in Ap- pendix[A.2 In summary, the vMF distribution has two parameters: the location parameter E $ which is the mean, and the concentration parameter A E R+ which plays the role as the precision. Thank the interpolation properties of the vMF distribution: lim VMF(0)e, k) U(S"11) and limx- VMF(0 x) = 6c. the transition distribution can balance between heading to the "max" projecting direction and exploring the space of directions.
Stationarity of (0r). A natural important question arises: what is the distribution of 0r((r)= f...f (ff)..... 000 d when T + oo? The answer to the above questions depends on the choice of the projection distribution which is discussed in Section 3.2 For the Orthogonal- based transitions and the uniform distribution prior, it is unclear whether the stationary distri- bution exists. For the deterministic Input-awared transition and the uniform prior, we have lim (0r) = Ex=1 Gggg; with Σx=1 Oa = where 6% (a = I.....A) are local maxi- mas of the optimization problem maxgegs W (0 ftv) and some unknown weights ag that depend on and v. This property is due to the fact that the projected sub-gradient ascent can guarantee local maxima convergence [46]. For the Input-awared vMF transition, it is also unclear the stationary distribution exists when the parameter 00.
3.3 Burning and Thinning
In the definition of MSW in Definition I. we take the expectation the joint distribution over all timesteps a (01:r) which leads to the time and memory complexities to be linear with T in the Monte Carlo approximation. Therefore, we can adapt the practical technique from MCMC methods which is burning and thinning to reduce the number of random variables while still having the dependency.
Definition 2. For any 2 1, T > 1, dimension d > 1, the number of burned steps M 2 O, and the number of thinned steps N Z 1, the burned thinned Markovian sliced Wasserstein of order p between two probability measures μ E Pp (RR)) and v E (RR)) is:
(A-N/NN
MSW
(.T. (H, = T- Σ
WB (0'du, 0/
(8) (0 with
where the expectation is under the projection distribution (1-N(T-M) o o0 ((LNTT-M) being the marginal distribution which is obtained by integrating out random projecting directions at the time step t such that t S M or t%N + 0 from ((1,...,,r) = (1(01) IT (00 all =1....... I....,T.
Similar to MSW, the sumned-thinned MSW is also a metric on (IR)) when there exists time step t that is not burned, is not thinned, and 0, is a random variable that has the supports on all gd-1 We discuss more details about the surned-thinned MSW including its topological and statistical properties in Appendix A The Monte Carlo estimation of the
MSW is given in Equation I0 in Appendix A.4 The approximation is the average of the projected Wasserstein distance from 0n with t 2 M and 1% = O. By reducing the number of random projecting directions, the computational complexity of the burned-thimne MSW is improved ((((T M) Ln log2 + (T Ldn) in the orthogonal- based transitions. In the case of the input-awared transition, the computational complexity is still OT log, TLdn) since the transition requires computing the gradient of the projected Wasserstein distance. However, in all cases, the memory complexity is reduced to O(T (d + n))N).
Burned thinned MSW is the generalization of Max-SW. the empirical computation of Max- SW 144 with the projected sub-gradient ascent and uniform random initialization can be viewed as special case of burned thinned MSW with the input-awared transition and with the number of burned samples M- T - 1. The difference is that Max-SW uses only one local maximum to compute the distance while the burned thinned MSW uses L > 1 maximums (might not be unique).
More discussions. We refer the reader to Appendix A.5 for other related discussions e.g.. "K-SW is autoregressive decomposition of projecting distribution "sequential generalization of Max-K-SW", and related literature.
7

---

ManiON Tr000
21:333166 (00)
Wit A 12.35
Ny MC (230)
WADOO LOD Tulyent
The figures show the gradient flows that are from the empirical distribution over the color points the empirical distribution over S-shape points. The corresponding Wasserstein-2 distance between the empirical distribution at the current step and the S-shape distribution and the computational time (in seconds) to reach the step is reported at the top of the figure.
Figure 1:
L-ndoa ELITIE My
Nou det for Lie iiaL Ri-
Figure 2: The figures show the source image, the target image, and the transferred images from different distances. The corresponding Wasserstein-2 distance between the empirical distribution transferred color palates and the empirical distribution computational time (in second) are reported at the top of the figure.
the target color palette and the
4 Experiments
In this section, we refer MSW with orthogonal- -based transition as oMSW, MSW with input-awared transition as iMSW (using the Dirac distribution) and viMSW (using the vMF distribution). We compare MSW variants to SW, Max-SW, K-SW, and Max-K-SW in standard applications e.g., gradient flows, color transfer, and deep generative models. Moreover, we also investigate the role of hyperparameters, e.g., concentration parameter the number of projections L, the number of time steps T, the number of burning steps M, and the number of thinning steps N in applications.
4.1 Gradient Flows and Color Transfer
Gradient flows. We follow the same setting in 117 The gradient flow models distribution (()) flowing with time along the gradient flow of loss functional μut) - D(u(t), 1) that drives it towards target distribution (53) where D is given distance between probability measures. In this setup, we consider 1 Σi= 8y; as a fixed empirical target distribution and the model distribution u(() - - (x) Here, the model distribution is parameterized by time-varying point cloud (t) (x,(t) E (I=")". Starting from an initial condition at time t = O, we integrate the ordinary differential equation (t) = -n V (t) (D ( Σi= 6x.(0) 2)]] for each iteration. In the experiments, we utilize the Euler scheme with 300 timesteps and the step size is 10-3 to move the
-
empirical distribution over colorful 1000 points ((0) the distribution over S-shape 1000 points (v) (see Figure For Max-SW, Max-K-SW, iMSW, and viMSW, we use the learning rate parameter for projecting directions = 0.1. report Wasserstein-2 distances between the empirical distribution su(() and the target empirical distribution v, and the computational time in Table I We also give the visualization of some obtained flows Figure [ We refer the reader Figure 4 in Appendix C.I for the full visualization of all flows and detailed algorithms. We observe that iMSW

---

Table 1: Summary of W distances, computational time in second (s) of diffferent gradient flows.
Distances
Wasserstein-2 (J)
Time (4)
Distances
Wasserstein-2 (4)
Time (1)
SW (1=30)
0.0099 x 10
1.55
Max-K-SW (K=),
0.0146 10-2
3.35
Max-SW (T=30)
0.0098 x 10-2
3.48
iMSW (L=2,T=5) (ours)
0.0064 10-2
1.41
K-SW (L=15.K=2)
0.0098 x 10-2
1.71
viMSW (L=2T=55x=500umm
0.0043 10 2
2.94
Table 2: Summary of FID and IS scores from three different
CIFARIO (32x32), and CelebA (64x64).
CIFARIO (32x32)
CelebA (64x64)
CIFARIO (32x32)
CelebA (64x64)
Method
Method
FID (
IS (f)
FID (L)
FID (1)
(?)
FID (
SW
14,21+1112
8.1940.07
8.93+:0223
oMSW (ours)
14.12:20.54
8.20:10.05
9.68=0.55
Max-K-SW
14. 14.38400.8
8,15++0.2
8.94+0..5
iMSW (ours)
14.12440..8
8,24-00.9
0.23
K-SW
15:24::002
8.15:0.03
9.41:0.16
vIMSW (ours)
13.98:10.59
8.124:0.00
8.91
gives better flows than SW, Max-SW, K-SW, and Max-K-SW. Namely, the empirical distribution u(t) (t = 300) with iMSW is closer to // in terms of Wasserstein distance. More importantly, iMSW consumes less computation than its competitors since it can to more informative projecting directions. Furthermore, viMSW gives better final results than iMSW, however, the trade-off is doubling the time computation due the sampling step of vMF distribution. In this case, K-SW is equivalent to our oMSW with T=K=2 since the dimension d = 2. We refer the reader Appendix C for more discussion.
smaller number of projections due
Studies on hyperparameters. From Table Appendix C.I increasing the number of projections L yields better performance for SW, K-SW, and iMSW. Similarly, increasing the number of timesteps T also helps Max-SW and iMSW better. Moreover, we find that for the same number of total projections e.g.. L 5, T 2 and T 2, L 5. larger timestep T might lead to better result for iMSW. For burning and thinning, we see that they help to reduce the computation while the performance stays comparable
even better if choosing the right value of M and N. Also, iMSW the burning steps M = T - is still better than Max-SW with T time steps. For the concentration parameter K in viMSW, the performance of viMSW is not monotonic in terms of k.
Color transfer. We aim to transfer the color palate (RGB) of source image to the color palette (RGB) target image. Therefore, it is natural to build gradient flow that starts from the empirical distribution over the color palette of the source image to the empirical distribution over the color palette of the target image. Since the value of color palette is in the set value of the supports of the empirical distribution at the final step of the Euler scheme with 2000 steps and 10 -0 step size. Greater detail can be found in Appendix C.2 For Max-SW, MaX-K-SW. iMSW, and viMSW, we use the learning rate parameter for projecting directions 17 = 0.1. We show the transferred images, the corresponding Wasserstein-2 2 distances between the empirical distribution over the transferred color palette and the empirical distribution over the target color palette, and the corresponding computational time in Figure From the figures, iMSW and viMSW give the best transferred images quantitatively and qualitatively. Moreover, oMSW is comparable to SW, Max-SW, K-SW, and are better than Max-K-SW while consuming much less computation. We refer the reader to Figure 5 in Appendix C.2 for the color palette visualization and to Figure another choice of the source and target images. We also conduct studies on hyperparameters Appendix C.2 where we observe some similar phenomenons as in gradient flow.
255 we round the
4.2 Deep Generative Models
We follow the setup of sliced Wasserstein deep generative models in 15 The full settings of the framework including neural network architectures, training framework, and hyperparameters are given Appendix C.3 We compare MSW with previous baselines including SW, Max-SW, K-SW, and S-W on benchmark datasets: CIFARIO (image size 32x32) [29]. and CelebA (36] (image size 64x64). The evaluation metrics are FID score [1] and Inception score (IS) 51 (except on
CelebA since IS score poorly captures the perceptual quality of face images 21). A notable change
in computing Max-SW is that we do not momentum in optimization for max projecting direction like in previous works (26] 42), which leads to a better result.
Summary of generative performance. (100, 1000, 10000)). K-SW (I. E (1, 10, 100), K = 10), Max-K-SW (K = {1, 103, 00:7 T = {1, 10, 100, 1000), E {0.01, 0.1)))aa--KK55 K-SW (K=1) is Max-SW), MSW (all variant, L
We train generative models with SW (L E
9

---

CFA1GO
OTARD
CaleA
5H
Max 6:
01
600W
17397
NEW
Via SM
6SW
KONN
VSW
120
SW
Max-K-SW
iMSW
Figure 3: The FID scores and the IS scores epochs, and generated images from CelebA
{10, 100), T E (10, 100)), iMSW and viMSW (n {0.01, 0.1)). and viMSW and (x E (10, 50)). We report the best FID score and the best IS score for each distance Table 2 In addition, we show how scores change with respect to the training epochs in Figure Overall, observe that viMSW and iMSW give the best generative performance in terms of the final scores and fast convergence on CIFARIO and CelebA. The oMSW gives comparable results baselines. Since training deep generative models for updating neural networks, the computational time for distances almost the same. Furthermore, we show some generated images on CelebA in Figure and all generated images on CIFAR and CelebA in Figure / and Figure 8 Appendix C.3 We visually observe that the qualitative results are consistent with the quantitative results in Table
computation in
Studies on hyperparameters. We conduct experiments to understand the behavior of the burning and thinning technique, and compare the role of L and T in Table 5 in Appendix C3 Overall, burning (thinning) sometimes helps to improve the performance no clear sign of superiority between burning and thinning. We compare number of total projections (same complexities): L 10, T = 100 and L, = 100, T 10. On CIFAR10 10, the first setting better while the reverse case happens CelebA.
training generative models. There settings of the same
5 Conclusion
We have introduced the Markovian sliced Wasserstein (MSW), novel family of sliced Wasserstein (SW) distances, which imposes a first-order Markov structure on projecting directions. We have investigated the theoretical properties of MSW including topological properties, statistical properties, and computational properties. Moreover, we have discussed three types of transition distribution for MSW, namely, orthogonal-basee and input-awared transitions. In addition, we have proposed burning and thinning technique to improve the computational time and memory MSW. Finally, we have compared MSW to previous variants of SW in gradient flows, color transfer, and generative modeling to show that MSW distances are both effective and efficient.
Acknowledgements
NH acknowledges support from the NSF IFML 2019844 and the NSF AI Institute for Foundations of Machine Learning.
10

---

References
[1] J. Altschuler, Niles-Weed, and Rigollet. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In Advances in Neural Information Processing Systems, pages 1964-1974, 2017.
[2] Y. Bai, B. Schmitzer, M. Thorpe, and S. Kolouri. Sliced optimal partial transport. arXiv preprint arXiv:2212.08009, 2022.
[3] V. I. Bogachev and M. A. S. Ruas. Measure theory, volume 1. Springer, 2007.
[4] C. Bonet, P. Berg, N. Courty, F. Septier, L. Drumetz, and M.-T. Pham. Spherical sliced- wasserstein. arXiv preprint arXiv:2206.0m 08780, 2022.
[5] C. Bonet, N. Courty, F. Septier, and L.. Drumetz. Efficient gradient flows in sliced- Wasserstein space. Transactions on Machine Learning Research, 2022.
[6] N. Bonneel and Coeurjolly. Spot: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 38(4):1-13, 2019.
[7] N. Bonneel, J. Rabin, G. Peyré, and H. Pfister. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 1(51):22-45, 45,222552220 2015.
[8] N. Bonnotte. Unidimensional and evolution methods for optimal transportation. Phl) thesis, Paris 11, 2013.
(9] S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-35) 2015.
[10] X. Chen, Y. Yang, and Li. Augmented sliced Wasserstein distances. International Conference on Learning Representations, 2022.
[11] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, pages 2292-2300, 2013.
[12] B. Dai and U. Seljak. Sliced iterative normalizing flows. In International Conference Machine Learning, pages 2352-2364. PMLR, 2021.
[13] T. R. Davidson, L. Falorsi, N. De Cao, T. Kipf, and J. M. Tomczak. Hyperspherical variational auto-encoders. In 34th Conference on Uncertainty in Artificial Intelligence 2018, UAI 2018, pages 856-865. Association For Uncertainty in Artificial Intelligence (AUAI), 2018.
[14] 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 Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pages 16648-10656. 2019.
[15] I. Deshpande, Z. Zhang, and A. G. Schwing, Generative modeling using the sliced Wasserstein distance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1183-3491, 2018.
[16] L. Devroye, L. Györfi, and G. Lugosi A probabilistic theory pattern recognition, volume 31. Springer Science & Business Media, 2013.
[17] Feydy, Séjourné, F.-X. Vialard, S.-i. Amari, A. Trouve, and G. Peyré. Interpolating between optimal transport and MMD using Sinkhom divergences. In The 22nd International Conference on Artificial Intelligence and Statisties, pages 2681-2690, 2019.
[18) R. Flamary, N. Courty, A. Gramfort, M. Z. Alaya, A. Boisbunon, S. Chambon, L. Chapel, A. Corenflos, K. Fatras, N. Fournier, I.. Gautheron, N. T. Gayraud, H. Janati, A. Rakotomamonjy, I. 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.
[19] 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.

---

[20] A. Genevay, G. Peyré, and M. Cuturi. Learning generative models with Sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics, pages 1608-1617. PMLR. 2018.
[21] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter. GANs trained by a two time-scale update rule converge to a local Nash equilibrium. In Advances in Neural Information Processing Systems, pages 6626-6637, 2017.
[22] M. Huang, S. Ma, and L. Lai. A Riemannian block coordinate descent method for computing the projection robust Wasserstein distance. In International Conference on Machine Learning. pages 4456-4455. PMLR, 2021.
[23] P. E. Jupp and K. V. Mardia. Maximum likelihood estimators for the matrix von Mises-Fisher and Bingham distributions. The Annals of Statistics, 7(3):599-606, 1979.
[24] O. Kallenberg and O. Kallenberg. Foundations of modern probability, volume 2. Springer, 1997.
[25] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6900 2014.
[26] Kolouri, K. Nadjahi, U. Simsekli, R. Badeau, and G. Rohde. Generalized sliced Wasserstein
distances. In Advances in Neural Information Processing Systems, pages 261-272, 2019.
[27] S. Kolouri, P. E. Pope, C. E. Martin, and G. K. Rohde. Sliced Wasserstein auto-encoders, In International Conference on Learning Representations, 2018.
[28] S. Kolouri, G. K. Rohde, and H. Hoffmann. Sliced Wasserstein distance for learning Gaussian mixture models. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3427-3436, 2018
[29] A. Krizhevsky, G. Hinton, et Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
[30] C.-Y. Lee, T. Batra, M. H. Baig, and D. Ulbricht. Sliced Wasserstein discrepancy for unsuper- vised domain adaptation. Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages (0285-10295, 2019.
[31] J. Lezama, W. Chen, and Q. Qiu. Run-sort-rerun: Escaping batch size limitations in sliced Wasserstein generative models. In International Conference on Machine Learning, pages PMLR, 2021.
[32] Lin, Fan, N. Ho, M. Cuturi, and M. Jordan. Projection robust Wasserstein distance and Riemannian optimization. Advances in Neural Information Processing Systems, 33:9383-9397, 2020.
[33] T. Lin, N. Ho, X. Chen, M. Cuturi, and M. I. Jordan. Fixed-support Wasserstein barycenters: Computational hardness and fast algorithm. In NeurlPS, pages 5368-5380, 2020.
[34] T. Lin, N. Ho, and M. Jordan. On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. In International Conference on Machine Learning, pages 3982-3991, 2019.
[35] Lin, N. Ho, and M. Jordan. On the efficiency of entropic regularized algorithms for optimal transport. Journal of Muchine Learning Research (JMIR),, 23:1 13:1-42, 2022.
[36] Z. Liu, P. Luo, X. Wang, and X. Tang, Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[37] A. Liutkus, U. Simsekli, S. Majewski, A. Durmus, and F.-. Stöter. Waase---essrsttein flows: Nonparametric generative modeling via optimal transport and diffusions. In International Conference on Machine Learning, pages 4104-4113, PMLR, 2019.
[38] N. Naderializadeh, J. Comer, R. Andrews, H. Hoffmann, and S. Kolouri. Pooling by sliced- Wasserstein embedding, Advances in Neural Information Processing Systems, 34, 2021.
12

---

In International Conference on [39] K. Nadjahi, V. De Bortoli, A. Durmus, R. Badeau, and U. Şimşekli. Approximate Bayesian computation with the Srreed-Wssersttinn distance. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5470-5474, IEFE, 2020.
[40] K. Nadjahi, A. Durmus, L. Chizat, S. Kolouri, Shahrampour, and U. Simsekli. Statistical and topological properties of sliced probability divergences. Advances in Neural Information Processing Systems, 33:20802-20811 2020.
[41] K. Nadjahi, A. Durmus, U. Simsekli, and R. Badeau. Asymptotic guarantees for learning generative models with the sliced-Wi Wasserstein distance. In Advances in Neural Information Processing Systems, pages 250-260, 2019.
[42] K. Nguyen and N. Ho. Amortized projection optimization for sliced Wasserstein generative models. Advances in Neural Information Processing Systems, 2022.
[43] K. Nguyen and N. Ho. Revisiting sliced Wasserstein on images: From vectorization to convolution. Advances in Neural Information Processing Systems, 2022.
2022.
[44] K. Nguyen, N. Ho, T. Pham, and H. Bui. Distributional sliced- Wassersensn and applications to generative modeling. In International Conference on Learning Representations, 2021.
[45] K. Nguyen, S. Nguyen, N. Ho, T. Pham, and H. Bui. Improving relational regularized au- toencoders with spherical sliced fused Learning Representations, 2021.
[46] S. Nietert, R. Sadhu, Z. Goldfeld, and K. Kato. Statistical, robustness, and computational guarantees for sliced wasserstein distances. Advances in Neural Information Processing Systems, 2022.
[47] F.P. Paty and M. Cuturi. Subspace robust Wasserstein distances. In International Conference on Machine Learning, pages 5072-5081, 2019.
[48] G. Peyré and M. Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends Machine Learning, 115-6))355-607, 2019.
[49] G. Peyré and M. Cuturi. Computational optimal transport, 2020.
[50] M. Rowland, J. Hron, Tang, K. Choromanski, T. Sarlos, and A. Weller. Orthogonal estimation of W Wasserstein distances. In The 22nd International Conference Artificial Intelligence and Statistics, pages 186-195. PMLR, 2019.
[51] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen. Improved techniques for training GANs. Advances in Neural Information Processing Systems, 29, 2016.
[52] T. Salimans, H. Zhang, A. Radford, and D. Metaxas. Improving GANs using optimal transport. In International Conference on Learning Representations, 2018
[53] F. Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-33):94, 2015.
[54] M. Sommerfeld and A. Munk. Inference for empirical wasserstein distances on finite spaces. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 80(1):219-238, 2018.
[55] S. Sra. Directional statisties in machine learning: a brief review. 2016.
arXiv preprint
[56] N. M. Temme. Special functions: An introduction to the classical functions of mathematical physics. John Wiley Sons, 2011.
[57] C. Villani. Optimal transport: Old and New. Springer, 2008
[58] C. Villani. Optimal transport: old and new, volume 338. Springer Science Business Media,
2008.
13

---

[59] M. J. Wainwright. High-dimensional statistics: A non-asymptotic viewpoint. Cambridge University Press, 2019.
[60] Wu, Z. Huang, D. Acharya, W. Li, J. Thoma, D. P. Paudel, and L. V. Gool. Sliced Wasserstein generative models. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition, pages 3712-3722, 2019.
[61] M. and S. Liu. Sliced Wasserstein variational inference. In Fourth Symposium on Advances in Approximate Bayesian Inference, 2021.
14

---

Supplement to "Markovian Sliced Wasserstein Distances: Beyond Independent Projections"
In this supplementary material, we present additional materials in Appendix A In particular, we provide additional background on sliced Wasserstein variants in Appendix A background on von Mises-Fisher distribution in Appendix A.2 algorithms for computing Markovian sliced Wasserstein distances in Appendix A.3] additional information about burned thinned MSW in Appendix AA44 and discussion on related works in Appendix A.3] We then provide skipped proofs in the main paper in
Appendix B
Additional experiments are presented in Appendix C
A
Additional Materials
A.1 Background on Sliced Wasserstein Variants
We review computational aspects of sliced Wasserstein variants.
Computation of Max sliced Wasserstein distance. We demonstrate the empirical estimation of Max-SW via projected sub-gradient ascent algorithm in Algorithm | The initialization step for 6 is rarely discussed in previous works. Normally, & is randomly initialized by drawing from the uniform distribution over the unit-hypersphere Many previous works [26] 44 [4] 42) use Adam update instead of the standard gradient ascent update for Max-SW. In this work, we find out that using the standard gradient ascent update is more stable and effective.
Algorithm Max sliced Wasserstein distance
Input. Probability measures μ,, v, learning rate n,. the order p, and the number of iterations T.
Initialize 0g- for t T do 0. 0,-1 + Vo._, 10100-1t4,00-111
0. de
119.112
end for Return. Wp(0r (u, (v
K sliced Wasserstein distance. We first review the Gram-Schmidt process in Algorithm 2 With the Sram-SShmidt process, the sampling from u(Vx x (R2) can be done by sampling o...... Og i.id from (0, Ia) then applying the Gram-Schmidt process on them. Therefore, we present the computation of K sliced Wasserstein distance in Algorithm 3 We would like to recall that the original work of K-SW (50) uses only one set of orthogonal projecting directions. Here, we generalize the original work by using L sets of orthogonal projecting directions.
Algorithm 2 Gram-Schmidt process
Input. K vectors .1.....03 0g
0, [0 for to K do
for i = 1 to k 1 do
0% = 0x 0.,
0x)
0
end for
0s: Tillla
#1
end for Return. .1..... 0K
Max K sliced Wasserstein distance. We now present the empirical estimation of Max-K-SW via projected sub-gradient ascent algorithm Algorithm This algorithm is first discussed in the original paper of Max-K-SW [2]. The optimization of Max-K-SW can be solved by using Riemannian optimization since the Stiefel manifold a Riemannian manifold. However, the best of our knowledge, Riemannian optimization has not been applied to
15

---

Algorithm 3 K sliced Wasserstein distance
Input. Probability measures μ, v. the dimension d, the order p, the number of projections L, the number of orthogonal projections K.
for = to L do
Draw fn,.. 8ik i.idd from (0, Ia)-
011..... 01K Gram-Schmidt (011,- -.., Ouk)
end for Return.
1 LK
E'=
(F(Outpp,Otttt) Outtv)
Algorithm 4 Max-K sliced Wasserstein distance
Input. Probability measures J4, v, learning rate n, the dimension d, the order p. the number of iterations 7 > 1, and the number of orthogonal projections K > 1. Initialize 001 for t = 1 to
dox to be orthogonal. do for k 1 to K do
8. = 8c + Vá, Wp Wp(0l-untn 8 1xtv
end for 0......, 0ik Gram (cam--Shhmid((:11.. 0.k)
end for Return.
K Σ k=1 wg(0rsku, 0Tzte) ;
A.2
Von Mises-Fisher Distribution
We first start with the definition of von Mises-Fisher (vMF) distribution.
Algorithm 5 Sampling from vMF distribution
Input. location concentration K, dimension d, unit vector = (1, (1,0,...0)
Draw ~ 2
-2xt -2k+ ( x- (d-1)+2n+ -12 1)a
4nb (1+b)
(d - 1) log d
d-1
repeat
Draw 10 ~ Beta (1 - 1), 1 (d (id-1)) 1))
w f- h(bb,, k)
(1+b)a)
1-(1-b}
1- (1-111)p b)n
Draw ~ Z1 [0, 1))
until (d 1) log(t) + log(u)
h (w, /1 u T)
+ 61 -
Te
U
2un T
Output. Uh1
Definition 3. The von Mises-Fiss Fisher distribution (vMF) is probability distribution on the unit hypersphere Sd-1 with the density function be:
f(zle, == (a(K) exp(ReTx))
(9)
where E gd-1 the location vector, K 2 the concentration parameter, and Ca(k) == 14/2-1
(2n) 106) is the normalization constant. Here, 1y is the modified Bessel function of the first
kind at order v [6
The vMF distribution is continuous distribution, its mass concentrates around the mean and its
density decrease when goes away from e. When - vMF converges in distribution (Sd-1)))
and when - vMF converges in distribution to the Dirac distribution centered c [55).
16

---

Sampling: We review the sampling process in Algorithm 5 vMF distribution is based on the rejection sampling procedure. It is worth noting that the sampling algorithm is doing reparameterization implicitly. However, we only use the algorithm to obtain random samples without estimating stochastic gradients.
13 45
The sampling process of
A.3 Algorithms for Computing Markovian Sliced Wasserstein Distances
We first start with the general computation of MSW in Algorithm For the orthogonal- transi-
tion in oMSW, we use O2r ~ (( by first sampling 0/ ~ (( then set Ov. - Oir
10, 013 0l
then normalize 8ie- = B1 To For deterministic input-awared transition, iMSW, we set O1c- = 0
7 W, (0 On (h--tt) (tv) then normalize Orr T0
01.
For probabilistic input-awared transition,
viMSW, Bie k Projge-10fe-1 k)) with 8% = Ou-1 + 1/ 0: (p 0
Algorithm Markovian sliced Wasserstein distance
Input. Probability measures v, the dimension d, the order p, the number of projections L, and the number of timesteps T.
for / = to L do
Draw O/0 o (00)
for = 1 to T do
Draw P1. (0.
end for end for Return.
EL Wp(Orep Autvv) $
A.4 Burned Thinned Markovian Sliced Wasserstein Distance
We continue the discussion burned thinned MSW in Section Carlo estimation of burned thinned MSW.
We first start with the Monte
Monte Carlo Estimation: We samples 01....., 011 ~ (61) for L > 1, then we samples 8i (0,(0)))))) for .....,7 T and | 1,..., L.
L. We then obtain samples by by filtering out I < M and I%N f 0 from the set {0re] for 1 = 1, 1,.... L and /. = I....,..
T. T. The Monte Carlo approximation the burned-thinned Markovian sliced Wasserstein distance is:
L (T (T-M//N
MSW P.T. (H = L(T- - M)
N
Σ
Σ
WP (0%,114, 61,
(10)
Theoretical properties. We first state the following assumption: A2. Given T> M 2 0, N 1, the prior distribution σ (0i) and the transition distribution a. (0,10,-1) are chosen such that there exists with 2 M and 1%,N = L = 11. ,TI' # l)-
marginals (0.) = (0,,
The assumption A2 can be easily obtained by using vMF transition, e.g., in probabilistic input-awared transition. From this assumption, we can derive theoretical properties of burned- surned-thinned MSW including topological properties and statistical complexity.
Proposition 4. For any p 2 1, 1, M 2 O, N > L, and dimension d 2 1, if holds, the burned thinned Markovian sliced Wasserstein distance MSW, p.T.N,M is valid metric on the space of probability measures (RR)), namely, it satisfies the (i) non-negativity (ii) symmetry, (iii) triangle inequality, and (iv) identity.
The proof of Proposition 4 follows directly the proof Theorem D in Appendix B.I
and dimension 2 1, A2 holds, the convergence of probability measures in Py (Rd) under the burned thinned Markovian sliced Wasserstein distance MSW p.T.N. implies weak convergence of probability measures and
Proposition 5 (Weak Convergence). For any p 2 1,
vice versa.
17

---

The proof of Proposition Soriiioonnnoooooo follows directly the proof of Theorem 2 in Appendix B.2
Proposition 6. For any p Z 1 and dimension d 1, for any T 2 M ,r, E (TR"), MSW N. (M,,N S MMx-SW, (H,,) v) S (,(,,,). v).
0, 2
and
The proof of Proposition
6 follows directly the proof Proposition I in Appendix
B33
Proposition 7 (Sample Complexity). Let X1......... be ii.d. samples from the probability mea- sure μ being supported on compact set of TRd We denote the empirical measure fon -i=1 5x,- Then, for any p 2 1 and T 2 1, M 2 O. N 2 1, there exists universal constant C > 0 such that
EIMSW P.T.N.M (pm. S C Cv(d+ (dd++)logn// n/
where the outer expectation is taken with respect to the data X1, X2, Xn-
The proof of Proposition follows directly the proof Proposition 2 in Appendix B.4
Proposition 8 (Monte Carlo error). For any p 2 1, T 2 1. M 2 0, N 1. dimension d 2 1, and H., V/ E )R))), we have:
E|MSW
S.MSW...NNM. ((, MSW
P.T.N. (1,
(T M)/N
Var N VLT(T M)
WP (0itu, 02tv) Σ
where the variance is with respect a(0',....
"(' (1--N)/N)
The proof of Proposition 8 follows directly the proof of Proposition 3 in Appendix B.5
A.5 Discussions on Related Works
K-SW is autoregressive decomposition. In MSW, we assume that the joint distribu- tion over projecting directions has the first-order Markov structure: a0l,,..., 0r) a (0:) oz
full autoregressive decomposition Let T = K in K-SW, hence the transition distribution that is used in K-SW is: or (0, 0--1) Gram-Schmidde, Tram-Schmidtto...... (0.) denotes the Gram-Schmidt process update that applies on 0,.
However, we can consider (01,..., 0r) on (01) II (8, 01....
(U(S)-)),, where
Generalization of Max-K-SW Similar to Max-SW, we can derive a Markovian- based K-sliced Wasserstein distance that generalizes the idea of the projected gradient ascent update in Max-K-SV K-SW. However, the distance considers the transition on the Stiefel manifold instead of the unit hypersphere, hence, it will be more computationally expensive. Moreover, orthogonality might not be a good constraint. Therefore, the generalization of Max-K-SW might not have many advantages.
Beyond the projected sub-gradient ascent update. In the input- transition for MSW, utilize the projected sub-gradient update as the transition function to create a new projecting direction. Therefore, could other optimization techniques such momentum, adaptive stepsize, and so on to create the transition function. We will leave the investigation about this direction to future work.
Applications to other sliced Wasserstein variants. The Markovian approach can be applied to other variants of sliced Wasserstein distances c.g., generalized sliced Wasserstein [26] augmented sliced Wasserstein distance (TO), projected robust Wasserstein (PRW) projection), convolution sliced Wasserstein
47
32
22
(k > dimensional
sliced partial optimal transport [6] and so on.
Markovian sliced Wasserstein distances in other applications. We can apply MSW to the setting 31 which an implementation technique that utilizes both RAM and GPUs' memory for training sliced Wasserstein generative models. MSW can also replace sliced Wasserstein distance in pooling in [38] Similarly, MSW can be used applications that exist sliced Wasserstein distance e.g., clustering (28). Bayesian inference [39 61), domain adaptation (60), and on.
18

---

B Proofs
B.1 Proof of Theorem 1
(i), (ii): the MSW is an expectation of the one-dimensional Wasserstein distance hence the non- negativity and symmetry properties of the MSW follow directly by the non-negativity and symmetry of the Wasserstein distance.
(iii) From the definition of MSW in Definition given three probability measures Pts M22 143 Pp (R(R)) we have:
WP (0:tm), 0.8rs)) 1)
t
MSW p,7,
(
T
((0ir))o((brr)
(Wp (Ortm), 0ztr2) + Wn (Ortue, 0edua)))
T
W3 (O:Hu,, Aotpes) 1)
E B((IT)~a((1r))
T
5.
W (Oriuz, (ntwss)
+ ((
T
MSW (11( U2) + MSW, p.r( p3).
where the first inequality due the triangle inequality of Wasserstein distance and the second inequality is due to the Minkowski inequality. We complete the triangle inequality proof.
(iv) We need to show that MSW p. p.r (,, 2/) 0 if and only if μ First, from the definition of MSW. we obtain directly = y/ implies MSW MSWp.r(H4 v) = 0. For the reverse direction, we use the same proof technique in [8) If MSWWW.T.e /) = O, we have fgra-1107 + > Wp (OrHu, 0,tv) (0 0.
If A1 holds. namely, the prior distribution 01 (02) is supported on all the unie-hypersphere or exists transition distribution o. (0.-1) is supported on all the uni--hypersphere, we have W,, (0tH, Btv) = for all B E dd-1 where denotes the prior or the transition distribution that satisfies the assumption A1. From the identity property of the Wasserstein distance, we obtain 0ip = Aiv for --a.e O E $d-1 Therefore, for any E R and f E sd-1, we have:
-- du(a)) [ e = =F)
Flu)(10)
(=txxd0t(()) = 1 e (i dF(e))=())))
= =110tu](t)
where F(z](w) = Sgw e ((w,,))) d7(()) denotes the Fourier transform of 7 E P(Rd"). By the injectiv- ity of the Fourier transform, we obtain which concludes the proof.
B.2 Proof of Theorem 2
Our goal is to show that for any sequence of probability measures (uR)ReN and i in Py ( lim MSW p.. (u) if and only for any continuous and bounded function f: Rdd + R. limp-++00 f f duk = f dp. The proof follows the techniques in 41.. We first state the following
lemma
Lemma 1. For any T 2 1, and dimension d 2 1, if holds and a sequence of probability measures (Dx ken satisfies oim NSSW,T(JKK,) (1) = O with in P(R.), there exists an increasing function
Φ: N.N- - N such that the subsequence (Ho()) kEN converges weakly to
Proof. We are given that limp-++0 MSW1.r(pu 11)
=
0. therefore
limp Jga n ET, W1 (0, 0,tp) (01.)) 0. If A1 holds, namely, the prior
19

---

distribution x1 is supported on all the unit-hypersphere or exists transition distribution (1-1)) is supported on all the unit- untthyyperpphere we have
W1 (Oipue 04p) do (0) = 0,
where a denotes the prior or the transition distribution that satisfies the assumption A1. From Theorem 2.2.5 in 31, there exists an increasing function N - N such that limæ-+oo W1 (f1ppa())) ( 0
for a-a.e g Since the Wasserstein distance implies weak convergence [58] (0tP)(k) KEN
converges weakly to 0ip for o-a.e 9 E gd-1
Let Φ = 52 e
the characteristic function of μ E P(RR), we have the weak conver-
gence implies the convergence of characteristic function (Theorem 4.3 24 limp-+so Pospeces (s) (s))(s), Vs E R, for a-a.e E gd-1 Therefore, limg->oc Pack) (2) (z), for almost most every E R
For any 7 and continuous function RR + with compact support, we denote fa( f 9- (x) (2m7²) - d/2 Sua [(x - 2) exp (-11=11// da where By is the density function of (O0 -Ta)- We have:
[ (=)dd)(())()) [ J/r f(w)gg(2 w (2)
[ Spc f(w) (2TT?) d/2 exp(-1le w21?/(2???) )d (1)(()(2))
(2 - 4/2
ad 1 S(w)
ci cl(=-w,)) (x)dx dw dusck)
Jzd
(2TT²) 4/2
[ f(w) I
-ilmm, c(2..)) 91 dr dw duack) (z)
e
Bdd Jzd
(2 4/2 [ ludd
[ [(w)e- 1ww 91/7 (1t) / clla)) dupces (=)sc))()ddl (=)de dw
(2m7²) - 4/2
JoJ [
Ja f(w)e
-imma) 01/7 (1/) mocas (x))d dw
(2m>²) - 4/2
[ F(fl())9//
HocN) (x)dæ,
where the third equality is due to the fact that Sgu ei(z- m..) 9 (1/> = exp(-lla-w1(/((2})) and F(f(ww) = -gg (xx)e-t(w,a)) dr denotes the Fourier transform of the bounded function f. Similarly, we have
/ Rd
f=()d((==)= = /er f(w)gg(2 w)dd du(z))
[ [ f(w) (2mH?) d/2 exp(-1l= w|l (oll)((??)))do du(z)
(2mm/2)
Jud J S(w)
cllo-w,)) (1) dw du(z))
Rdd
(2 4/2 [ [ S(w)
(ilmmm)) 91/4 (x)d a dw du(=)
Jac Jzd
(2mH²)) d/2
Jee [ f(w)e
Huw K(u)e-Keanhgg,1a 91/1(0) I clla.a) da(2)dr dw
(2mH?) - d/2
( { [(w)e Hmma)) 9 ( (x)dx dw
JRd J
(2Tr2) - d/2
(1)
Since f is assumed to have compact support, Fl exists and is bounded by fee lf(w) t00. Hence, for any k E R and
E gd we have [Fff(())115) (x) pa (z) 5
20

---

91/>(x) Iga If(w)) dw and ( I 91/>(x) fge lf(w))dw. Using the proved
result of lim 2 Ppoces (z) = xz))) and Lebesgue's 's Dominated Convergence Therefore, we obtain
lim { (x(d)))))))(3) k-y00
lim (2
-//2 F1 (2)dx
J
1-000
= -2 -a/2 /
(1) (x))dr
Jec fx(z)du(z))
Moreover, we have:
/ f())d1o(0((z) (x f(z)dp(z)
Jim lim sup 7-+0 k-
2 sup 1f(z) - fx(2)] + 1 f=(2)d(o())(2)) - 1 fr(e)du(a)
< lim lim sup
7-+0 k++00
=ERd
lim 2 sup [f(z) fz(2) 0, 7-+0
zERd
which implies (Ho(t)) KEN converges weakly to μ..
We now continue the proof of Theorem 2 We first show that if lime-soo MSW B.W,,((K,, ())
(ux)een converges weakly μ. We consider sequence (HoO)) such that
limp-soe MSWp.T(HKR,
and we suppose (Jo(K) does not converge weakly to There- fore, let do be the Lévy-Prokhorov metric, lim dp(m).))) * 0 that implies there exists > 0
and a subsequence (Mo(K))en KEN with an increasing function N - N such that for any k E N: dp (Ho00), p)) However, we have
MSW MSW (1, ((
WH (Betn,, (1it))
T
2 (((LT)mo(BIr))
Wp (Oetu1, Octv)
T
2 ((
Σ
Wi (O.tu,, Octv) MSW v),
T
by the Holder inequality with (4, v E (RR)). Therefore, limg-soe MSW (SW1))(
which
implies that there exists s a subsequence (Mo(((())) KEN with an increasing function Φ N + N such that (Mo((())) kEN converges weakly to y by Lemmal 1 Hence, limg->oo dp ((6(о()))) 14) which contradicts our assumption. We conclude that limg-+o MSW p.T (pk, H1) 0, (ux) converges weakly to μ..
Now, show that if (Mu))nN converges weakly μ4, have limg-1oo MSW p,rk 11) 0. By
the continuous mapping theorem, we obtain (#tju) converges weakly to fhn for any O sd-1 Since the weak convergence implies the convergence under the Wasserstein distance [38], we obtain lim W,, (o, μ) Moreover, the Wasserstein distance is also bounded, hence the bounded convergence theorem:
T
lim MSWP (MK, p)) = ((
we (Orsjux 0:t1))
k0000
T
= =E(orr)
Σ = 0.
T
By the continuous mapping theorem with function x > 11/ we obtain limg- MSW ASSW,T(PE,P p)) - O which completes the proof.
21

---

B.3 Proof of Proposition !
(i) We recall the definition of Max-SW.
Max-SW ((,,)
W Wo 0tv)).
0884
Let 0" = orgmax0ega-1 (ennaaxeee-WWW,00... (05u, 0tv), from Definition and p, E (R)) we have:
for any p 2 1. 2 1, dimension d 2 1,
T
MSW ()) = ((0ir)o
w (Ortu,, 0ctur) (0tt
T
T
WP (0 mu4, 0'tw)
W (0" 0" = Max-SWp(1,0))
T
Furthermore, by applying the Cauchy-Schward Schwartz inequality, we have:
{ 10Tx x - o0 ull dr((..)) v)
( = max 8E
inf =EN((LM)
inf (FET((,,N) JR4xd |101|||0 ul dT f
max 058
f
inf =ET((NP)) JRRxR |011-1000 - ylllddT (z,, w) [
inf *EIl(u.)) JR yl
=W (W,
which completes the proof.
(ii) This result can be directly obtained from the definitions of MSW and SW.
B.4 Proof of Proposition] 2
In this proof, we denote + C [Rd as the compact set of the probability measure μ. From Proposition | we find that
E|MSW p.r (Pr μ0] < E [Max SWxxSSWp(mn. p)]
Therefore, the proposition follows long
demonstrate that
(Pn, 14) & Cv(d + 1) logz n/n
where some universal constant and the outer expectation is taken with respect to the data. The proof for this result follows from the proof of Proposition 3 in (43. Here, we provide the proof for the completeness. By defining Fn,0 and Fg as the cumulative distributions of 08pn, and 0zj, the closed-form expression of the Wasserstein distance in one dimension leads to the following equations and incqualities:
[' (E- - Fo du)
Max-SWP (W = max
0E84
/' (F)b(() Fg (u)
max
0ER*:
diam ())
max
(F, Po
PER*: 181
We can check that
max
Fn.((z) - FF(()) = sup
(mx(B) - (BB)).
0ER4: 1
BEB
22

---

where B is the set of half-spaces {a E R 2 S x²) for all A E R such that ||0]| S 1. From VC
inequality (Theorem 12.5in [T6] have
IP sup (m. M(B)| [LB)]>(]) 8S(B, n)e nt /32
BEB
with S(B, n) is the growth function which is upper bounded by (n 1)VC(B) due the Sauer Lemma (Proposition 4.18 in (59]). From Example 4.21 in [59], we get (C(B)= = d+
Let 85( n)n-nteen n /32 s 6, we have 12 2
32 log
(S(..n) 5
Therefore, we obtain
32
85( n)
sup
Un (B) (B[]
log
8,
BEB
71
6
Now we convert the probability statement to inequality with expectation. Using the Jensen inequality and the tail sum expectation for non-negative random variable, we have:
sup BEB
(n,n( - -n[B]
12
x0 P
(((2ng sup (Mn (M(B3)) 21) de BEB
E
sup 1y4n - [n(B]]
BEB
{ 000
(Mn ((B3)) )11)
IP
sup BEB
(B) (BB)))
> dl +
P
sup BEB
21 di
1/" 1dt + { 8S(B, nt/32 m))
2565(B, e e-nu/32
n
Let f(u) u + 2B65(B, n) ns/32 we have f'(u) + 85 m)e- n2,
hence the minima
2* 32 (og((S((E.n)))
Since the inequality holds for any have:
E sup Ir (B) - -n(B] 32 (85 n)) + 32 - CV BBB
(d+ log(n + 1)
by using Sauer Lemma. Putting the above results together leads
E/M, μ)] < Cv log, n/n,
where C > 0 is some universal constant. As consequence, we obtain the conclusion of the proposition.
B.5
Proof of Proposition
For any 2 1.7 2 1, dimension d 2 1, and u.v E (R"),, using the Holder's 's inequality, we have:
E. E|MSW P (1, MSWP (,,
E MSW (. MSW (,,
T
L
T wp (B.tu, 0(te)
2
E2
Wg(Ondu Outv) (o
TL
T
T
wy (Ontu, Outtess
Var
TL
t=1
TVT. ar Σ
WT (O.tH, Octu)
which completes the proof.
23

---

Algorithm 7 Gradient flow with the Euler scheme
Input. the start distribution μ = Ei= dx., the target distribution v == - Ei= dy, number of
Euler iterations T (abuse of notation), Euler step size y7 (abuse of notation), metric D.
for t = to do X X 1/ VVXD((x
end for Output. / 7 Ei=1x,, 8x,
25 11843188 pg
20 TIMREEa (1)
By BTEMEAT (5A81
Ny 2343333 100
N) 12736400 ceg
Ry: C003+00 ILSH
23233334--38 300
My. 0.ME311 Fresed
0.004400 7 11Ata
Ry B10ne430 12
The figures show the gradient flows that are from the empirical distribution over the color points to the empirical distribution over S-shape points produced by different distances. The corresponding Wasserstein-2 distance between the empirical distribution at the current step and the S-shape distribution and the computational time (in second) to reach the step is reported at the top of the figure.
Figure 4:
C Additional Experiments
In this section, we present the detail of experimental frameworks and additional experiments on gradient flows, color transfer, and deep generative modeling which are not in the main paper.
C.1 Gradient Flows
Framework, We have discussed detail the framework gradient flow Section 4.1 in the main paper. Here, we summarize the Euler scheme for solving the gradient flow in Algorithm
Visualization of gradient flows. We show the visualization of gradient flows from all distances (Table D in Figure 4 Overall, we observe that the quality of the flows is consistent with the quantitative Wasserstein-2 score which is computed using [8]. From the figures, we see that iMSW and viMSW help the flows converge very fast. Namely, Wasserstein-2 scores steps 200 of iMSW and viMSW are much lower than other distances. For oMSW, with = 5, T = 2, it achieves a comparable result SW, K-SW, and Max-SW while being faster.
Studies on hyper-parameters. We run gradient flows with different values of report the Wasserstein-2 scores and computational time in Table 3 From the table and Figure 4
and

---

Table 3: Summary of Wasserstein-2 scores, computational time in second (s) of different distances in gradient flow application.
Distances
Wasserstein-22 ())
Time (U)
Distances
Wasserstein-2 (4)
Time (1)
SW (I==10)
0.0113 x 10-2
0.85
SW (1=100)
0.0096 x 10"
4.32
Max-SW (T=5)
0.0231 x 10-2
1.02
Max-SW (T=100)
0.0083 10-2
10.46
K-SW (I=5,.=2))
0.0104 10-4
0.92
K-SW (1=20.)=2)
0.0096 10-2
Max-K-SW (K=2TT=5)
0.0152 x 10
1.41
Max-K-SW (K=2,T=100)
0.0083 x 10
10.46
iMSW (L=1,T=5)
0.0109 x 10-2
1.07
iMSW (L=5,T=5)
0.0055 x 10-2
2.44
iMSW (I:=2,T=10)
0.0052 x 10
2.79
iMSW (1T2)
0.0071 x 10-2
1.14
iMSW (1:2,)=
0.0101 x 10
1.2
iMSW (1=22T55M=2)
0.0055 x 10
1.25
IMSW (L=2,T=5.M-NN=))
0.0066 x 10-2
1.28
iMSW (L-2.T=3.M22-=2)
0.0072 x 10-2
1.19
viMSW (1==2,=5Sx=10))
0.0032 x 10
3.12
viMSW (0=
0.0053 10-2
2.76
1W3--22-4611 40.70 Ny A955
KGG DU BAN- JANEE -004
No- M- 5280 1780-1843
Figure The figures show the source image. the target image, and transferred images from different distances. The corresponding Wasserstein-2 distance between the empirical distribution over transferred color palates and the empirical distribution over the target color palette and the computational time (in second) is reported at the top of the figure. The color palates are given below corresponding images.
see that SW with L 10 is worse than oMSW, iMSW, and viMSW with L 2,7 5 (10 total projections). Increasing the number of projections to 100, SW gets better, however, its Wasserstein-2 score is still higher than the scores of iMSW and viMSW while its computational time is bigger. Similarly, Max-(K)-Si with T 100 is better than Max-(K)-SW with = 5 and T 10, however, it is still worse than iMSW and viMSW in terms of computation and performance. For burning and thinning, we see that the technique can help improve the computation considerably. More importantly, the burning and thinning techniques do not reduce the performance too much. For iMSW, increasing L and 7 leads to a better flow. For the same number total projections e.g.. 10, 2, T 5 is better than L however, its computation worse due to the sampling complexity of the vMF distribution. We vary the concentration parameter suggest that a good balance between heading to the "max" projecting direction and exploring the space of projecting directions is the best strategy.
T 2. For viMSW, it usually performs better than iMSW,
{10, 50, 100} and find that к 50 is the best. Hence, it might
C.2 Color Transfer
Framework. our experiments, we first compress the color palette of the source image and the target image 3000 colors by using K-Mean clustering. After that, the color transfer application is
25

---

E-H0 MINORIT-CE Min -3-232122
6.00 8-13 JA08BL
Figure 6: The figures show the source image, the target images, and transferred images from different distances. The corresponding Wasserstein-2 distance between the empirical distribution over transferred color palates and the empirical distribution over the target color palette and the computational time (in second) is reported at the top of the figure. The color palates are given below the corresponding images.
Algorithm 8 Color Transfer
Input. source color palette X (O...., 255)nx3, target color palette Y E (O...., 2 2 nx3 number of Euler iterations T (abuse of notation), Euler step size 1) (abuse of notation), a metric D. for t 1 to T do
X == - n DV)((p)
end for
X
= round X, fo,...,,55.. 255})
Output. X
conducted by using Algorithm g which is modified version of the gradient flow algorithm since the color palette contains only positive integer in ).5). The flow can be seen incomplete transportation map that maps from the source color palette to color palette that is close to the target color palette. This is quite similar to the iterative distribution transfer algorithm [8), however, the construction the iterative map is different.
Visuallization of transferred images. We show the source image, the target image, and the corresponding transferred images from distances Figure Figure The color palates are given below the corresponding images. The corresponding Wasserstein-2 distance between the empirical distribution over transferred color palates and the empirical distribution over the target color palette and the computational time (in second) is reported at the top of the figure. First, observe that
26

---

Table 4: Summary of Wasserstein-2 scores, computational time in second (s) of different distances in the color transfer application.
Distances
Wasserstein-2 (L)
Time (4)
Distances
Wasscrstein-2 (L)
Time (4)
SW (1:45)
414,51
41.77
SW (I==15)
421.5
12.96
Max-SW (T=15)
449.42
59.13
Max-SW (T=15)
450.37
19.03
K-SW (L=15,K=3)
411.74
38.86
K-SW K=3))
413.16
14.2
Max-K-SW (K=3,T=15)
479.43
53.95
Max-K-SW (K=3,T=5)
510.43
17.46
oMSW (I.=3,T=5)
415.06
13.69
oMSW (I.=3,T=15)
414.29
38.51
iMSW (L=33.=55)
16.97
25.91
iMSW (L=3,T==15
79.47
iMSW (I==S,T=5)
21.63
39.82
iMSW (I=5,T=33)
24.02
22.27
iMSW (=11
26.23
48.08
iMSW (1=3,T=15.M=10)
18.67
55.55
IMSW
(L=3.T=15MM-NN-))
16.6
62.66
iMSW (L=3.T=15.M:11N-2))
19.2
50.1
viMSW (1=33,=5
16.48
29.14
viMSW (1=33T=55x==100)
16.49
29.06
the qualitative comparison (transferred images and color palette) is consistent with the Wasserstein scores. We observe that iMSW and viMSW have their transferred images closer the target image in terms color than other distances. More importantly, iMSW and viMSW are faster than other distances. Max-SW and Max-K-SW do not perform well in this application, namely, they slow and give high Wasserstein distances. For oMSW, is comparable to SW and K-SW while being faster.
Studies on syper-parameters
addition to result in Figure S we run color transfer with other settings of distances in Table 4 From the table, increasing the number of projections L lead to a better result for SW and K-SW. However, they are still worse than iMSW and viMSW with smaller number of projections. Similarly, increasing T helps Max-SW, M-X-K-SW, and iMSW better. As discussed in the main paper, the burning and thinning technique improves the computation and sometimes enhances the performance.
C.3 Deep Generative Models
Here, we state an adaptive formulation of the framework. We are given a data distribution js E P(X' through its random samples (data). Our goal is to estimate parametric distribution V/d, that belongs to family of distributions indexed by parameters é in a parameter space c. Deep generative modeling is interested in constructing V4 via pushforward measure. In particular, My implicitly represented by pushing forward random noise un E P(Z)= e.g., standard multivariable Gaussian, through parametric function G Z + X' (a neural network with weights Φ). To estimate e (uz), the expected distance estimator [54]]]]]]] is used: argmin sea
Framework. We follow the generative modeling framework from 20 42
(X.2) ar
D [D(Px,
where m 2 1, D can be any distance on space of probability measures, S is the product measures, namely, X (.i,..., Tim) @ is equivalent to æ; ~ yu for i 1,.... : m, and Px m Ex &z,- Similarly, Z = (Z1,..., Zm) with 2; Do for i I,..., and Gz(Z) is the output of the neural work given the input mini-batch Z.
By using Wasserstein distance, sliced Wasserstein distance, and their variants as the distance D, we obtain the corresponding estimators. However, applying directly those estimators natural image data cannot give perceptually good results (0 [5]. The reason that Wasserstein distance, sliced Wasserstein distances, and their variants require ground metric input e.g., L2, however, those ground metrics are not meaningful on images. Therefore, previous works propose using a function that maps the original data space X' to feature space J where the La norm is meaningful [5 We denote the feature function F,, X' - F. Now the estimator becomes:
argmin seo (x (xx mm
27

---

SW
Max-K-SW
K-SW
oMSW
iMSW
viMSW
Figure 7: Random generated images of distances on CIFARIO.
The above optimization be solved by stochastic gradient descent algorithm with the following stochastic gradient estimator:
V (x pm (E PR,(G,(2))] E
(x.7) (x.Z)~m
cm g
(E,
K
D (x.) PF.1..,)
K
km
where ..,..., XK are drawn i.i.d from @ and Zi...., Z are drawn i.i.d from 10th There are several ways estimate the feature function Fyy in practice. In our experiments, we use the following objective [15]
min E Ex [min [=E,0,-1++(E(( + EZz.g [min(0, -1 ((FF(GG(()))))
where H : F F R. The above optimization problem is also solved by the stochastic gradient descent algorithm with the following gradient estimator:
[x [xx=pom [min(0.
( @m [min(0, -1 -I((((((((((2))
Ex V min(0, -1 H(F,())) + Zww @m V -1 min(0,-1-H(E,(C,
K
1
V min -1 H| (X)) +
Σ
V min (0, -1 (GFF
K
K
1=1
where X1,..., Xx are drawn i.i.d from @m and Zi..., Zx drawn i.i.d from Smm
Settings. We the following neural networks for G and Fg:
CIFARIO:
Goi 2 E 1288 Vo : ()) - 4 256 Linear) ResBlock up 256 + ResBlock up 256 - ResBlock up 256 + BN, ReLU, + 3x conv, Tanh.
Fry: x [-1, 322x3223 + ResBlock down 128 - ResBlock down 128
ResBlock down 128 - ResBlock 128 + ResBlock 128.
28

---

Table 5: Summary of FID and IS scores of methods on CIFARIO (32x32), and CelebA (64x64)
Method
CIFARIO (32x32)
ColebA (64x64)
FID ())
IS (1)
FID (
IMSW (L= 100. (0, N0
14:61=0.72
8.15=0.15
9.73++0.33
IMSW 10.
14.16-1111
8.1740.07
9.10+-034
IMSW (L= 1 (-
13.93=0211
8.15=0.05
9.49+0.52
IMSW (1 100,T 10
0.33
8.15+0.06
8.99+-064
IMSW 1==10.11100.M-0000
14.26=0.74
8.15=0.07
8.89+0.23
iMSW (1=1000:11000--999N11
14,50=0.70
8.12:0008
9. 9.55++035
IMSW Baw.L=:1011100MMM500.
14.41=0588
8.12:0.06
9.4620.73
iMSW (L==000=:1100.0000222
14.65-0.01
8.11=00.6
9 9.49+0.39
Fagi x E 12288888
ReLU
Global sum pooling(12S))
(Speectrl normalization).
- (x) = (F (2), Fra (Fy, (x))) (x))) and ((F((x)) = F (F (x))
CelebA.
- Go: 2 E (128(~ v0
MO 1)) + 4 x 4 x 256 Linear) ResBlock up 256
ResBlock up 256
-
ResBlock up 256
ResBlock up 256 + BN, ReI.U, + x 3 conv, 3 Tanh
Fyi: æ E [-1,1]52x52X3 - ResBlock down 128 + ResBlock down 128- + ResBlock 128 + ResBlock 128.
ResBlock down 128
-Fay x E 1288888 (Sppectral normalization). (x) (F,, (I)), (F)))))) and (x) (Frr
ReLU
Global sum pooling(12))
For all datasets, the number of training iterations is set to 50000. We update the generator G each iterations while we update the feature function F., every iteration. The mini-batch size m is set 128 in all datasets. The learning rate for G and F, is 0.0002 and the optimizer is Adam [25] with parameters 32) (0, 0.9). We use the order p for all sliced Wasserstein variants. We use 50000 random samples from estimated generative models G for computing the FID) scores and the Inception scores. In evaluating FID scores, we use all training samples for computing statisties of dataset:
Generated images. We show generated images on CIFARIO and CelebA from different generative models trained by different distances in Figure 7 and in Figure g in turn. Overall, images are visually consistent with the quantitative FID scores in Table 2
Studies on hy pyrrparraeeers.. We run some additional settings of iMSW to investigate the perfor- mance of the burning thinning technique and compare the role of L and T in Table 5 First, see that burning and thinning helps to improve FID score and IS score on CIFAR 10 and CelebA in the settings of L. 100, T 10. It is worth noting that the original purpose of burning and thinning is to reduce computational complexity and memory complexity. The side benefit of improving performance requires more investigation that is left for future work. In addition, same number of total projections 1000 without burning and thinning, the setting of L. = 10, T = 100 better than the setting of L 100, T = 10 CIFARIO. However, the reverse direction happens on CelebA. Therefore, on different datasets, it might require hyperparameter tunning for finding the best setting of the number of projections and the number of timesteps T.
find that for the
We evaluate the scores based the code from
29

---

SW
Max-K-SW
K-SW
oMSW
iMSW
viMSW
Figure 8: Random generated images of distances CelebA.
30


Reviews:
[{"review_id": "wSTDBoCYcw", "reviewer": "Reviewer_AyBm", "summary": "The authors propose a variant of the sliced Wasserstein distance that samples the projection directions from a Markov chain instead of uniformly from the hypersphere. They propose two Markov chain designs: the first chooses the next projection vector to be orthogonal to the previous one and the second is deterministic and basically performs projected gradient ascent on the projected Wasserstein distance.", "questions": "1. How do you choose the parameters of the vMF distribution? Why would there be any preference regarding the first projection direction?\n1. Why would the stationary distribution of the $\\sigma_T(\\theta_T)$ for uniform initialization and orthogonal chain not be the uniform distribution?\n1. If orthogonality of directions is a desirable property, shouldn't oMSW always be worse than K-SW for $T = K$?", "limitations": "The authors did not discuss any limitations of their method.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors analyze their proposed method theoretically in various ways\n- Multiple experiments compare the proposed method against baselines", "weaknesses": "1. In high dimensions, two random vectors will be almost orthogonal to each other with high probability. Therefore, oMSW should be basically equivalent to SW which is confirmed by Table 2 and Table 4 in the appendix (compare SW(L=45) to oMSW(L=3,T=15), so that they use the same number of samples; both methods take roughly the same time and lead to almost the same Wasserstein-2 distance)\n1. Table 2: The majority of results overlap so much (i.e. many are within one standard deviation of each other) that no conclusions can be drawn. In particular, putting any of the numbers in bold is misleading.\n1. oMSW is only evaluated in Table 2 (which does not really show anything, see previous point)\n1. Burned-thinned MSW is introduced as a performance enhancement but (1) its impact only evaluated in the appendix (2) its impact on performance is difficult to understand from Table 3 and it looks like there is no real benefit to it\n1. Paragraph \"Stationarity of $\\sigma_T(\\theta_T)\" is has neither positive nor negative results and is vague overall", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for the time and constructive feedback.\n\n**Q1**: In high dimensions, two random vectors will be almost orthogonal with high probability. Therefore, oMSW should be basically equivalent to SW.\n\n**A1**: Regarding the concentration result, two uniformly drawn vectors from the unit-hypersphere are likely to be orthogonal in high dimensions. However, when $2 << K \\approx d$, uniformly drawn vectors are not likely to be orthogonal with high probability. Moreover, there are also applications on low dimensions e.g., 3D point-clouds. In Table 4, oMSW (L=3, T=5) has a W2 score of 415.06, while SW (L=15) has a score of 421.5. Therefore, they are not the same for a limited number of projections. Since the key motivation of MSW is to reduce the number of projections in practice, we believe orthogonal sampling could still offer some benefits. We acknowledge that the performance of the orthogonal transition is not as appealing as the input-aware transition (iMSW). However, we believe that discussing the orthogonal transition is interesting and helpful to future works.\n\n\n**Q2**: Table 2: The majority of results overlap so much.\n\n**A2**: We believe this is an application-specific problem. In generative modeling, achieving a significant reduction in the FID score when reaching a high-quality generative model is challenging. As a reference, the original SNGAN had a FID score of about 21, which is not as favorable as the results presented in our paper. We offer generative modeling mainly as evidence of the widely applicable capabilities of the proposed distances. Additionally, in the paper, we highlight that iMSW demonstrates superior performance in gradient flow and color transfer applications. \n\n**Q3**: oMSW is only evaluated in Table 2\n\n**A3**:   In the gradient flow application, $d=2$, hence oMSW is equivalent to K-SW.This equivalence is mentioned in line 338 of the submission. As previously discussed in **Q1*, we believe that oMSW offers advantages in practical scenarios involving a restricted number of projections. Furthermore, it's important to note that oMSW is just one variant of MSW. In the paper, we also introduce iMSW, which achieves significantly better results compared to oMSW. \n\n**Q4**: On Burned-thinned MSW \n\n**A4**: In summary, from Table 1, iMSW (L=2, T=5) demonstrates a W2 value of 0.0064 and a runtime of 1.41 seconds. Moving to Table 3, iMSW (L=2, T=5, M=4) achieves a W2 of 0.0101 and takes 1.2 seconds; iMSW (L=2, T=5, M=0, N=2) shows a W2 of 0.0066 and a runtime of 1.28 seconds; iMSW (L=2, T=5, M=2, N=2) yields a W2 of 0.0072 and completes in 1.19 seconds. These results collectively indicate that employing burning and thinning aids in reducing computational time, a phenomenon also observed in Table 4. Furthermore, under specific configurations of burning and thinning, improved results are evident, such as iMSW (L=2, T=5, M=2) with a W2 of 0.0055 and a runtime of 1.25 seconds in gradient flow and deep generative modeling (as demonstrated in Table 5). However, burning and thinning are primarily recommended as computational reduction techniques.\n\n\n**Q5**: On paragraph \"Stationarity of $\\sigma_T(\\theta_T)$\"\n\n\n**A5**: Our main goal is to discuss the distinctions between iMSW and Max-SW, while also exploring the relationship between the two. Through this discussion, we could shed light on why iMSW outperforms Max-SW, partially attributed to the stationarity of iMSW—characterized as a mixture of local minima from the optimization problems within Max-SW.\n\n\n**Q6**: How do you choose the parameters of the vMF distribution? \n\n\n**A6**: For gradient flow and color transfer applications, we choose values of $\\kappa$ from the set $\\{10, 50, 100\\}$. In the context of generative modeling, our selection for $\\kappa$ comes from ${10, 50}$. Conceptually, the concentration parameter $\\kappa$ in viMSW can be interpreted as an exploration parameter. Specifically, when $\\kappa$ is small, the transition distribution explores the vicinity of the location parameter more extensively. As $\\kappa$ approaches 0, the transition distribution tends towards a uniform distribution over the unit-hypersphere. On the other hand, higher values of $\\kappa$ result in a more adhesive behavior of the transition distribution around the location parameter. When $\\kappa$ tends towards infinity, the transition distribution becomes deterministic, leading viMSW to converge back to iMSW.\n\n\n**Q7**: Why would there be any preference regarding the first projection direction?\n\nA7:  From a theoretical standpoint, employing a continuous prior distribution ensures the metricity of the distance, applicable to both deterministic and probabilistic transitions. Looking from an empirical perspective, a well-chosen prior distribution can effectively determine the length of the chain, denoted as $T$, allowing for shorter chain lengths due to the availability of a favorable distribution governing projecting directions. \n\n\n**Q8**: Why would the stationary distribution of the $\\sigma_T(\\theta_T)$ for uniform initialization and orthogonal chain not be the uniform distribution?\n\n**A8**: Thank you for your insightful question. Addressing this fundamental question isn't straightforward, and at present, we lack a definitive answer. However, as elaborated upon in **Q7**, it's feasible to employ alternative non-uniform distributions as the prior distribution. The choice of a uniform prior in the paper primarily stems from its simplicity and continuity.\n\n\n**Q9**: If orthogonality of directions is a desirable property, shouldn't oMSW always be worse than K-SW for $T=K$\n\n**A9**: If prioritizing the orthogonality of directions is a key objective, K-SW would outperform oMSW when considering the same number of projections. However, it's important to note that oMSW offers a computational advantage over K-SW, as enforcing pairwise orthogonality in K-SW comes with a quadratic increase in computational complexity."}, {"review_id": "jUupEZpEMS", "reviewer": "Reviewer_yZut", "summary": "This paper presents a novel variant of the sliced Wasserstein (SW) distance, addressing the challenges of redundancy and loss of metricity in other SW distance variants, such as Max-K-SW. The proposed method introduces the use of Markov chain-based projection directions selection to overcome these issues.\n\nThe theoretical contributions of the paper include proving that the new variant of SW distance is a metric, establishing its ability to induce weak convergence. Additionally, sample complexity bounds are derived, demonstrating that the proposed distance, called MSW, does not suffer from the curse of dimensionality. The authors also analyze the Monte Carlo approximation error for computing the distance.\n\nEmpirical evaluations are conducted to validate the performance of MSW compared to other SW distance variants. The results demonstrate the superiority of MSW in various tasks, showcasing its effectiveness and advantages in practical applications.", "questions": "- It would be valuable if the authors could provide further explanation regarding why the newly introduced method outperforms other variants of the sliced Wasserstein (SW) distance empirically. Considering Proposition 1, which suggests that Max-SW is a better proxy for the Wasserstein distance, is it due to the errors introduced in computing the optimal projection direction? Additional insights into the specific factors that contribute to the superior performance would enhance the understanding of the proposed method's advantages.\n\ntypos\n- line 593: \"We samples\" should be \"We sample\"\n- line 703: in the limit I assume that you mean $\\mu_{\\phi(k)}$ instead of $\\mu_k$.\n- line 704: in the limit, $(\\mu_k,\\mu)$ shouldn't be in subscript. In general the subsequence notation is weird in this proof. For example, $\\phi$ appears twice in the proof with different meanings. Please fix this.\n- line 727: do you mean $\\Theta$ is the compact support of $\\mu$?\n- line 735: it's better to write something like $\\mathcal{B}_\\theta$ to make the set depending on $\\theta$ explicitly.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper presents a novel and intriguing idea of utilizing a Markov chain to select projection directions. This approach offers a fresh perspective on addressing the challenges of redundancy and loss of metricity in other variants of the sliced Wasserstein (SW) distance. The novelty and innovation of this idea contribute to the strength of the paper.\n- The authors showcase a commendable strength in their thorough theoretical analysis, covering multiple aspects such as topology and statistics. This comprehensive analysis ensures that the proposed method is well-founded and supported by solid theoretical underpinnings.\n- The experimental findings presented in the paper are convincing and demonstrate the superior performance of the newly introduced method compared to other variants of the SW distance. However, I have some questions regarding these experiments and see below.", "weaknesses": "One potential weakness of the paper lies in the claim that Max-K-SW suffers from a loss of metricity when not obtaining the optimal projections. While this issue is acknowledged, it would be beneficial for the authors to emphasize how their proposed method, even with the use of Monte Carlo approximation, mitigates or eliminates this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We begin by expressing our gratitude for the insightful feedback and comments provided in the review. In response, we offer the following explanations and answers to your inquiries. We welcome any further questions and are open to engaging in a more in-depth discussion on the matter.\n\n**Q9**: One potential weakness of the paper lies in the claim that Max-K-SW suffers from a loss of metricity when not obtaining the optimal projections. While this issue is acknowledged, it would be beneficial for the authors to emphasize how their proposed method, even with the use of Monte Carlo approximation, mitigates or eliminates this problem.\n\n\n**A9**: Thank you for your comment. The difference becomes apparent when considering the asymptotic setting. In particular, for Max-K-SW, it cannot guarantee metricity even as $T$ approaches $\\infty$ due to the non-convex optimization problem. In contrast, as $L$ approaches $\\infty$, MSW can guarantee metricity due to the law of large numbers. Moreover, Max-K-SW is deterministic in nature; hence, there is no derived approximation guarantee. However, we can determine the approximation error of MSW thanks to the MC approximation. Additionally, the unbiasedness of the MC approximation could lead to a better optimization loss, a phenomenon widely observed in SGD. \n\n\n**Q10**: It would be valuable if the authors could provide further explanation regarding why the newly introduced method outperforms other variants of the sliced Wasserstein (SW) distance empirically. Considering Proposition 1, which suggests that Max-SW is a better proxy for the Wasserstein distance, is it due to the errors introduced in computing the optimal projection direction? Additional insights into the specific factors that contribute to the superior performance would enhance the understanding of the proposed method's advantages.\n\n\n**A10**: Proposition 1 implies that MSW can retain the favorable properties of SW and Max-SW, such as low sample complexity. In the paper, we do not contest the optimality of Max-SW in the population form. However, the practical limitations of the current optimization scheme prevent Max-SW from achieving its optimum. Furthermore, utilizing Max-SW as a minimization loss gives rise to a challenging min-max problem, well-known for its difficulty. Motivated by these challenges, we introduce MSW as a computationally effective and efficient variant that establishes a flexible framework for selecting projecting directions. The MSW population offers expressiveness in terms of prior distribution selection, transition distribution, and the lengths of the Markov chain ($T$). Therefore, we could balance between exploration in the space of projecting directions and searching for good projecting directions as we do with iMSW. \n\nOn the theoretical side, there exist numerous theoretical challenges in comprehending MSW due to its expressiveness, hence, we believe it is worth careful independent future exploration. In this paper, we concentrate on the fundamental properties of MSW, demonstrating its practicality and its applicability in various applications. Therefore, we suggest viewing MSW as a practical variant of SW at the moment. \n\n\n**Q11**:  do you mean $\\Theta$ is the compact support of $\\mu$?\n\n\n**A11**: Yes, we will revise the proof to indicate it explicitly.\n\n**Q12**: On typos and presentation suggestions.\n\n\n**A12**: Thank you for pointing this out. We will fix all the typos and adjust our presentation based on your suggestion in the revision.\n"}, {"review_id": "Mz52R5qyyv", "reviewer": "Reviewer_72x2", "summary": "This paper introduces Markovian Sliced-Wasserstein distances, which imposes a Markovian structure on the projecting directions. The author impose different distributions on the transition kernel.", "questions": "- The experiments in generative modeling are not very convincing, would you have the time to do some other experiments? I think it would benefit the paper by giving more impact to the paper.\n- One of the best method for smart SW projections is Distributional SW. Why did the authors did not compare their method with it? \n- I am waiting to see other reviewers questions, to see if it raises other questions on my side.\n\nI am willing to discuss and modify my score in accordance if the authors address my points.", "limitations": "No need to discuss societal impact here.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written and easy to follow. The idea is well-presented.\n- Each important theoretical quantity is studied (metricity, sample complexity, MC approximation error, computational complexity).\n- Different choices of transition kernels are proposed and studied.", "weaknesses": "- I think experiments are not that convincing for people to adopt this method. For instance, Figure 3 graphs and Table 2 results are not enough to show that this method is better than the other ones (see standard deviations for instance).\n- I think this is the type of paper that iterates in the study of SW projections, with a standard theoretical study, good experiments, well-written, but that may not be groundbreaking.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We'd like to express our gratitude for the constructive feedback. We're here to provide responses as outlined below. We are eager to participate in further discussions.\n\n**Q13**: The experiments in generative modeling are not very convincing, would you have the time to do some other experiments? I think it would benefit the paper by giving more impact to the paper.\n\n**A13**: As discussed in the global rebuttal, we believe that iMSW has clearly demonstrated its benefits in gradient flow and color transfer. The primary reason for including deep generative modeling in the paper is to showcase the versatility of the proposed distances. As mentioned in the global rebuttal, we believe we have achieved the highest performance of the SNGAN architecture. Therefore, it is challenging to significantly improve the FID score by a wide margin. We have presented three applications, and iMSW outperforms the other baseline considerably in two of them. Additionally, we have included a comparison between iMSW and DSW on point-cloud interpolation in the rebuttal PDF, which can be viewed as a more practical scenario for gradient flow. In this application, iMSW has demonstrated superior performance compared to DSW. Overall, we believe our paper presents relatively intensive experiments compared to the current literature on proposing new SW variants [1] [2]. \n\n[1] Generalized sliced Wasserstein distances, Kolouri et al\n\n[2] Spherical Sliced Wasserstein, Bonet et al\n\n**Q14**: I think this is the type of paper that iterates in the study of SW projections, with a standard theoretical study, good experiments, well-written, but that may not be groundbreaking.\n\n**A14**: Sliced Wasserstein (SW) distance has various applications in practice e.g., deep generative modeling, point-cloud processing [3], texture synthesis [4], clustering [5], and so on. Therefore, any improvements to SW could make a good impact on downstream applications. Moreover, in the paper, we discuss a new aspect of SW  i.e., dependent projections which has been never investigated in the literature. Overall, we believe our paper could be one key step to push forward the applications of SW variants in general.\n\n[3]  Lidar Upsampling With Sliced Wasserstein Distance, Savkin et al,\n\n[4]  A Sliced Wasserstein Loss for Neural Texture Synthesis, Heitz et al,\n\n[5] Sliced Wasserstein Distance for Learning Gaussian Mixture Models, Kolouri et al,\n\n**Q15**: One of the best method for smart SW projections is Distributional SW. Why did the authors did not compare their method with it?\n\n\n**A15**: In the paper, our focus is on the independent structure between projections, rather than the law governing projecting directions. DSW can indeed provide a reliable law of projecting directions; however, it's important to note that projecting directions are still independently and identically distributed (i.i.d.) samples from that law. In response to your suggestion, we have conducted additional experiments to compare iMSW with DSW in gradient flow, point-cloud interpolation, and deep generative modeling on CIFAR. For a comprehensive understanding of the experimental setup and results, we kindly refer the reviewer to the global rebuttal.\nAs outlined in the paper, specifically in lines 240-241, MSW can utilize the law discovered by DSW as a prior for the Markov chain. This advantageous prior enables a practical reduction of the Markov chain length, constituting a noteworthy extension. We firmly believe that a more profound exploration of the prior distribution and its corresponding transition distribution merits an independent study. Consequently, we have deferred this investigation to future research endeavors.\n"}, {"review_id": "JzA29MEDJs", "reviewer": "Reviewer_YkFo", "summary": "The authors focus on the study of sliced Wasserstein distances. \nIt consists in projecting measures onto Euclidean lines, such that OT between these projected measures has low complexity because it amounts to sort samples. \nThe projections are unit vectors of the d-dimensional sphere of R^d, and in practice one samples a set of projections uniformly samples over the unit sphere. \nHowever, this might be sub-efficient since some projections might be redundant by sampling close directions, or uniformative by projecting in directions where measures are similar. \n\nTo solve this issue, the authors propose to sample projections non-uniformly. In particular they consider sampling processus satisfying a first-order Markov property.\nThey propose a sliced OT variant called 'Markovian Sliced Wasserstein'.\nThey prove metric, weak* convergence and statistical properties.\nThey propose two families of Markov processes, focusing on orthogonality or data-driven.\nThey propose a 'burning and thinning' variant to reduce the number of projections and improve complexity.\nThey run experiments of gradient flows, color transfer and generative learning to illustrate the properties of their losses.\n", "questions": "See my questions which are detailed above.", "limitations": "They adressed the societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I believe that the directions tackled by the authors is interesting, in that they propose ways to change the sampling process of projections, with the hope that it improves the properties of the discretized sliced divergences in practice.\n- The contributions are thorough, with both methodological, theoretical and numerical content on their proposed sliced OT variant.", "weaknesses": "Major issues:\n\n- To my mind, the use of a Markov chain does not seem to bring a significant improvement. \nConcerning Table 1, after running the gradient flow, all W2 distances are of order of $10^{-5}$, whatever the choosen loss. \nThe running times are also equivalent up to a factor $2$. \nIn table 2, the FID and IS scores are not significantly different when we take into account the variance of scores (which is nice to have included it).\nMy take-home message of these experiments is the negative result (as an open question to prove rigorously) that there exists no sampling process which yields a significantly better error rate of the Monte-Carlo approximation.\nHowever, I acknowledge that exploring this question of sampling is an interesting, and that even absence of significant improvement is a beneficial insight to the ML community.\n\n- Section (3.3) on 'burning and thinning' processes is not sufficiently motivated. \nFirst, is it a standard approach in MCMC sampling ? \nIf so, could the authors provide references in the main body about this ? \nSecond, what are the main advantages of doing this ? \nThere should be a key property highlighting the benefits in the main body, otherwise it looks like a variant with no main benefit. \nExcept the reduced computational complexity, nothing else is discussed. \nIf the sampling error rates scale the same as before, I am not motivated by using a more elaborate variant, and would personnally prefer to use a simple yet straightforward algorithm.\nNumerical experiment also do not support a significant advantage of using these techniques.\n\n- I have an issue with the proof of Proposition 2.\nIn the proof there is a term $\\log (8 / \\delta)$ which somehow disappears when the 'universal constant' C is defined.\nHowever, this term seem not to converge to zero when the number of samples goes to infinity.\nCould the authors provide more details on this proof ?\nWith all due respect to the authors, I am not completely sure of the rigor of the proof yielding this statistical rate.\n\nMinor remarks:\n\n- Line 51: Do we only use one projection to optimize Max-SW via gradient ascent ? It seems to be a terrible idea, probe to fall into local maxima. Also why not solving sliced Wasserstein for a set of random projections and then keep the projection yielding the largest score ?\n\n- Line 62: Do we really need in practice to have a loss which is a distance ? In practice training a model by minimizing a loss which is only definite (e.g. Kullback-Leibler) seems to be suffice.\n\n- Line 222: From what I understand, L is the number of Monte-Carlo chains, and T is the number of projections for a given MC chain. Thus the number of total projections is $T \\times L$.\n\n- Line 251: Maybe a notation 'Proj' and not 'Prod' would be more relevant to denote a projection operation.\n\n- Line 263: How do you tune $\\kappa$ in the Input-Aware sampling ? Do we need to scale it w.r.t. loss, data, or something else ? Some insights would be welcome here.\n\n- In general figures have legends which are too small to read without zooming significantly. Could the authors increase their size ?\n\n- Line 343: You could comment that this remark on having a larger T is better by connecting it to Proposition 3, since the error scales proportionnaly to $1 / T \\sqrt{L}$. Theory indeed show it is more efficient to take T large rather than L.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to show our appreciation for your valuable feedback and comments. \n\n**Q16**: To my mind, the use of a Markov chain does not seem to bring a significant improvement... all W2 distances are of order of  $10^{-5}$.\n\n**A16**: This is due to the small scale of the initial supports. The scale of distances can be easily controlled by scaling up the supports by a fixed constant, and the scale of computation time can be easily controlled by adjusting the number of supports.\n\n**Q17**: In table 2, the FID and IS scores are not significantly different when we take into account the variance of scores (which is nice to have included it). \n\n**A17**: As discussed in the global rebuttal, we believe that this is an application-specific problem. In generative modeling, reducing the FID score by a large margin becomes challenging when aiming for a high-quality generative model. For reference, the original SNGAN FID score is approximately 21, which is significantly lower than the values presented in our paper. Overall, we firmly believe that iMSW demonstrates distinct advantages in terms of gradient flow and color transfer.\n\n**Q18**: On burning thinning techniques.\n\n**A18**: The introduction of burning and thinning can be found in Chapter 10 of [1]. We kindly direct the reviewer to the global rebuttal for a comprehensive discussion regarding the benefits of burning and thinning. In brief, we propose the utilization of burning and thinning as a computational acceleration method.\n\n[1] Monte Carlo theory, methods and examples, Orwen et al. \n\n**Q19**: On the proof of sample complexity.\n\n**A19**:  We apologize for the oversight in omitting the proof. We kindly refer the reviewer to a more detailed proof provided in the rebuttal PDF file. In the course of the proof, it becomes evident that the variable $\\delta$ disappears as we transition from a probability-based statement to an inequality of expectations\n\n\n**Q20 **: Line 51: Do we only use one projection to optimize Max-SW via gradient ascent ? It seems to be a terrible idea, probe to fall into local maxima. Also why not solving sliced Wasserstein for a set of random projections and then keep the projection yielding the largest score ?\n\n\n**A20**: The projected gradient ascent presently stands as the most widely employed algorithm for solving Max-SW, as highlighted in references [2], [3], and [4]. Your suggestion is indeed intriguing and aligns with the motivation behind the burning and thinning technique. With burning, we constrain ourselves to projecting directions at the final time step. Your proposed approach, involving the selection of the highest score, bears resemblance to filtering and resampling techniques in Markov chain literature. However, converting this concept into a well-defined distance in a population form poses challenges. Additionally, attaining global maxima through initial random projections can be computationally demanding, particularly in high-dimensional spaces. In summary, at the moment, formulating this technique within the context of SW literature is not trivial, and we defer its exploration to future work\n \n[2] Generalized Sliced Wasserstein distances, Kolouri et al\n\n[3] Distributional Sliced-Wasserstein and Applications to Generative Modelin, Nguyen et al\n\n[4] Shedding a PAC-Bayesian Light on Adaptive Sliced-Wasserstein Distances, Ohana et al.\n\n**Q21**: Line 62: Do we really need in practice to have a loss which is a distance? In practice training a model by minimizing a loss which is only definite (e.g. Kullback-Leibler) seems to be suffice.\n\n\n**A21**: One of the key advantages of optimal transport-based distances, in comparison to KL divergence (including its generalization f-divergence), is their capacity to handle non-overlapping support measures. Particularly, when confronted with non-overlapping support measures such as point clouds or histograms, KL divergence becomes ill-defined due to density ratio issues. Additionally, symmetry holds significance when aiming for a symmetric estimator, as is the case in learning latent representations. Furthermore, triangle inequality plays a crucial role in establishing distance properties, including aspects like two-sided sample complexity. All in all, possessing the complete set of metric properties proves advantageous both in theory and practical applications.\n\n\n\n**Q22**: Line 222: From what I understand, L is the number of Monte-Carlo chains, and T is the number of projections for a given MC chain. Thus the number of total projections is TxL\n\n\n**A22**: Yes, $T$ L is the number of Monte-Carlo chains, T is the number of projections for a given MC chain, and the total number of projections is $L\\times T$.\n\n**Q23**: Line 263: On choosing $\\kappa$\n\n**A23**: In the paper, we select $\\kappa$ from $\\{10, 50, 100\\}$. Here, $\\kappa$ serves as a hyperparameter, influencing the exploration of the Markov chain. A lower $\\kappa$ value fosters more exploratory behavior in the Markov chain, aiding the discovery of various project directions. However, excessively small $\\kappa$ equates MSW to SW. On the other hand, a higher $\\kappa$ value leads to a more concentrated transition distribution around the location parameter. An excessively high $\\kappa$ value causes the vMF distribution to become deterministic—akin to a Dirac delta centered at the location parameter—prompting viMSW to revert to íMSW\n\n**Q24**: On the approximation error with respect to the number of time steps $T$\n\n\n**A24**: Although augmenting $T$ could mitigate the approximation error, its reduction rate hinges on the variance of the mean projected distance along the Markov chain. This variance is influenced by both the prior and transition distributions. Currently, analyzing this variance comprehensively presents challenges. Consequently, we defer this investigation to future research works.\n\n**Q25**: Typos and presentation\n\n**A25**: We will fix all typos and adjust the revision of the paper based on your suggestion.\n"}]

Author rebuttal:
We would like to begin by extending our gratitude to the reviewers for their valuable time and feedback. In our response, we will outline a summary of additional experiments in the rebuttal PDF and provide answers to questions frequently raised by the reviewers. Further inquiries have been addressed in the corresponding rebuttal aimed at addressing the concerns of the reviewers.

1. **Detailed proof for sample complexity.** In response to the suggestion of Reviewer **YkFo**, we have provided a more detailed derivation of the sample complexity proof in the rebuttal PDF. Specifically, we discuss how we can derive the interested expectation inequality from the original probability statement of Vapnik–Chervonenkis theorem using the Jensen inequality, tail sum expectation, and change of variables.

2. **Comparison to DSW**. As suggested by Reviewer **72x2**, we have added a comparison to DSW [1]. DSW is a notable variant of SW that selects the most discriminative slicing distribution in a family of distributions over the unit-hypersphere. However, DSW still utilizes independent and identically distributed (i.i.d) projecting directions. In contrast, our focus is on constructing dependent projecting directions via the first-order Markov structure. We provide new experiments on gradient flow to compare iMSW and DSW. We set $L=2, T=5$ for both iMSW and DSW. For iMSW, we use $\eta = 0.1$. For DSW, we report the best hyperparameters: $\lambda \in {1,10,50}$ and slice learning rate $\eta \in {0.001,0.01,0.1}$. Figure 1 in the rebuttal PDF shows that iMSW still drives the flow to converge faster than DSW. For a more realistic usage of gradient flow, we repeated the comparison using point-cloud interpolation with two randomly selected point-clouds from ShapeNet [2], each containing 2048 points. Overall, we still observe the same phenomenon: iMSW is faster and performs better. Finally, we present the results of DSW in deep generative modeling on CIFAR10 with FID 14.18 and IS 8.14, which are slightly worse than iMSW. Due to time constraints, we were unable to run the experiments multiple times and conduct experiments on CelebA.

    As discussed in the paper, DSW can be used as a building block for MSW. For instance, the slicing distribution found in DSW could serve as a good prior distribution. Moreover, we can also design a transition distribution in a similar way as DSW. We would like to emphasize that MSW is the first variant of SW that discusses non-stationary slicing distribution, offering a flexible modeling opportunity. Given the extensive room for designing better prior and transition distributions based on recent literature [1], [3], we leave a detailed investigation for future work.

   [1] Distributional Sliced-Wasserstein and Applications to Generative Modeling, Nguyen et al

   [2] https://shapenet.org/

    [3] Shedding a PAC-Bayesian Light on Adaptive Sliced-Wasserstein Distances, Ohana et al.

3. **On the significance of experimental results.** As discussed with Reviewers **YkFo** and **72x2**, we would like to emphasize the significance of the experimental results. We believe iMSW has demonstrated significantly better performance in gradient flow and color transfer. Particularly, iMSW reduces the Wasserstein metric by about 91% compared to SW and by at least 50% compared to Max-SW and Max-K-SW at step 200 in gradient flow (Figure 1 and Figure 2), all while being faster. In color transfer (Figure 2), iMSW reduces Wasserstein-2 by at least 95% compared to SW and Max-(K)-SW. Additionally, it is worth noting that the scale of the distances can be easily controlled by scaling the supports of measures by a constant. In generative modeling, significantly reducing the FID score becomes challenging when reaching a high-quality generative model. For reference, the original SNGAN FID score is about 21 which is considerably worse than those reported in our paper. Overall, we provide these experiments mainly as evidence of the widely applicable capability of the proposed distances.

4. **On burning and thinning.** As discussed with Reviewers **AyBm** and **YkFo**, burning and thinning techniques could reduce computational time while maintaining comparable performance. For instance, in gradient flow, iMSW (L=2, T=5) achieves W2=0.0064 and takes 1.41 seconds, iMSW (L=2, T=5, M=0, N=2) achieves W2=0.0066 and takes 1.28 seconds, and iMSW (L=2, T=5, M=2, N=2) achieves W2=0.0072 and takes 1.19 seconds. A similar phenomenon is observed in color transfer (Table 4); for example, iMSW (L=3, T=15) achieves W2=15.23 and takes 79.47 seconds, iMSW (L=3, T=15, M=0, N=2) achieves W2=16.6 and takes 62.66 seconds, and so on. Interestingly, burning and thinning can improve performance with the right choice of hyperparameters (Table 1, Table 3, and Table 5). However, we still recommend using burning and thinning as computational acceleration techniques due to their widely recognized benefits.

Overall, we would like to reiterate that the main focus of the paper is to provide a unified approach to using dependent projecting directions for the sliced Wasserstein distance. Specifically, we offer a clear population formulation that has not been previously derived, along with a discussion of its theoretical properties. While the paper presents specific instance choices of the prior distribution and transition distribution, yielding notable performance (iMSW), the designs proposed may not be optimal and could be further improved. Given the flexibility of MSW in designing the Markov structure, we leave a thorough investigation to future work.

Best regards,

Authors,

Meta-review: The paper proposes a novel way for doing sliced Wasserstein. Instead of using an iid sampling from a
predefined distribution on the sphere, they propose to use a first-order Markovian structure on random
84 projecting directions. Several properties of the new method have been proved and its empirical performance
compared to other sliced methods has been highlighted. 
Overall, all reviewers are happy about the paper and the rebuttal and propose to accept the paper.
Decision: Accept (poster)