Fast Approximation of the Sliced-Wasserstein Distance Using Concentration of Random Projections
Authors: Kimia Nadjahi
Alain Durmus
Pierre Jacob
Roland Badeau
Umut Simsekli
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimal transport
central limit theorem
random projections
high-dimensional data
generative modeling

Abstract: The Sliced-Wasserstein distance (SW) is being increasingly used in machine learning applications as an alternative to the Wasserstein distance and offers significant computational and statistical benefits. Since it is defined as an expectation over random projections, SW is commonly approximated by Monte Carlo. We adopt a new perspective to approximate SW by making use of the concentration of measure phenomenon: under mild assumptions, one-dimensional projections of a high-dimensional random vector are approximately Gaussian. Based on this observation, we develop a simple deterministic approximation for SW. Our method does not require sampling a number of random projections, and is therefore both accurate and easy to use compared to the usual Monte Carlo approximation. We derive nonasymptotical guarantees for our approach, and show that the approximation error goes to zero as the dimension increases, under a weak dependence condition on the data distribution. We validate our theoretical findings on synthetic datasets, and illustrate the proposed approximation on a generative modeling problem.

Fast Approximation of the Sliced- wasse--Wasserstein Distance Using Concentration of Random Projections
Kimia Nadjahi Alain Durmus', Pierre Jacob Roland Badcau', Umut Şimşekli
1: LTCI, Télécom Paris, Institut Polytechnique de Paris, France Université Paris-Saclay, ENS Paris-Saclay, CNRS, Centre Borelli, F-91 190 Gif-sur- Yvette, France
3: Department of Information Systems, Decision Sciences and Statistics, ESSEC Business School, Cergy, France 4: INRIA Département d' Informatique de l'École Normale Supérieure, PSL Research University, Paris, France
Abstract
The Sliced- Wasserstein distance (SW) is being increasingly used in machine learn- ing applications alternative to the Wasserstein distance and offers significant computational and statistical benefits. Since it is defined as an expectation over random projections, SW is commonly approximated by Monte Carlo. We adopt new perspective to approximate SW by making use of the concentration of measure phenomenon: under mild assumptions, one-dimensional projections of high- dimensional random vector are approximately Gaussian. Based on this observation, we develop simple deterministic approximation for SW. Our method does not require sampling number of random projections, and is therefore both accurate and easy to compared to the usual Monte Carlo approximation. We derive nonasymptotical guarantees for our approach, and show that the approximation error goes to zero the dimension increases, under weak dependence condition on the data distribution. We validate our theoretical findings synthetic datasets, and illustrate the proposed approximation on generative modeling problem.
Introduction
Recent years have witnessed the emergence of numerical methods inspired by optimal transport (OT) to solve machine learning problems. In particular, Wasserstein distances are a core ingredient of OT and define metrics between probability measures. Despite their nice theoretical properties, they are in general computationally expensive large-scale settings. Several workarounds that scale better to large problems have been developed, and include the Sliced-Waad Wasserstein distance (SW, [ 21).
The SW metric is a computationally cheaper alternative to Wasserstein as it exploits the analytical form of the Wasserstein distance between univariate distributions. More precisely, consider two random variables X and Y in d.d with respective distributions μ and v, and denote by f 11, 8:v the univariate distributions of the projections of X, Y along E Rd. SW then compares μ and by taken with respect 0 uniformly distributed
computing W (0 μ. V)v) where the expectation on the unit sphere, and W is the Wasserstein distance.
practice, expectation typically estimated by Monte Carlo: one uniformly draws projection directions (0) and approximates SW with ---1 Σt W(O))) (0)):)) Since the Wasserstein
"Corresponding author: kimia. simia.nadjja. jahi wwwahhhieeeeooomoeceeec paris.fr
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

distance between univariate distributions can easily be computed in closed-form, this scheme leads to significant computational benefits as compared to the Wasserstein distance, provided that L is not chosen too large. SW has then been successfully applied in several practical tasks, such as classification A Bayesian inference [5), the computation of barycenters of measures [1, and implicit generative modeling 17-12). Besides, SW has been shown to offer nice theoretical properties as well. Indeed, it satisfies the metric axioms (13), the estimators obtained by minimizing SW are asympiotically consistent [1),, the convergence in SW is equivalent to the convergence in Wasserstein [3), and even though the sample complexity of Wasserstein grows exponentially with the data dimension [8). the sample complexity of SW does not depend on the dimension [9]. However, the latter study also demonstrated with a theoretical error bound, that the quality of the Monte Carlo estimate of SW depends on the number of projections and the variance of the one- dieedimensional
Wasserstein distances [19 Theorem 6]. In other words, to ensure that the induced approximation error is reasonably small, one might need choose a large value for L, which inevitably increases the computational complexity of SW. Alternative approaches have been proposed to overcome this issue, and mainly consist in picking more "informative" projection directions: e.g.. SW based on maximum SW (21), generalized SW distances [22] and distributional
orthogonal projections [10 20)
SW distances 223]
In this paper, we adopt a different perspective and leverage concentration results on random projec- tions to approximate SW: previous work showed that, under relatively mild conditions, the typical distribution of low- di-ensimeiinnll projections of nigh-dimensional random variables is close to some Gaussian law 24 25 Recently, this phenomenon has been illustrated with bound in terms of the Wasserstein distance 26) let ( {X.) be a sequence of real random variables with distribution jat- such that XI...., Xa are independent with finite fourth-order moments; then, E[ (0g U'd pm ) goes to zero as dl increases, where An, is univariate Gaussian distribution whose variance depends on jid and the expectation is taken with respect to a Gaussian variable B. This result has very recently been used to bound the "maximum-slie sliced distance" between any probability measure and its Gaussian approximation [27]. In our work, we use it to design a novel technique that estimates SW with a simple deterministic formula. As opposed Monte Carlo, our method does not depend on finite set of random projections, therefore it eliminates the need of tuning the hyperparameter I. and can lead to significant computational time reduction. Besides, our proposal is quite different from the aforementioned variants of SW which consist in selecting "informative" projection directions: these alternatives are defined as optimization problems whose resolution is challenging (e.g.. (23 Section 3.2]) and are then computed by finding an approximate solution. This incurs an additional computa- tional cost and estimation error, while our method directly approximates SW (thus, does not define an alternative distance) via simple deterministic operations, does not rely on any hyperparameters, and comes with theoretical guarantees on its induced error.
The important steps to formulate our approximate SW are summarized as follows. We first define an alternative SW whose projection directions are drawn from the same Gaussian distribution as in (26). instead of uniformly on the unit sphere, and establish its relation with the original SW. By combining this property with (26, Theorem 1J, we bound the absolute difference between SW applied to any two probability measures pa, Pa on IR, and the Wasserstein distance between the univariate Gaussians Npa. Nug- Then, we explain why the mean parameters of pd and va should be zero for the approximation error to decrease as d grows. Nevertheless, we show that it is not a limiting factor, by exploiting the following decomposition of SW: SW between Md, Va can be equivalently written as the sum of the difference between their means and the SW between the centered versions of pa, Va.
Our approach then consists in estimating SW between the centered versions with the Wasserstein term between Gaussian approximations to meet the zero-means condition, and recover SW between the original measures via the aforementioned property. Since the Wasserstein distance between Gaussian distributions admits a closed-form solution, our approximate SW is very easy to compute, and faster than the Monte Carlo estimate obtained with a large number of projections. We derive nonasymptotical guarantees on the error induced by our approach. Specifically, we define a weak dependence condition under which the error is shown to go to zero with increasing d. Our theoretical results are then validated with experiments conducted on synthetic data. Finally, we leverage our theoretical insights to design a novel adversarial framework for a typical generative modeling problem in machine learning, and illustrate its advantages in terms of accuracy and computational time, over
2

---

generative models based on the Monte Carlo estimate of SW. Our empirical results can be reproduced with our open source codo
2 Background
We first give some background on optimal transport distances and concentration of measure for random projections. All random variables are defined on a probability space (S2, F, with associated expectation operator E. We denote N N \ {0}, and for d E NN, P(RR)) is the set of probability measures on R.
2.1
Optimal transport distances
Let p E (oo+ and Pp (IR)) = {u E P(Rd) S ||=||" dp(x)) < +00} be the set of probability measures on [Rd with finite moment of order p. The Wasserstein distance of order between any H, (RR)) defined as
W2(+ inf / *EI((Le) Rd Rd*xd || yll (///dd((a) dr(
where || denotes the Euclidean norm, and [[,, v) the set of probability measures on Rd x Rdd whose marginals with respect to the first and second variables are given by Jr and respectively. In some particular settings, W, is relatively easy to compute since the optimization problem in admits closed-form solution: we give two examples that will be useful in the rest of the paper.
Gaussian distributions. Denote by N(m, Σ) the Gaussian distribution on Rd with mean m E Rd and covariance matrix Rdxd symmetric positive-definite The Wasserstein distance between two Gaussian distributions, also known the Wasserstein-Buur metric, is given by (28)
( E1), N(m,, Σ2)} = ||m m²ll² + Tr Tr[E, + E2 - 2( /////3 (2)
where Tr is the trace operator.
Univariate distributions. Consider u, (RR), and denote by Fjt and F-11 the quantile functions of μ and y respectively. By (29. Theorem 3.).).(a)).
W v) /
F (F F. (1)P
If 1 = -n=nn-1 -n SR, and n Ei= yy. with {ar f8 D R" and 6, the Dirac distribution with mass on 2, (3) can simply be calculated by sorting { and {y/ as z(1) S
I (())) and W(1) _... S V(n)- Indeed, in this case, Wg v) = n n - [m(]
- y(o) P.
However, when the empirical distributions are multivariate, Wp(n, v/ is not analytically available in general, its computation is expensive: the standard methods used to solve the linear program in ① have a worst-case computational complexity in (n log n), and tend to have super-cubic cost in practice (30 Chapter 3].
The Wasssrsessnrttnin distance [ 2 defines a practical alternative metric by leveraging the compu- tational efficiency of Wp p for univariate distributions. Let Sd-1 be the d-dimensional unit sphere and the uniform distribution gd-1, For 0 E gd-1, 6* Rd -> R denotes the linear form Ø (0, x) with () the Fuclidean inner-produce Then, SW of order p E [1, oo) between μr, Pp (Rd) is
WW) - ga-1
where for any measurable function f Fd IR and & E P(Rd), f&f is the push- forw-forward measure of & by f: for any Borel set A in I. fiC(A) (A)), with (A) {i Rd f(x) E A).
Since 6 μu, v are univariate distributions, the Wasserstein distances in (4) are conveniently computed
using (3). Besides, in practical applications, the expected value in (4) typically approximated with a standard Monte Carlo method:
See https::////tt wetggghhubb...... cww www.///maadd//////oooc.c.a..octa faattaannd/d//teeeee
3

---

SW (,, (1/L) Σ ( (00)g)) with {0:)1= i.id. from o
(5)
Computing SWp, p.L between two empirical distributions then amounts to projecting sets of n ob- servations in Rd along directions, and sorting the projected data. The resulting computational complexity is OLLdn + Ln logn,, which is more efficient than W, in general. This complexity means that the Monte Carlo estimate is more expensive when d, nt and L increase, and often unclear how L should be chosen in order to control the approximation error; [19] Theorem 6].
2.2 Central limit theorems for random projections
There is a rich literature on the typical behavior of one-dimensional random projections of high- dimensional vectors. To be more specific, let (6:) be i.i.d. standard one me-dimensional Gaussian random variables and (X; N- be a sequence of one-dimensional random variables. Denote for any d N 0nd {0.) and X1.d (X+) Several central limits theorems ensure that, under relatively mild conditions, the sequence distributions of d (01:d:
IR given 0 Rd converges in distribution to a Gaussian random variable in probability. This line of work goes back to 24 [5]], whose contributions have then been sharpened and generalized in B1 In particular, recent study (26) gives a quantitative version of this phenomenon. More precisely, denote for any d E N by fá the distribution of X1.d (i.e., the joint distribution of X1,X2, ....... Xa) and Ya the zero-mean Gaussian distribution with covariance matrix (1/d)Ig. Assume that for any E N
M E P2()).. Then, (26] Theorem I] shows that there exists a universal constant C' > 0 such that
W (05 N(0, d m2 ))) dya(0) CEa(1)) with -
(6)
Rd
Ex(uX) d d (a + (m2 ( ) (1 1/2 m2(u 115 32(1x) 4/53.
(7)
ma (2 = EE' ||X [2] alp E || m2 (2 |1| (g E. [|
where q E {1,2} and (Xf) is an independent copy of (Xi)ieN-. A formal statement of this result also given for completeness in the supplement.
3 Approximate Sliced- Wasserstein distance based on concentration of random projections
We develop novel method to approximate the Sliced-Wasse Wasserstein distance of order 2, by extending the bound in (6) and deriving novel propertics for SW. We then derive nonasymptotical guarantees of the corresponding approximation error, which ensure that our estimate is accurate for high- dimensional data under a weak dependence condition.
3.1 Sliced- Wasserstein distance with Gaussian projections
First, enable the use of (6) for the analysis of SW, we introduce variant of SW whose projections are drawn from the Gaussian distribution considered in (6), instead uniformly on the sphere. The Sliced- Wasserstein distance of order p (1,+ based on Gaussian projections is defined for any μ, E (IR as
SW (H, J WF(00n,000)aaa(())
In the next proposition, we establish simple mathematical relation between traditional SW and the newly introduced one: we prove that SW, is equal to SW, up to proportionality constant that only depends the data dimension d and the order p.
Proposition 1. Let p E +o0) Then, SW, ( is related to SW, p as follows: for any
Jt, E P,, SW, (W,(u, 122 (T(d/2 + p/2) / T(d/2)) Sw, v), where the Gamma function.

---

Since (6) only applies to the Wasserstein distance of order 2, we will focus on SW of that same order in the rest of the paper. In this case, SW with Gaussian projections equal to the original SW. Indeed,
we can show that the constant (2/d) {T(d/2 + p/2) 2) r(d/2)) defined in Proposition is equal when p 2. by using the property r(d/2 + 1) (d22)(d//))))))
3.2 Approximate Sliced- Wasserstein distance
Our next result is an easy consequence of and Proposition [ and shows that the absolute difference between S (22 va) and W (0,, d' mm2 (pa)), d m2((aa)} for any Ha, Va E P2 P2((R), is bounded from above by Ea(ua) (vaa
Theorem 1. There exists a universal constant C > O such that for any pd, Va E P2(
(SW2(Pa.z W2(N(O, mm (0 S C(Eaa(aa) + =d(va)) 1/2 (10)
where, for &a E {Ha EE(Ea) and my (Ea) are defined in and 8 respectively.
Since W2(N((, d=- N(O, d m22(m)2()) has closed-form solution by (2) it provides computationally efficient approximation of SW 2 ( Va) whose accuracy is quantified by Theorem Next, we identify settings where this approximation is accurate, by analyzing the error Ea(ua) (va).
Our first observation is that Pa and Va should have zero means for the error to go to zero as d - +oc, and we develop a novel approximation of SW that takes into account this constraint. Going back to the definition of ( x in setting X, = X, - E[X,] and X = X - E[X]], we get
(2 x = E|| X lid P] + I.a]]
(11)
B3 = E L:d x + 41 [E] X1.a)" |] ||||
(12)
By Equations 111 and 12 since in practice the norm of the mean 1.a) is expected to increase linearly with d²/2 at least, so (rx² and (2(2 functions of d. As consequence, =a(n]) cannot be shown to converge to O as d - oo in this setting, but only to be bounded. However, the data are centered, the norm of the mean is zero, thus Eg(x²) ) might be decreasing. Therefore, we derive a convenient formula to compute SW (W2a, Va) from 2W2 Pa) where for any & E (2 Ed is the centered version of &, í.e. the pushforward measure of &a by Z + x - my, with mc JRs y dy)(()) This result is the last ingredient to formulate our approximation of SW.
Proposition 2. Let pa, Va E (2(Rd) with respective means Ma my Then, the Sliced- Wasserstein distance of order 2 can be decomposed as
Sw va) SW3(Pa, Fa) (1/d) | my 11
(13)
2 instead of estimating (a) with (2( d mm(a)), N(0, m22()))) directly, we propose approximating SWa(Da Pa)
Based on Proposition
with W, 2 (N(O, d mm N(O, d 'm (2a))) and then using (13). This strategy yields our final
approximation of SW, which is defined for any pa, va P2
SWi va) = (N(O, d (p.)) d
mm (Pa)) + (1/d) mp. - m IP
(14)
where for & E (āa, Daj. m2 (Ea) is defined in 8 Note that (4) can be simplified since by 2 W3
m2 (/2) Besides, if ja and va are both supported on a finite set of points, S SW2(ua, Ma) has closed-form expression: given & = Σソ= 5200 > E (2 with x(5) e Rd for j {1...., n), we then have mę, =n = "''''=-' 20), and (E = =n Σソ= ||2 The associated computational complexity is therefore in (dn).
N(0, d m2(aa)) = d (m2
Hence, we introduced an alternative technique to estimate SW which does not rely on finite set of random projections, as opposed to the commonly used Monte Carlo technique (5). Our approach thus eliminates the need for practitioners tune the number of projections L. but also sort the
projected data. As a consequence, it is more efficient to compute SW SW2(ps P2) than SW (pa va) for large L. We illustrate this latter point with empirical results in Section
5

---

3.3 Error analysis under weak dependence
We have discussed why centering the data important to ensure that the approximation error goes to zero with increasing d. Next, we introduce a weak dependence condition under which the error is guaranteed decrease as d increases.
We first consider setting mentioned in [26] where μl ((()) 8....uud and Va = v/11 @.. .... @pld) @ denoting the tensor product of measures, and ((مر vاu E (R( for (1....,d) ,d,. We prove in this case that 2 (N d (m2()))), d m (va))) converges to SW2 Va) at a rate of d 1/8, This result reported in the supplementary document, and can be interpreted as an extension of [26] Corollary 3] for SW.
We emphasize that the assumptions of this first setting severely restrict the scope of application of our approximation method: in several statistical and machine learning tasks, the random variables of interest {x,) are not independent from each other (e.g. for image data, each X; typically represents the value of a pixel at a certain position, thus depends on the neighboring pixels). Therefore, we relax this independence condition by considering a concept of 'weak dependence" inspired by [3] and properly defined in Definition [
Definition 1. Let (Xj)jeN- be a stationary sequence of one-dimensional random variables with = O. We say that (Xj)JeN- fourth-order weakly dependent if there exist some constant K 2 and nonincreasing sequence of real coefficients (p(n)FnEN such that, for any i, E EN, i
mean zero, i.e. X; and Xj have the same distribution for any i, E I and [[X]]=
[Cov(X; (X2, x33) I Kplj - i),
(X, Kp(j - i)
(15)
In addition, the sequence {p(n) satisfies D p(n) S Pso < +o0
Intuitively, in practical applications, the weak dependence condition would essentially require the components of the observations not to exhibit strong correlations; yet, they are allowed to depend on
each other. Furthermore, since weak dependence condition is weaker than the one introduced in
[3 Theorem IJ, it is satisfied by the various examples of models described in [39] Section 5J. We
present some of them below, illustrate Definition I more clearly.
1) Gaussian processes and associated processes 40 Section 3.1], provided that they are stationary.
2) Bernoulli shifts: X, , ét-r) for I E N*, where H RR+1 R is measurable function and (Ei)veN- is a sequence of i.i.d. real random variables. A simple example of such process given by moving-average models.
3) Autoregressive models, defined as X, -(X, sequence of i...d. real random variables with E |&il < co, and [f(u)...... (uu....."0 u,,
Xt-r) + for L N*, where (Ei)seN-
(w1,...... Ur)
E ai 14 m/| for some a,,-.., 0r 0 such that (E=1a)) 1/r 1.
We then consider a sequence of fourth-order weakly dependent random variables (X,) and prove that =x(xx) goes to zero as d + co, with a rate of convergence depending on (p(n) meN. This result is given in the supplementary document, and helps refine Theorem [ under this weak dependence condition: the next corollary establishes that the error approaches 0 at rate of d 1/8
Corollary 1. Let (X,) and (Yj)sEN= be sequences of random variables which are fourth-order weakly dependent. Set for any E No, X1.d = [X,]4=1 and YI.a = {Y,))==> and denote by pa, Va the distributions of X1sd Yıa respectively. Then, there exists a universal constant C >> 0 such that
SW 2 ( ua) - (N,, mm ((0.d--mp)
S Cd/1/88
Hence, by replacing the independence condition of the first setting with weak dependence, we broaden the scope of application whilst guaranteeing that the approximation error goes zero d increases. We finally note that in these two settings, the data are required to have zero mean, which is automatically verified with our approximation method since we estimate SW between the centered distributions (see eq. [44) )
Experiments
Synthetic experiments. The goal of these experiments is illustrate our theoretical results derived in Section 3 In each setting, we generate two sets of d-dimensional samples, denoted by {z(1) fj=1

---

30
10P
0.25
10x1
0.5
app
(a) Nonzero means
(b) Zero means
(c) Gaussian noise
(d) Student-t noise
Figure 1: Analysis of the approximation according to the dimension: in Figures I(a) and T(b) data
have independent components, in Figures [[c] and [(d] they are stationary AR(1) processes. Errors
are averaged over 100 runs and reported on log-log scale with their 10th-90th percentiles.
aperoximation orter
2.0
Monte Carlo, 1000
Monte Carlo, 5000
time (in sac]
method
1.0
4-
0.5
0.0
10
10" dimension
107
10'
10'
10
Figure 2: Comparison of different methods to approximate SW, according to their accuracy (left) and computation time (right). The datasets contain n samples of dimension d independently drawn from Gamma distributions, with [10*, 10a] and n 10 Results are averaged over 100 runs.
and fulr) with 10 and 200),y00 E Rd for j E .l....,n]. We then approximate SW between their empirical distributions in P2(R"), given by ps = -1 Ei 8209 and va n E"=1 8ym-
First, we analyze the consequences of centering data. Here, (r 1==ı: (3 are indepen- dent samples from Gaussian or Gamma distributions: see the supplementary document for more details. We compute 2 d m= N(0, d' mz
SW2 ( va)l on the one hand, 2W 2a)l on the other hand. the Gaussian case, the exact value of SW₂ is known (we report it in the supplementary document), while for the Gamma distributions, it is approximated with Monte Carlo based on 2 x 10 random projections. Figures I(a) and ((b) show that the error goes to zero as d increases if the data centered. This confirms our analysis provided in Section 3.2 about the influence of the mean, and in Section 3.3 on sequences of independent random variables.
and (2 (Ra)) N( m=-))
Next, we consider autoregressive processes of order one (AR(1)). An AR(1) process is defined as Xi and, for i E N', Xx aXt-1 Et, where [0, 1] and (E:) is an i.i.d. sequence of real random variables with E[e]] = and finite second-order moment. If a < 1, the process has stationary distribution and (X, JEN- satisfies the weak dependence condition in its stationary regime 41 In practice, we generate sample by using this recursion formula for 10a + d steps, and keeping the last d samples. The discarded samples correspond
"burn-in" phase which helps reaching the stationary solution of the process. We generate {z((6 In j==1 and { yy=1 using the same distribution for the noise (either Gaussian or Student's l-distribution, as described in the supplementary document). This means that both datasets come from the same distribution, thus the exact value of SW₂ is zero. We plot on Figures
[(c) and [(d) the approximation eтror according
to d E [10, 100] for different values of a. The error converges to zero with increasing d, which consistent with Corollary [
Note that Figure exhibits rate of convergence that are better than the one in d1// derived in Section 3.3 in Figure [(b). the slope is approximately -0.45 (Gaussian) and -0.7 (Gamma), and
in Figures| [(c) and [(d], it is on average -0.35. This suggests that our theoretical bounds might be improved, and we further investigate this aspect for the Gaussian case: consider the
where {z(0) Jj=1, (1))) 1 py
n independent samples from Gaussian distributions with diagonal
7

---

Tsw (s/epoch)
Tiot (s/epoch)
Dataset
Model
FID
GPU
CPU
GPU
CPU
MNIST
SWG
2.34
1.3
1.4 x10
4.5
2.7 x10
Reg-SWG
15.53 + 0.88
1.1
1.1 x102
6.5
3.0 x102
Reg-der-SWG
15.72 0.57
0.07
0.2
5.3
1.5 x102
CelebA
SWG
31.04 2.78
10.1
2.7
X10
3.9 x x
1.6 x10
Reg-SWG
24.14 0.48
10.0
2.7
x10
4.4 x10
2.0 x10*
Reg-det-SWG
23.65 = 0.93
1.3
2.6
4.2 x x10
1.7 x10*
Table 1:
Results obtained after training generative models on MNIST and CelebA, averaged over 5 runs. FID reported with their standard deviation (the lower FID, the better). Tsw denotes the average time per epoch for approximating SW. Tux is the average running time per epoch.
covariance matrices, and we prove that E| W 2 (N d' (ma)), N(O, d' (22))) SW2 ( Pa)l goes 0 as dn + +00 with convergence rate in d
1/2, We provide the complete statement and formal proof in Section (Proposition S3 This result is consistent with Figure [(b] and first encouraging step towards the following research direction: we will study if our proofs and the ones in [26] can be refined when assuming additional structure on the distributions (e.g.. Gaussinni and sub-exponential). in order to identify the settings under which our current bounds are tight or can be improved.
Finally, compare our approximation scheme against the standard Monte Carlo estimation, in terms of accuracy and computation time. We use the same setting as in Figure [(b]] where the samples are independently drawn from Gamma distributions. We compute SW2(Ha, va) (14) and SWa,r. ua) (5) with L E (100, 1000, 5000), and we compare each approximation with SW2,2x10 10 (/a: Ma), which we consider as the exact value of SW. Figure 2 reports reportss the approximation error and computation time of each scheme for d E [10, 10"]. and shows that our method is more accurate and faster than Monte Carlo. In particular, when d = 10s, the average computation time of our technique is 0.02s, while the second best approximation (Monte Carlo with L = 5000) takes more than 8s. Besides, we observe that Monte Carlo is very sensitive to the hyperparameters, since it loses accuracy when L decreases and gets slower L and d increase. This observation is consistent with the computational complexity of SW2.1 recalled in Section 2.1 On the other hand, approximation scheme is extremely efficient even for large d and since it based on simple deterministic formula which does not require projecting and sorting data along random directions.
Image generation. Finally, we leverage theoretical insights to design novel method for typical generative modeling application. The problem consists in tuning neural network that takes as input k-dimensional samples from a reference distribution (e.g.. uniform or Gaussian), generate images of dimension d >> A: During the training phase, the parameters of the network are updated by iteratively minimizing dissimilarity measure between the dataset to fit and the generated images.
In 19) the dissimilarity measure is Monte Carlo SW approximated with 10 random projections, and the resulting generative model is called the Sliced- Wassersten generator (SWG). This model performs well on moderately high-dimensional image datasets (e.g., 28 x 28 for MNIST images [42). ). However, for very large dimensions (e.g., 64 64 x for the CelebA dataset 48) Monte Carlo SW requires more than 10 random projections to capture relevant information, which leads to very expensive training iterations and potential memory issues. To offer better scalability. SWG can be augmented with a discriminator network [9] Section 3.2] that aims at finding a lower-dimensional space in which the two projected datasets are clearly distinguishable. The intuition behind this heuristic is that the more distinct the two datasets are from each other, the fewer projection directions Monte Carlo SW requires to provide useful information. The training then consists in optimizing the generator's 's and discriminator's ' objective functions in an alternating fashion.
Our novel approach builds on SWG and modifies the aaddle-point problem in 9 Section 3.2]: motivated by the gain in accuracy and time illustrated in Figure 2 on high-dimensional datasets, we propose replace Monte Carlo SW with approximate SW (14) in the generator's is objective; then, to make sure that our approximation is accurate, we regularize the discriminator's objective:
max L( + Y1 Covld (X)I + > |llCoolldd (as (Z
(16)
+ Ao EE [1 (X) + A2 E (go
(17)
8

---

3
2
2
3
8
6
9
4
6
3
2
2
7
9
4
3
9
8
3
4
7
7
9
6
9
6
8
9
5
3
9
6
1
4
4
3
4
7
8
7
6
/
S
4
4
8
2
5
O
4
8
4
4
6
7
0
/
X
4
3
7
3
4
6
6
4
7
7
4
5
E
3
T
i
3
/
/
7
0
O
3
2
7
4
9
8
O
O
C
/
8
7
3
i
9
3
O
9
/
5
2
7
5
4
6
/
6
/
O
0
4
3
6
/
3
9
2
7
O
5
9
4
2
4
4
6
7
8
4
8
/
4
7
6
4
3
2
Q
3
8
8
6
5
7
7
7
(a) SWG (FID= 19.52)
(b)
Reg-det-SWG (FID 14.87)
(c) SWG (FID- 27.75)
(d) Reg-det-SWe (FID = 22.87)
Figure 3: Images generated after training on MNIST (top row) and CelebA (bottom row). For each model, the images are associated with the lowest FID obtained over 5 runs.
where L is the discriminator's 's loss used in SWG, 96 and dy the generator's last layer and the discriminator's 's penultimate layer respectively (parameterized by o, vb), X and Z are the random variables corresponding to the images to fit and the generator's 's input, Cov denotes the covariance matrix, || the Frobenius norm, and X1 A2 0. The regularization in (16) enforces the weak dependence condition (Corollary] while (17) prevents the network to converge to d' = We call this generative adversarial network regularized deterministic SWG (reg-det-SWG).
To investigate the consequences of (i) regularizing the discriminator, and (ii) replacing the Monte Carlo SW with our approximation, we design another model, called regularized SWG (reg- (WG): similarly to SWG, the generator minimizes SW but the discriminator's objective is regularized as in (6). [17. We then compare reg-det-SWa against SWG and reg-SWG, by training the models on MNIST and CelebA and measuring their respective training time and Fréchet Inception Distances (FID, 44): see T We used the same network architectures for all methods, and tuned (A1, A2) via cross-vais validation: more details on the experimental setup are given in Section [S4] First, we observe that the regularized models produce images of higher quality, since reg-SWG and reg-det-SWG return lower FID values than SWG. The FID of reg-SWG and reg-det-SWG are close for both datasets, thus the two models seem yield similar performances. Hence, we report in Figure the images generated by SWG and reg-det-SWG only.

---

The training process is more expensive when regularizing the discriminator: the average running time per epoch is higher for the regularized models. We also observe that reg-det- is faster than reg-SWG, which is consistent with the fact that our approximation method is faster than Monte Carlo on high-dimensional settings. To further illustrate this point, we reported the average time spent in computing the generative loss per epoch, i.e. 2W2,10 for SWG and reg-SWG, and SW for reg-det-SWG: see column Tsw in Table On GPU, reg-det-SWG is at least 15 times faster than SWG and reg-SWG on MNIST, and 6 times faster on CelebA. Note that the models were trained using PyTorch, thus Monte Carlo SW benefits from a GPU-accelerated implementation of the sorting operation (with the function torch. sort). We also reported the computation times when models are trained on CPU. In this case, computing SW₂ takes at most less than 3s per epoch, whereas the Monte Carlo estimation executes in several minutes (e.g., approximately 45min on CelebA). As result, the total training time is almost the same for Set--de-WWG and SWG CelebA, and the lowest for reg- reg-det-SWe SWG on MNIST.
5 Conclusion
In this work, we presented novel method approximate the Sliced-Wasserstee Wasserstein distance of order 2, which relies on the concentration-of-nee -f----uuu- phenomenon for random projections. The resulting method computes SW with simple deterministic operations, which are computationally efficient even on high-ddmensiooal settings and do not require any hyperparameters. We proved nonasymptotical guarantees showing that, under a weak dependence condition, the approximation error goes to zero as the dimension increases. Our theoretical findings are then illustrated with experiments on synthetic datasets. Motivated by the computational efficiency and accuracy of our approximate SW, we finally designed novel approach for image generation that leverages our theoretical insights, As compared to generative models based on SW estimated with Monte Carlo, our framework produces images of higher quality with further computational benefits. This encourages the use of our approximate SW on other algorithms that rely on Monte Carlo SW, e.g. autoencoders
[ or normalizing flows [12]
The weak dependence condition can be inappropriate to describe the underlying geometry of real data in ML applications, and in that case, approximating SW with our method seems inadequate. To overcome this problem, we encourage practitioners to resort to models where real data are represented by features that can be made weakly dependent. This strategy has proven successful in our image generation experiment: the reg- Seg-Ge model uses our approximation to compare two sets of features (instead of the raw images) whose covariance matrices are regularized to enforce weak dependence. Since many ML techniques make use of features and regularizers, we believe that our methodology is not restrictive and can then be applied to other standard problems than image generation. Besides, our weak dependence condition in Definition] I is weaker than the one in (39]. which is a notion commonly used in statistics.
Our empirical results on synthetic data show that the approximation error goes to zero with a faster convergence rate than the one we proved. Then, the main current limitation of our framework is that our theoretical convergence rate in d-1//8 might be slower than necessary. We proved that the overall approximation error is popedebbunded by term in 1/2 when comparing Gaussians with diagonal covariance matrices, and the improvement of our error bounds for other specific distributions is left for future work. On the other hand, the extension of our methodology variants of SW is another challenging future research direction. To the best of our knowledge, the literature on the concentration of measure phenomenon focuses linear random projections, therefore the derivation of deterministic approximations for SW based on nonlinear projections seems highly nontrivial. A more promising direction would be generalize our approach to SW based k-dimensional linear projection by leveraging the bound in (26] Theorem 1] for A >>> 1.
Since this paper is focused developing a theoretically -grounddd novel method to estimate distance between probability distributions, we believe it will not pose any negative socictal or cthical consequence. On the other hand, as demonstrated in Section 4 our contribution provides tools to speed up existing machine learning algorithms on CPU, which is useful when powerful hardware resources not available, when their use is deliberately avoided for environmental purposes.
10

---

Acknowledgments and Disclosure of Funding
This work is partly supported by the industrial chair "Data Science & Artificial Intelligence for Digitalized Industry & Services" from Télécom Paris. Umut Simşekli's research is supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' a'avenni" program, reference E. Jacob gratefully acknowledges support by the National Science Foundation through grant DMS- 1844695. Alain Durmus acknowledges support of the Lagrange Mathematical and Computing Research Center. Kimia Nadjahi is grateful to Pierre Colombo for his helpful advice on how train the generative models in Section
(PRAIRIE 31A Institute). Pierre
4 on Télécom Paris's GPUs.
References
[1] Julien Rabin, Gabriel Peyré, Julie Delon, and Marc Bernot. Wasserstein Barycenter and Its Application to Texture Mixing, In Alfred M. Bruckstein, Bart M. ter Haar Romeny, Alexander M. Bronstein, and Michael Bronstein, editors, Scale Space and Variational Methods in Computer Vision, pages 435-446 Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978- 178-3-642-24785--
[2] Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51(1):22-45, 2015.
[3] Soheil Kolouri, Yang Zou, and Gustavo K Rohde. Sliced- W Wasserstein Kernels for Probability distributions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4876-4884, 2016.
[4] Mathieu Carrière, Marco Cuturi, and Steve Oudot. Sliced Wasserstein Kernel for Persistence Diagrams. In Doïna Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 664-673, International Convention Centre, Sydney, Australia, 06-11 11 Aug 2017, PMLR.
[5] Kimia Nadjahi, Valentin Bortoli, Alain Durmus, Roland Badeau, and Umut Simsekli. Approximate Bayesian Computation with the Sliced-W Boodd-Wassse Wasserstein distance. pages 5470-5474, 05 2020. doi: 10.1109/ CCASSP44077..022000552
[6] Samuel Cohen, S Sesh Kumar, and Marc Peter Deisenroth. Sliced Multi-Marginal Optimal Transport, 2021.
Soheil Kolouri, Gustavo K Rohde, and Heiko Hoffmann. Sliced Wasserstein distance for Leamiing Gaussian Mixture Models. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3427-342443 -436, 2018
[8] Soheil Kolouri, Phillip E. Pope. Charles E. Martin, and Gustavo K. Rohde. Sliced Wasserstein Auto- Encoders. In International Conference on Learning Representations, 2019.
[9] Ishan Deshpande, Ziyu Zhang, and Alexander Schwing. Generative Modeling using the Sliced Wasserstein Distance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3483-3491, 2018.
[10] Jiqing Wu, Zhiwu Huang. Dinesh Acharya, Wen Janine Thoma, Danda Pani Paudel, and Van Gool. Sliced Wasserstein Generative Models. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 371 3713-3722, 2019.
[11] Antoine Liutkus, Umut Simsekli. Szymon Majewski. Alain Durmus, and Fabian- Robert Stöter. Sliced- Wasserstein Flows: Nonparametric Generative Modeling via Optimal Transport and Diffusions. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pages 4104 4113, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
[12] Biwei Dai and Uros Seljak. Sliced Iterative Normalizing Flows, 2021.
[13] Nicolas Bonnotte. Unidimensional and Evolution Methods for Optimal Transportation. PhD thesis, Paris
11, 2013.
[14] Kimia Nadjahi, Alain Durmus, Umut Simsekli, and Roland Badeau. Asymptotic Guarantees Learning Generative Models with the Sliced- Wasserstein distance. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems 32, pages 250-260. Curran Associates, Inc., 2019.

---

[15] Erhan Bayraktar and Gaoyue Guo. Strong equivalence between metrics of Wasserstein type. 2019.
[16] Richard M. Dudley. The speed of mean Glivenko-Cantelli convergence. Ann. Math. Statist. 40(1)):00500 02 1969. doi: 10. 10.12144omm/1117700 177697802.
[17] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3-4):707, August 2015.
[18] Jonathan Weed and Francis Bach. Sharp asymptotic and sanite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli, 25(4A):2620-205 2648, 11 2019, doi: 10.3150/18-1 S-BEJJOG 1065.
[19] Kimia Nadjahi, Alain Durmus, Lénaic Chizat, Soheil Kolouri, Shahin Shahrampour, and Umut Simsekli. Statistical and Topological Properties of Sliced Probability Divergences. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20802 20812. Curran Associates, Inc., 2020.
[20] Cheng Meng. Yuan Ke, Jingyi Zhang, Mengrui Zhang, Wenxuan Zhong, and Ping Ma. Lcage-scale optimal transport map estimation using projection pursuit. In Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E, Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[21] Ishan Deshpande, Yuan-Ting Hu, Ruoyu Sun, Ayis Pyrros, Nasir Siddiqui, Sanmi Koyejo, Zhizhen Zhao, David Forsyth, and Alexander Schwing. Max-Sliced Wasserstein distance and its use for GANs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 10648-10656. 2019.
[22] Soheil Kolouri, Kimia Nadjahi, Umut Simsekli, Roland Badeau, and Gustavo Rohde. Generalized Sliced Wasserstein Distances. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox. and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 261-272 Curran Associates, Inc., 2019.
[23] Khai Nguyen, Nhat Ho, Tung Pham, and Hung Bui. Distributional Wassersenss and Applications to Generative Modeling. In International Conference on Learning Representations, 2021.
[24] Vladimir Nikolaevich Sudakov. Typical distributions of linear functionals in finite dimensional spaces of high dimension. Soviet Math. Dokl., 19(6):5578 1582, 1978.
[25] Persi Diaconis and David Freedman. Asymptotics of Graphical Projection Pursuit. The Annals of Statistics, 12(3))793- 815, 1984, doi: (2.1121/aos// 1ttes//11666.. 176346703.
[26] Galen Reeves. Conditional central limit theorems for Gaussian projections. 2017 IEEE International Symposium on Information Theory (ISIT), pages 3045-3049, 2017, doi: 10. (00p//STT.207780070000
[27] Scbastian Goldt, Bruno Lourciro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. The Gaussian equivalence of generative models for learning with shallow neural networks. Proceedings of Machine Learning Research, 145:1 - 46, 2021.
[28] D.C Dowson and B.V Landau. The Fréchet distance between multivariate normal distributions. Journal of Multivariate Analysis, 1203):450-455, 1982. ISSN 0047-259X. doi: https://doi. 100/ 10160044000004725999900 90077-X.
[29] Svetlozar T Rachev and Ludger Rüschendorf. Mass Transportation Problems: Volume I: Theory, volume 1. Springer Science & Business Media, 1998.
[30] Gabriel Peyré and Marco Cuturi. Computational Optimal Transport: With Applications to Data Science. Foundations and Trends in Machine Learning, (((6)))3556677 2019. ISSN 1935-8237. doi: 10. 2200000073.
[31] Peter Hall and Ker-Chau Li. On almost Linearity of Low Dimensional Projections from High Dimensional Data. The Annals of Statistics, 21(2):867 - 889, 1993. doi: 1214////a 17634911551
[32] Heinrich von Weizsäcker. Sudakov's typical marginals, random linear functionals and a conditional central limit theorem. Probability Theory and Related Fields, 107(3):313 324, Mar 1997.
[33] Milla Antila, Keith Ball, and Irini Perissinaki. The Central Limit Problem for Convex Bodies. Transactions of the American Mathematical Society,
2003. ISSN 00029947.
[34] Sergey G. Bobkov. On concentration of distributions of random weighted sums. The Annals of Probability. 31(1):195 215, 2003. doi: 10.1214/aop/1044224000
12

---

[35] Bo' az Klartag. A central limit theorem for convex sets. Inventiones mathematicae, 168(1)991-131, Jan 2007. doi: 10.1007/s00222-000 -20-02202220000002------
[36] Elizabeth Meckes. Approximation of Projections of Random Vectors, Journal of Theoretical Prohability, 25(2):333-352 Jun 2010. doi: 10.1007/s19959-0111 -000999900-2992222
[37] Lutz Dümbben and Perla Del Conte-Zerial. On low-dimensional projections of high-dimensional distribu- tions. Institute Mathematical Statistics Collections, pages 91 104, 2013. doi:
[38] Hannes Leeb, On the conditional distributions of low-dimensional projections from high-dimensional data. The Annals of Statistics, 41(2):464- 483, 2013. doi: 10.1214/1-AOSS0881
[39] Paul Doukhan and Michael H. Neumann. Probability and moment inequalities for sums of weakly dependent random variables, with applications. Stochastic Processes and their Applications, 117(7):
878 (13--903,2200 2007. ISSN 4304-4149. doi: https//0b..oog//000001161pp...02
[40] Paul Doukhan and Sana Louhichi. A weak dependence condition and applications inequalities. Stochastic Processes and their Applications, 84(2):313- 3-24,, 1999. ISSN 0304-4149, doi: https://doi.org/10.10000
[41] Paul Doukhan and Michael H. Neumann. The notion of v-weak dependence and applications to bootstrapping time series. Probability Surveys, 5(none): 146 168, 2008. doi: 10.1214/06-PS08.
[42] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL httth://yyyann.... Lecun com/ wwwdeenddssteeeeeeeeeeeeeeeeesee /mnist/
[43] Ziwei Liu, Ping Luo, Xiaogang Wang, Xiaoou Tang. Deep Learning Face Auributes in the Wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[44] Martin Heusel, Hubert Ramsauer. Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium. In Proceedings of the st International Conference on Neural Information Processing Systems, NIPS' 17, page 6629-6640, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860999
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section S
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and the supplementary document.
(b) Did you include complete proofs of all theoretical results? [Yes] See the supplementary document.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material as a URL.)? [Yes] See the supplementary material or wrtttps:///ittaai
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the supplementary material.
(c) Did you report error bars (e.g., with respect the random seed after running experi-
ments multiple times)? [Yes] See Section 4
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4 and the supplementary document.
13

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See the supplementary material.
(b) Did you mention the license of the assets? [Yes] See the supplementary material.
(c) Did you include any new assets either the supplemental material or as URL? [es]] See the supplementary material or httttts: / giggitth com/ kimi hammiindd/aassttm
(d) Did you discuss whether and how consent was obtained from people whose data you 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "sa12KXVsK8I", "reviewer": "Reviewer_sFFp", "summary": "The paper presents a method to estimate the Sliced-Wasserstein distance. The method is based on the Gaussian approximation of the projected data, thus the SW distance could be approximated through the SW distance between Gaussians which has a closed-form. Hence, the method is better than the Monte Carlo SW distance in term of computational speed. The authors also demonstrate their method on toy data set and real data sets, i.e. MNIST and Celeb A.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper starts with reviewing some results from Reeves that the SW-2 distance between the  projected distribution and the corresponding Gaussian could be bounded by a constants which depends on the mean and covariance matrix. Then in Section 3,  it moves to the SW-2 distance with Gaussian projections, where they proved that  the SW-2 distance using unit projection vector is proportional to the SW-2 distance using Gaussian projection. This result is not surprising, since the way to generate random unit vector from uniform distribution on the sphere based on normalzing a Gaussian vector. From the theoretical point of view, normalzing a Gaussian vector in high dimensional space to form an unit vector will not affect too much to the effect of the SW-2 distance. Because in high dimensional space, a Gaussian vector with independent components has a similar magnitude of length by the law of large number.  Using Gaussian projection might only  have some advantages of playing with the formulas rather than the effectiveness of the projection. \n\nIn section 3.2,  the authors  provide a similar bound for the difference between the SW-2 distance between two probability measures and W-2 distance between the corresponding Gaussian distributions, which is bounded by function of covariance matrices.  Section 3.3 shows the error analysis under the assumption of weak dependence between vector's components and the dependency between vector's component decrease as the gap between components increases.  The reviewer personally finds the condition of weakly dependency quite unrealistic.  It could be realistic in some cases like time series data. But weak dependency is closer to independency, thus the point cloud of the distribution is all over the space, i.e point cloud of Gaussian distribution. It  is quite contradictory to the popular view that the data generally lie in a low dimensional manifold. What could the authors comment about it?\n\nThe experiment section starts with a toy example of synthetic data, it is time series  data, so it is quite different from other data sets, because there is an order between components and weakly dependency condition over the order of components. For the real data set, they present 3 methods of  two using the Monte Carlo.  Among them, the Reg-det-SWG obtains a comparable FID score but a much faster processing time. However, the authors have not compared their methods with other methods of selecting important directions for projection.  \n\nOverall, this work is based on approximating the SW-2 distance. The main question is that why on the real data the approximation produces a comparable performance  with  the Monte Carlo method even when the number of the projection for the Monte Carlo method is large and the upper bound for the approximation error is not small? Because of the above-mentioned reasons, I do not believe that the theory of weak dependency is the  explanation for the comparable performance of the method on the real data set. Hence, there needs at least an ablation study to shed some light on the question.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is fine.", "review_text": "", "extra_scores": {"ethical_concerns": "It is fine.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8 hours"}, "extra_text": {}}, {"review_id": "VnXO6iVzFn4", "reviewer": "Reviewer_QHXY", "summary": "The paper proposes a new approach to approximate the sliced Wasserstein distance. In particular, the paper extends the central limit theorems for random projections to derive a deterministic approximation of sliced Wasserstein (based on the closed form of Wasserstein distance between two Gaussians) that is efficient (low error) in high dimension under centering assumption (weak dependence assumption). On the experimental side, the paper illustrates the derived theory on the synthetic data and compares the proposed approach to the conventional Monte Carlo approximation of the sliced Wasserstein distance.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: Gaussian projections were also used in the sliced score matching technique [1], however, the application to the sliced Wasserstein in the paper is original. The deterministic approximation of the sliced Wasserstein that is based on the usage of the central limit theorems for random projections is new and novel.\n\nQuality: The submission is technically sound. The error between the proposed approximation and the true value of the sliced Wasserstein is bounded for both two assumptions. Moreover, the paper haves demonstrated the superiority of the new approximation over the Monte Carlo estimation in terms of both computation complexity and performance in generative modeling experiments.  The authors have also discussed the limitations of the approximation due to the independence (the weak dependence) assumption. The experiments are adequate for showing the faster computational speed of the deterministic sliced Wasserstein.\n\nClarity: The paper is well-written, easy to follow. The experimental settings are reported enough to reproduce. The proofs are written rigorously and correctly.\n\nSignificance: The paper pushes forward the practical applications of the sliced Wasserstein distance, and provides a new insight to understand the distance. However, the convergence rate is slow, hence, the approximation seems only efficient in the case of very high dimensional measures.\n\n[1] Sliced Score Matching: A Scalable Approach to Density and Score Estimation", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The weak dependence assumption is not easy to be satisfied in practice, additional experiments on other datasets  (CIFAR-10, LSUN) and other applications (e.g. autoencoders, approximate Bayesian computation) are needed. The approximation seems only work well with high dimensional measures, hence, I think it is necessary to do some experiments on applications that involves low dimensional  measures (latent space of autoencoders, color transfer).\n\nMinor comments: FID scores should also be reported in the middle of the training process (different epochs).\n\nQuestions:\n1. is it possible to extend the result to derive deterministic approximation for the non-linear projecting (generalized sliced Wasserstein) and other extensions of sliced Wasserstein such as max sliced Wasserstein, k-max sliced Wasserstein and spherical sliced Wasserstein [2]?\n2. Can we derive an algorithm to transport a measure to a measure like the iterative distribution transfer algorithm for this type of approximation? \n\n[2] Improving Relational Regularized Autoencoders with Spherical Sliced Fused Gromov Wasserstein", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "Na0cQZUEZq-", "reviewer": "Reviewer_Zsjv", "summary": "This paper introduces a (possibly) cheaper approximation of Sliced Wasserstein (SW) distance. The proposed technique is based on calculating 1D Wasserstein distance between Gaussian projection directions. This is motivated by the fact that Wasserstein distance between Gaussian distributions admits a closed-form solution, which leads to an easy compute of the proposed approximate SW and discard a large number of uniformly sampling random projections for the Monte Carlo approximation of the original SW distance.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: the authors propose a new approach for approximate the SW distance using 1D Wasserstein distance between Gaussian distributions. Under mild conditions, the authors provide nonasymptotic guarantees on the error between the original and proposed approximation of SW distance. Overall, I find the exposure being well supported by the theory and the results are important to the field of sliced Wasserstein distances research direction. The paper is clearly written. The authors introduce all the material needed to understand the method. The proofs are well detailed and seem reasonable.\n\nWeaknesses: the rate $d^{-1/8}$ for the nonasymptotical analysis seems (too) slow, whereas some experiments show a decay for this error for reasonable values of $d$. There is one important missing work that should be cited though:\n\nNguyen, Khai, et al. \"Distributional Sliced-Wasserstein and Applications to Generative Modeling.\" (https://arxiv.org/abs/2002.07367)\n\nwhere authors proposed the distributional slicing approach which is a general technique to design a probabilistic way to select important direction by finding optimal distribution over explored projections. I really believe this paper could also lead to interesting computational comparisons.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "LeLOmLajWr1", "reviewer": "Reviewer_L6sj", "summary": "This paper develops a novel deterministic approximation for the Sliced-Wasserstein Distance (SWD), based on the fact that a random linear projection of a high-dimensional vector has an approximately Gaussian distribution. In many cases, the approximation involves no tuning parameters and can be computed much more quickly than the usual Monte Carlo estimate of SWD, especially for very high-dimensional data. If the $d$ dimensions of the data are not too strongly correlated, then the approximation converges no slower than $d^{-1/8}$ as $d \\to \\infty$. Experiments with synthetic data validate this theoretical result, as well as the computational benefits of the proposed approximation. Finally, the paper demonstrates an application to image generation.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is very clearly written and well-motivated, and the proposed estimator seems novel and useful. From a statistical perspective, I have some concerns about the usefulness of the provided theoretical results.\n\nMain Comments/Questions:\n1) The paper bounds the error between the true SWD and the approximation when the true data distributions are used. In reality, empirical distributions over IID data, rather than the true distributions are used. Roughly speaking, the paper bounds the bias of the proposed estimator, but not the variance. Could the authors discuss the rate as which the variance decays as the sample size increases?\n\n2) A convergence rate of d^{-1/8} is quite slow (a decrease by a factor of ~1.3 for each 10-fold increase in dimension). On the other hand, based on the synthetic experiments, it appears that the estimator might converge at a faster rate in practice. Could the authors speculate on whether this theoretical rate is tight (in the worst case) under the given fourth-order weak dependence assumption, and/or under what conditions the convergence rate might be faster? I see that this is noted in Lines 339-342, but it would be nice if the authors could expand on this a bit.\n\nMinor Comments:\n1) Line 126: Typo: \"whose contributions has\" -> \"whose contributions have\"\n\n2) Line 128, \"$\\mu_d^X$, the distribution of $X_{1:d}$\":  Upon first reading, it wasn't immediately clear to me whether $\\mu_d^X$ was the *empirical distribution* of the data, the *population distribution* from which each X_i was drawn IID, or the *joint population distribution* of all d. If I understand correctly, the assumption that $\\mu_d^X \\in \\mathcal{P}_2(\\mathbb{R}^d)$ (on Line 129) only really makes sense under the last interpretation, but this distinction could be clearer on Line 128.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper briefly discusses an apparent gap between the main theoretical and empirical results. I don't foresee any potential negative societal impact of the work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The focus of the submission is the fast approximation of the sliced-Wasserstein distance (SW). Particularly, the authors present a new scheme to tackle this task relying on specifically designed Gaussian projections as an alternative to the widely-used Monte Carlo approximation (where the projection directions are distributed uniformly on the unit sphere and their number often has to be large to achieve highly-accurate approximation), with consistency guarantees. The efficiency of the approach is demonstrated on synthetic examples and in generative modelling (tuning a neural network for image generation with SW objective).

Estimating the discrepancy of probability measures in R^d is a fundamental problem in statistics and machine learning with numerous applications. The submission is a well-organized, clearly-written work in this direction where the authors deliver important tools (SW estimator) with sound theoretical guarantees as assessed by the reviewers; it can be of definite interest to the ML community.
Decision: Accept (Poster)