Quasi-Monte Carlo for 3D Sliced Wasserstein
Authors: Khai Nguyen
Nicola Bariletto
Nhat Ho
Venue: ICLR 2024 spotlight (2024)
Keywords: Sliced Wasserstein
Monte Carlo Methods
Point-Cloud
Quasi-Monte Carlo
Optimal Transport
Primary area: representation learning for computer vision, audio, language, and other modalities
TL;DR: We propose Quasi-Sliced Wasserstein and Randomized Quasi-Sliced Wasserstein which are new approximation methods for Sliced Wasserstein distance based on Quasi-Monte Carlo methods.

Abstract: Monte Carlo (MC) integration has been employed as the standard approximation method for the Sliced Wasserstein (SW) distance, whose analytical expression involves an intractable expectation. However, MC integration is not optimal in terms of absolute approximation error. To provide a better class of empirical SW, we propose quasi-sliced Wasserstein (QSW) approximations that rely on Quasi-Monte Carlo (QMC) methods. For a comprehensive investigation of QMC for SW, we focus on the 3D setting, specifically computing the SW between probability measures in three dimensions. In greater detail, we empirically evaluate various methods to construct QMC point sets on the 3D unit-hypersphere, including the Gaussian-based and equal area mappings, generalized spiral points, and optimizing discrepancy energies. Furthermore, to obtain an unbiased estimator for stochastic optimization, we extend QSW to Randomized Quasi-Sliced Wasserstein (RQSW) by introducing randomness in the discussed point sets. Theoretically, we prove the asymptotic convergence of QSW and the unbiasedness of RQSW. Finally, we conduct experiments on various 3D tasks, such as point-cloud comparison, point-cloud interpolation, image style transfer, and training deep point-cloud autoencoders, to demonstrate the favorable performance of the proposed QSW and RQSW variants.

Published as a conference paper at ICLR 2024
QUASI-MONTE CARLO FOR 3D SLICED WASSERSTEIN
Khai Nguyen, Nicola Bariletto & Nhat Ho Department of Statisties and Data Sciences
The University of Texas at Austin
Austin, TX 78712, USA
(kha thh n ciciolll e bari letto, mi www.etto..mmnnatteeeeeeeeeoe Buteeast.eeeeexeeeeee...
ABSTRACT
Monte Carlo (MC) integration has been employed as the standard approximation method for the Sliced Wasserstein (SW) distance, whose analytical expression involves intractable expectation. However, MC integration is not optimal in terms absolute approximation error. To provide better class of empirical Sw, we propose quasi-sliced Wasserstein (QSW) approximations that rely on Quasi- Monte Carlo (QMC) methods. For comprehensive investigation of QMC for SW, we focus on the 3D setting, specifically computing the SW between probability measures in three dimensions. In greater detail, we empirically evaluate various methods to construct QMC point sets on the 3D unit-hypersphere, including the Gaussian-based and equal area mappings, generalized spiral points, and optimizing discrepancy energies. Furthermore, to obtain an unbiased estimator for stochastic optimization, extend QSW to Randomized Quasi-Sliced Wasserstein (RQSW) by introducing randomness in the discussed point sets. Theoretically, we prove the asymptotic convergence of QSW and the unbiasedness of RQSW. Finally, we duct experiments on various 3D tasks, such as point-cloud comparison, point-cloud interpolation, image style transfer, and training deep point-cloud autoencoders, demonstrate the favorable performance of the proposed QSW and RQSW variants
INTRODUCTION
The Wasserstein (or Earth Mover's) distance (Peyré & Cuturi 2020 has been widely recognized as a geometrically meaningful metric for comparing probability measures. For instance, has been successfully employed in various applications such as generative modeling (Salimans al. 2018), domain adaptation (Courty et al.] (017), clustering (Ho et al.) (017). and so on. Specifically the Wasserstein distance serves as the standard metric for applications involving 3D data, such as point- cloud reconstruction (Achlioptas et al. 2018), point-cloud registration (Shen et al. [222]) point-cloud completion (Huang et 20.33, point-cloud generation (Kim al. 2020), mesh deformation (Feydy et al. 2017). image style transfer (Amos et al. 2023), and various other tasks.
Despite its appealing features, the Wasserstein distance exhibits high computational complexity. When using conventional linear programming solvers, evaluating the Wasserstein distance carries a O(n logn) time complexity (Peyré Cuturi 2020), particularly when dealing with discrete probability measures supported on at most atoms. Furthermore, computing the Wasserstein distance has at least (n²) space complexity, which is related to storing the pairwise transportation cost matrix. The Sliced Wasserstein (SW) distance (Bonneel et al. (0055) stands rapid alternative metric to the plain Wasserstein distance. Since the SW distance is defined as sliced probability metric based on the Wasserstein distance, it is equivalent to the latter while enjoying appealing properties (Nadjahi) iet al. 2020). More importantly, the time complexity and space complexity of the SW metric are only log and O(n). respectively. As result, the SW distance has been successfully adopted in various applications, including domain adaptation (Lee et al.) 2019). generative models (Nguyen
Ho 2024, Nguyen et al. 2024). clustering (Kolouri et al. 2018). gradient flows (Bonet al.
2022). Bayesian inference (Yi & Liu 2021). and more. In the context of 3D data analysis. the SW
distance is employed numerous applications such as point-cloud registration (Lai & Zhao 2017).
"Code for the paper is published httpttp:://gtthhuucccm/

---

Published as a conference paper at ICLR 2024
reconstruction, and generation (Nguyen et al., 2023). mesh deformation (Le et al. 2024a), shape matching (Le et al. 2024b). image style transfer (Li et al. 2022), along with various other tasks.
Formally, the SW distance is defined the expectation of the Wasserstein distance between two one-dimensional projected measures under the uniform distribution over projecting directions, i.c., the unit hypersphere. Exact computation of the SW distance is well-known to be intractable; hence, in practice, it is estimated empirically through Monte Carlo (MC) integration. Specifically, (pseudo- Drandom samples are drawn from the uniform distribution over the unit hypersphere to approximate the analytical integral. However, the approximation error of MC integration is suboptimal because (pseudo-)uniform Juniform random samples may not exhibit sufficient "uniformity" over the space (Owen) 2013). Quasi-Monte Carlo (QMC) methods (Keller 1995) address this issue by building determin- istic point sets, known as wwwdescerepacy sequences", on which to evaluate the integrand. Low discrepancy implies that the points are more "uniform" and provide superior approximation of the uniform expectation over the domain, compared to randomly drawn points.
Conventional QMC methods primarily focus on integration over the unit hypercube [0, 1j (for 2 1). To assess the uniformity of a point set on [0, 10, a widely employed metric the "star- discrepancy" (Koksma 1942). A lower star-discrepancy value typically results in reduced approxi- mation error, as per the Koksma-Hlawka inequality (Koksma 1942). When a point set exhibits a sufficiently small star sur-discrepancy, it is referred to as "low-discrepancy sequence". For the unit cube, several options exist, such as the Halton sequence (Halton & Smith 1964). the Hammersley point set (Hammersley) 2013), the Faure sequence (Faure) 1982), the Niederreiter sequence (Niederreiter 1992), and the widely used Sobol sequence (Sobol 1967). QMC integration is renowned for its efficiency and effectiveness, especially in low (e.g., 3) dimensions.
Contribution. In short, we integrate QMC methodologies into the framework for SW distance computation. Specifically, our contributions are three-fold:
1. As the SW distance involves integration over the unit hypersphere of dimension d - 1, rather than the well-studied (for QMC purposes) hypercube, we provide an overview of practical methods for constructing point sets on the unit hypersphere, which can serve as candidates for oowdiscrepaancy sequences (referred to as QMC point sets). Specifically, our exploration encompasses the following techniques: (i) mapping a oow-diccepaanc sequence from the 3D unit cube to the unit sphere using the normalized inverse Gaussian CDF, (ii) transforming a low-discrepancy sequence from the 2D unit grid to the unit sphere via the Lambert equal-area mapping, (iii) using generalized spiral points, (iv) maximizing pairwise absolute discrepancy, (v) minimizing the Coulomb energy. Notably, we believe that our work is the first to make use of the recent numerical formulation of spherical cap discrepancy (Heitsch & Henrion 2021 to assess the uniformity of the aforementioned point sets.
2. We introduce the family of Quasi-Sliced Wasserstein (QSW) deterministic approximations the SW distance, based on QMC point sets. Furthermore, we establish the asymptotic convergence of QSW to the SW distance, the size of the point set grows to infinity, for nearly all constructions of QMC point sets. For stochastic optimization, we present Randomized Quasi-Monte Carlo (RMQC) methods applied the unit sphere, resulting in Randomized Quasi-Sliced Wasserstein (RQSW) estimations. In particular, we explore two approaches for generating random point sets on Sd 1. transforming randomized point sets from the unit cube and random rotation. We prove that nearly all variants of ROSW provide unbiased estimates of the SW distance.
3. We empirically demonstrate that QSW and RQSW offer better approximations of the SW distance in 3D applications. Specifically, we first establish that QSW provides a superior approximation to the population SW distance compared to conventional Monte Carlo (MC) approximations when comparing 3D empirical measures over point clouds. Then, we conduct experiments involving point- cloud interpolation, image style transfer, and training deep point-cloud autoencoders to showease the superior performance of various QSW and ROSW variants.
Organization. The remainder of the paper is organized as follows. We first provide some background on the SW distance, MC estimation, and QMC methods in Section 2 Then, we discuss how to construct QMC point sets on s define QSW and RQSW approximations, and discuss some of Deetioon[oontinnn experiments point-cloud autoencoders,
their theoretical properties in Section image style transfer, and deep point-cloud reconstruction. We conclude the paper in Section Finally, defer the proofs of key results, related work, and additional material to the Appendices.
2

---

Published as a conference paper at ICLR 2024
Notation. For any d 2 2, define the unit hypersphere 8d-1 (0 E R 1|01 = 1}, and denote the uniform distribution on it as 4( For p 2 1. Pp(x) represents the set all probability measures the set X' that have finite p-moments. We denote 0īμ as the push-forward measure o fo of through the function ʃo : TR + defined as fo(2) = OTT. x. For a vector X (II,,..,, Fm) E I Px represents the empirical measure 1 Lim 8p
2
BACKGROUND
In Section 2.1
we define the SW distance and review the standard MC approach to estimate it. After delve into QMC methods for approximating integrals over the unit hypercube.
that, in Section 2.2
2.1
SLICED WASSERSTEIN DISTANCE AND MONTE CARLO ESTIMATION
Definitions. Given p 2 1, the Sliced Wasserstein (SW) distance of order p (Bonneel et al. 2015 between two probability measures μr, y (R( (i.e., with finite pth moment) defined as
(W) E3- [Wp(0tu, 0iv)].
where (0t 0tz) is the one-dimensional Wasserstein between the projections of μ and v along direction 0. As mentioned, one has the closed-form Wp(Otu, 0tw) = So I' F (z), where Fogs (+) and (-) are the inverse cumulative distribution functions of 0ūμ and 0iv.
Monte Carlo estimation. To approximate the intractable expectation the SW distance formula, MC samples are generated and give rise to the following estimate:
(w, D)
wg(0rtp,
(2)
where random samples o,,..., 0r (referred to as projecting directions) are drawn i.i.d. from (Sd-1).
When μ and y are discrete probability measures that have most supports, the time complexity of
to compute SW, is O Ln log n + Ldn), while the corresponding space complexity is O(Ld Ln).
We refer to A in Appendix B for more details on the computation of (2).
Monte Carlo error. Similar to other usages of MC, the approximation error of the SW decreases at O(L-1/2) rate. greater detail, a general upper-bound (Nadjahi et al. 2020) is:
E Or.....rHHene HuL(B--1) SW (W,,,,;
- SWP(H,)))
Varo (V((0H,002)) 1/2
VL
2.2 QUASI-MONTE CARLO METHODS
Problem. Conventional Quasi-Monte Carlo (QMC) methods focus on approximating an integral T= JJo.1 fx=)dxx= [ (fx)) on the unit hypercube [0, 1]d, with ((( 1Jd) denoting the corresponding uniform distribution. Similarly to MC methods, QMC integration also approximates the expectation with an equal weight average (LL) = 1/ f(x)). However, the point set 0 . Or is constructed differently.
Low-diserepancy sequences. QMC requires point set 21,... Sr. such that f(L.)
as L - oc, and aims to obtain high uniformity. To measure the latter, the star discrepancy (Owen 2013) has been used: 1" (211...,,
(x)),1))))),; where Fz Fz #L) = 3 L2 (the empirical CDF) and (o Vol((0, .x)) is the CDF of the uniform distribution over the unit hypercube. Since the star discrepancy the sup-norm between the empirical CDF and the CDF of the uniform distribution, the points 21,-..; Et are asymp- 0. Moreover, there is a connection between the
supze(o.1)4 (=
totically uniformly distributed if D* (x),,..., .t) star discrepancy and the approximation error (Hlawka 1961) via the Koksma-Hlawe inequality, In particular, we have:
[Î(L) π D (z ........ 21) Varu (f),
(3)
3

---

Published as a conference paper at ICLR 2024
where (J) is the total variation of in the sense of Hardy and Krause (Niederreiter 1992 Formally, #1,...; ZL is called oovieiccyyynccy sequence D (z1...... ........,y IL) E OIL Therefore, QMC integration can achieve better approximation than its MC counterpart if L 2 since the error rate of MC is ( In relatively low dimensions, e.g., three dimensions, QMC gives a better approximation than MC. Several such sequences have been proposed, e.g., the Halton sequence (Halton & Smith 1964), the Hammersley point set (Hammersley (013), the Faure sequence (Faure 1982), the Niederreiter sequence [ (1992). and the Sobol sequence (Sobol 1967). We refer the reader Appendix B for the construction of the Sobol sequence.
QUASI-MONTE CARLO FOR 3D SLICED WASSERSTEIN
In Section 3.1. explore the construction of candidate point sets low-discrepancy sequences the unit hypersphere. Subsequently, we introduce Quasi-Sliced Wasserstein (QSW), Randomized Quasi-Sliced Wasserstein (RQSW) distance, and discuss their properties in Section 3.2 3.3
3.1 LOW-DISCREPANCY SEQUENCES ON THE UNIT-HYPERSPHERE
Spherical cap discrepancy. The most used discrepancy to measure the uniformity of point set 01...., Or E gd-1 is the spherical cap discrepancy (Brauchart Dick 2012):
D O1)
sup
Σ 1=1
1LLEO(w.)) co(C(w,t))
(4)
wE3d 1-83--11E(-11 1111
L
where C(w, t) fx gd I x) < t) is spherical cap, and oo is the law of of Is proven
that ......, 0r are asymptotically uniformly distributed D (f....., O2) + (Brauchart &
Dick 2012) A point set O,,...,,) O,. is called a low-discrepancy sequence on Sa if D3a (O,,..., ,0,) E OLL 3/4 [o)( For some functions belonging to suitable Sobolev spaces, lower spherical cap discrepancy leads to a better worse-case error (Brauchart & Dick 2012 Brauchart et al. 2014).
QMC point sets gd-1, We explore various methods to construct potentially cis-discyypancy sequences on the unit hypersphere. Some of these constructions are applicable to any dimension, while others are specifically designed for the 2-dimensional sphere 52 R
Gaussian-based mapping. Utilizing the connection between Gaussian distribution and the uniform distribution over the unit hypersphere, i.e., x (O, Ia) then æ/||=||2 ~ (1(511),, we can map low-discrepancy sequence Z #y on [0, 1] to potentially low-discrepancy sequence o2,..., 0, on Sd-1 through the mapping 0 = f(x) & (--(2)) 1--@000(000 (xx la. where Φ- is the inverse CDF of (O 1) (entry-wise). This technique is mentioned in Basu 2016 and can be used in any dimension.
Equal area mapping. Following the same idea of transforming a low-discrepancy sequence the unit grid, we can utilize an equal area mapping (projection) to map from [0, 1] to s². For instance, we use the Lambert cylindrical mapping [x; y) (2 y²² (os()) 2/ y sin(2rx), 1 2y). This approach generates an asymptotically uniform sequence which is empirically shown to be -os-diccepaancy on S (istleitner et al. 2012).
Generalized Spiral. We can explicitly construct a set of L points that are equally distributed on S with
spherical coordinates (ø1, d2) (Rakhmanov et al. 1994]; 2 =1 - 2 T, 0. cos cos- 612
2
1.8/Loh mod 2x for 1,.... L. We can then retrieve Euclidean coordinates through the mapping (Ø1, Φ2) + (sin(22) cos( ), sin (b) sin())), cos()1)). This construction outputs an
asymptotically uniform sequence (Hardin et al., al.] (0166) which is empirically shown to achieve optimal worst-case integration error Braaccarrt al. (2014) for properly defined Sobolev integrands.
Maximizing Distance and minimizing Coulomb energy. Previous work (Brauchart et al. 2014 2016) suggests that choosing point set 01..... Or which maximizes the distance Hardin et al.
Ei. E 0, 0-00, or minimizes the Coulomb energy Σ Σ}=1 - could create a potentially low-discrepancy sequence. Such sequences are also shown to achieve optimal worst-case error by BBauchart et al. (2014), though they might suffer from sub-optimal optimization in practice. Also, minimizing the Coulomb energy is proven to create an asymptotically uniform sequence (Götz) 2000). In this work, generalized spiral points initialization points for optimization.
4

---

Published as a conference paper at ICLR 2024
Empirical comparison. We adopt recent numerical approximation for the spherical cap discrep- ancy (Heitsch & Henrion 202I) to compare the discussed L-point sets. We visualize these sets and the corresponding discrepancies for L 10, 50, 100 in Figure o in Appendix D.I. Overall, generalized spiral points and optimization-base points yield the lowest discrepancies, followed by equal area mapping construction. The Gaussian-based mapping construction performs worst among QMC methods; however, it still yields much lower spherical cap discrepancies than conventional random points. Qualitatively, we observe that the spherical cap discrepancy is consistent with the uniformity of point sets. We also include a comparison with the theoretical line CL-3//4 v Vlog(L) L) for some constant C, in Figure 7 in Appendix [.I] In this case, we observe that the equal area mapping sequences, generalized spiral sequences, and optimization- sequences seem to attain low-discrepancy, as per definition. For convenience, we refer to these sequences as QMC point sets.
3.2 QUASI-SLICED WASSERSTEIN
Quasi-Monte Carlo methods for SW distances. Based on the aforementioned QMC point sets in Section 3.1 can define the the QMC approximation of the SW distance as follows.
Definition Given p 2 1, d 2 2, two probability measures p. v E Pp (R and QMC point set ....... fr. E gd-1, Quaauu-attaaa Sliced Wasserstein (QSW) approximation of order p between μ and is:
QSW Sawplu,,,, (u, 01 Ol)
(0(tt,,,01t)))
(5)
L
We refer to Algorithm in Appendix B for the computational algorithm of the QSW distance.
Quasi-Sliced Wasserstein variants. We refer to (i) QSW with Gaussian- mapping QMC point set as GQSW, (ii) QSW with equal area mapping QMC point set as EQSW, (iii) QSW with QMC generalized spiral points as SQSW, (iv) QSW with maximizing distance QMC point sets as DQSW, and (v) QSW with minimizing Coulomb energy sequence as CQSW.
Proposition With point sets constructed through the Gaussian-based. mapping, the equal area mapping, the generalized spiral points, and minimizing Coulomb energy, we have @SW, vz 01, - (,, v) as - oc.
The proof of Proposition is in Appendix A.1
We now discuss some properties of QSW variants.
Computational complexities. QSW variants are deterministie, which means that the construction of QMC point sets, which can be reused multiple times, carries a one-time cost. Therefore, the computation of QSW variants has the same properties as for the SW distance, i.e., the time and space complexities are OL log + -dn) and O + Ln), respectively. Since the QSW distance does not require resampling the set of projecting directions at each evaluation time, faster to compute than the SW distance if QMC point sets have been constructed in advance.
Gradient Approximation. When dealing with parametric probability measures, e.g., Vs, we might be interested in computing the gradient V&SW (w, us) for optimization purposes. When using QMC
integration, we obtain the corresponding deterministic approximation V QSW" Pe
02)
+ V WP (0:5,, 0.t1s) for a QMC point set Oy,.... Or. For more detailed definition of the gradient of the SW distance, please refer to Tanguy 2023). Since deterministic gradient
approximation may not lead to good convergence of optimization algorithms for relatively small L, we develop an unbiased estimation from QMC point sets the next Section.
Related works. The SW distance is used as an optimization objective to construct QMC point set on the unit cube and the unit ball in Paulin et al.] (2020). However, a QMC point set on the unit-hypersphere is not discussed, and the SW distance is still approximated by conventional Monte Carlo integration. In contrast to the mentioned work, our focus is on using QMC point sets on the unit-hypersphere to approximate SW. The usage of heuristic scaled mapping with Halton sequence for SW distance approximation is briefly mentioned for the comparison between two Gaussians in (Lin et al. 2020). In this work, consider broader class of QMC point sets, assess their quality with the spherical cap discrepancy, discuss some randomized versions, and compare them in real applications. For further discussion related work, please refer Appendix C
5

---

Published as a conference paper at ICLR 2024
1wa3
2
319.4
0058
DCDA
00E2
DO0A
Figure 1: The error for approximation SW distances between empirical distributions over point-clouds.
3.3 RANDOMIZED QUASI-SLICED WASSERSTEIN
While QSW approximations could improve approximation error, they are all deterministic. Fur- thermore, the gradient estimator based on QSW deterministic, which may be well-suited for convergence in optimization with the SW loss function. Moreover, QSW cannot yield any confidence interval about the SW value. Consequently, we propose Randomized Quasi-Sliced Wasserstein estimations by introducing randomness into QMC point sets.
Randomized Quasi-Monte Carlo methods. The idea behind the Randomized Quasi-Monte Carlo (RQMC) approach is to inject randomness into a given QMC point set. For the unit cube, we can achieve a random QMC point set I Iı,.... J7, by shifting (Cranley & Patterson 1976) i.e.
y1 (x; + U' mod for all i = I,.... L and U ~ ([00 1) In practice, scrambling (Owen 1995)
preferable since gives a uniformly distributed random vector when applied to x (0, In greater detail, is rewritten into that, we permute a1,- ag randomly to obtain the scrambled version of æ. Scrambling is applied to all points in QMC point set to obtain randomized QMC point set.
Σ 6 b=aa for base b digits and ak {0, 1,... b 1}. After
Randomized QMC point sets on sd-1. To the best of our knowledge, there no prior work of randomized QMC point sets the unit-hypersphere. Therefore, discuss two practical ways to obtain random QMC point sets i.e., pushfoward QMC point sets and random rotation.
Pushfoward QMC point sets. Given randomized QMC point set ,' on the unit-cube (unit-grid), we can use the Gaussian- mapping (or the equal area mapping) to create a random QMC point set on the unit hypersphere 0f,- .... 0z As long as the randomized sequence o' ......p. is low-discrepancy on the mapping domain (e.g., as it happens when using scrambling), the spherical point set 8....., 8',,
......,,, x
will have the same uniformity as the randomiddd construction.
Random rotation. Given a QMC point set 0,,..., Or, the unit-hypersphere Sd-1, we can apply uniform random rotation to achieve a random QMC point set. In particular, we first sample ~ u(V((R")) where V Vd((Rd) the new sequence 0g.... 8y, with 0' = U0; for all i I,.... L. Since rotation does not change the norm of vectors, the randomized QMC point set can be still cow-diccrppancy sequence of the original QMC point set is low- www-iscrepancy. Moreover, sampling uniformly from the Stiefel manifold
(U ud
Ia} the Stiefel manifold. After that, we form
is equivalent to applying the Gram-Smine orthogonalization process to 21,..., Bartlett decomposition theorem (Muirhead) 2009).
iid ~ N( Ia) by the
Definition 2. Given p 2 d 2, two measures p.v (R and randomized QMC point set 0 0z E gd-1, Randomized Quasi-Sliced Wasserstein estimation order p between l and is:
RQSW V. 8%,)
1
Σ W (().
L
1=1
We refer Algorithms and for more details on the computation of the ROSW approximation.
Randomized Quasi-Sliced Wasserstein variants. For pushfoward QMC point sets, we refer to (i) RQSW with Gaussian- mapping RGQSW, (ii) ROSW with equal area mapping REQSW. For random rotation QMC point sets, we refer to (iii) RQSW with Gaussian-based mapping as RRGQSW, (iv) ROSW with equal mapping RREQSW (v) RQSW with generalized spiral

---

Published as a conference paper at ICLR 2024
Table 1: Summary Wasserstein-2 2 distances (multiplied by 10") from three different runs.
Falications
Seep (W2 L)
Step 2000 200 J)
Stup (W; U)
Step 400,W, 3)
Stop 500 (W2 1)
(s4)
5,701 0,085
0.178 0.021
0.01 0.001
01,004 0.001
5.57
GOSW
0.335 & 0.0
0,255 2.00
0.077
0.07 2.00
3.008 0.0
5:38
BQSW
0..
0,071
30000
5.37
SQSW
5.718 010
4.00
0075
B
30000 20.0
5:38
DQSW
6.792 + 0.0
0.195 2
0.77 0.0
0.07 0.00
0.67 =0.00
8:37
CQSW
5:002 0.0
0.103 0.0
0.07 + 0.0
0.066:00..
0.06==0.0
8.37
ROQSW
5.727 4: 0.005
0.107 0.000
0,022 0.00:
0.807 0,001
01003 2: 0.001
8.75
BRGOOSW
5.788 9-0002
0.166 = 00000
0.025 0,003
0.011 = 5-0000
0.006 = 0.001
5:40
REOSW
5.737 4-0.017
0.17L = 0.003
0,022 0,002
0.007 200001
0,005 2: 0.001
6.78
RRBOSW
5,704 4: 0.011
DL163 = 0.033
0.021 2: 6.0
0.007 2: -00000
0,001 2: 0.001
5.41
BSQSSW
5.722 0.0
0:189 0.001
0:221 0:00
0.067 9-0.001
0.002 0.0
8.45
BDOSW
5.725 0.0002
0.100 0.091
0:025+ 0:002
0.000 +00002
0.003 0:002
8.40
ROQSW
5.721 0.002
0.167 0.032
0.02 0.0
0.007 0.000
0.003 0.001
8:45
points as RSQSW, (vi) ROSW with maximizing distance QMC point ROSW with minimizing Coulomb energy sequence as RCOSW.
RDQSW, and (vii)
Gaussian based mapping and random rotation randomized Quasi-Monte Carlo point sets are uniformly distributed, and the corresponding estimators RQSW;
Proposition 2.
p (1,, v; 0; 1....,, (,) are
unbiased estimations of SW (s, u) i.e., B[RQSW (J,, 12 - 01)] U),
The proof of Proposition in Appendix A.2 We now discuss some properties of RQSW variants.
Computational complexities. Compared to QSW, ROSW requires additional computation for ran- domization. For the push- muss-fforward approach, scrambling and shifting earry a ([d) time complexity. In addition, mapping the randomized sequence from the unit-cube (unit-grid) to the unit-hypersphere has time complexity (Ld). For the random rotation approach, sampling a random rotation matrix costs (dd)) After that, multiplying the sampled rotation matrix with the precomputed QMC point set costs O (d in time complexity and (Ld) in space complexity. Overall, in the 3D setting where d = 3 and n >> L > d. the additional computation for RQSW approximations is negligible compared to the (n log n.) cost from computing -ie-dimensional Wasserstein distances.
Gradient estimation. In contrast to QSW, ROSW is random and is an unbiased estimation when combined with the proposed construction of randomized QMC point sets from Proposition [ There- fore, it follows directly that E R.VS ( rule of differentiation. Therefore, this estimation can lead to better convergence for optimization.
va; 0/ ..., 0')] V voSW vs) due the Leibniz
4 EXPERIMENTS
We first demonstrate that QSW variants outperform the conventional Monte Carlo approximation (referred to as SW) in Section 4.1 We then showcase the advantages of RQSW variants in point-cloud interpolation and image style transfer, comparing them to both QSW variants and the conventional SW approximation in Section 4.2 and Section 4.3) respectively. Finally, we present the favorable performance of QSW and RQSW variants in training deep point-cloud autoencoder.
4.1 APPROXIMATION ERROR
Setting. We select randomly four point-clouds (1. 2, 3, and with 3 dimensions, 2048 points) from ShapeNet Core-55 dataset (Chang et al., 2015) as shown in Figure [] After that, we use MC estimation with clouds 1-2, 1-3, 2-3, and 3-4, then treat them the population value. Next, we vary L in the set (10, 100, 500, 1000, 2000, 5000, 10000) and compute the corresponding absolute error of the estimation from MC (SW), and QMC (QSWs).
100000 approximate SW between empirical distributions over point-
Results. We illustrate the approximation errors in Figure T From the plot, is evident that QSW approximations yield lower eиrors compared to the conventional SW approximation. Among the QSW approximations, CQSW and DQSW perform the best, followed by SQSW. In this simulation, the quality of GQSW and EQSW is not comparable to the previously mentioned approximations. Nevertheless, their errors are at least comparable to SW and are considerably better most of the time.
4.2 POINT-CLOUD INTERPOLATION
Setting. To interpolate between two point-clouds X and Y, we define the curve 2(t) = -nVz() z(0) [SW, (Pz(). Pr)] where Px and Py are empirical distributions over X and Y in turn. Here, the curve starts from (()) X and ends at Y. In this experiment, we set X as point-cloud 1
7

---

Published as a conference paper at ICLR 2024
CQSW
RCQSW
Figure 2: Point-cloud interpolation from SW, CQSW, and RCQSW with L 100.
Source
458.29
COSWI 149.22
RCOSWN
Target
Figure 3: Style- transferred images from SW, CQSW, and RCQSW with L 100. Table 2: Reconstruction losses (multiplied by 100) from trained by different approximations with L 100.
Approximation
Apoch
Epoch
Epoch
SW,(D)
W2(1)
SWo (1)
Wo(L)
SWa (-)
Wo(.)
SW
2,25 1. 0.06
10.58
0.12
2.11 0.004
9.92 1
1:91 1. 0.05
9:21 0.06
GOSW
11.17 = 0.07
32.58
0.06
11.76 D.07
33.27 0.00
14,82 0.02
37
0.05
EQSW
2.25 1: 0.02
10.57 -: 0.02
2.06 0.00
9.84 1:
1:90 1:001:00 0.04
9.20 0.07
SQSW
2.25 2: 11.01
10.57
0.01
2,08 0.01
9.90 2: 0.04
1:90 0,02
9.17 2: 11:55
DQSW
0.07
0.05
0.04
9.83 1
1.36 0.05
9.12 0.01
2.22
0.02
9:06
9:92
RRGQSW
0.001
0.05
9:84
REQSW
2.24: 0.04
0.90
1.80 0.04
9.17 0.06
RRBOSW
2.21 0.00
10.50
0.04
2.03 0.02
9.80 1. 0.02
1.58 0,05
9.15 1106
RSQSW
2.22 0.05
10.53
0.01
2.04 0.06
9.62 1 0.06
1.85 0.05
9.12 1. 0.02
KDOSW
2.21 0:03
10.00
0.02
2.03 0.04
9.82
0.04
1.86 2: 0,115
9.12 =: 1142
ROQSW
2.22 - 0.05
10.50 0.05
2 03
0.02
0.82
0.08
1.85 + 0.05
9.12 0.05
and Y point-cloud 3 in Figure 1 After that, conventional SW. QSW variants, and RQSW variants to perform the Euler scheme with 500 iterations, step size 0.01. To verify which approximation gives the shortest curve in length, compute the Wasserstein-2 distance (POT library, Flamary et al. (202T)) between Pz(() and Py.
different gradient approximations from the
Results. We report Wasserstein-2 distances (from three different runs) between Pz()) and Py time step 100, 200, 300, 400, 500 in Table with L = 100. From the table, we observe that QSW variants do not perform well in this application due to the deterministic approximation of the gradient with fixed set of projecting directions. In particular, although EQSW and CQSW perform the best time steps 100 and 200, QSW variants cannot make the curves terminate. As expected, ROSW variants can solve the issue by injecting randomness to create new random projecting directions. Compared to SW. RQSW variants are all better except RRGQSW. We visualize the interpolation for SW, COSW, and RCQSW in Figure 2 The full visualization from all approximations is given in Figure in Appendix D From the figures, we observe that the qualitative comparison is consistent with the quantitative comparison in Table ! In Appendix D.2 also provide the result for L 10 in Table 3 and the result for different pair of point-clouds in Table 4 and Figure 9 We refer the reader (opeeddi(D.2]fooo more detailed discussion.
4.3 IMAGE STYLE TRANSFER
Setting. Given a source image and target image, we denote the associated color palettes as X and Y, which are matrices of size we iterate along the curve between Px and Py. However, since the value of the color palette (RGB) the set [O.... 255), we need to perform an additional rounding step at the final Euler iterations. Moreover,
(n is the number of pixels). Similar to point-cloud interpolation,
iterations i.e., 1000, and bigger step size i.e., 1.
Results. For = 100, we report the Wasserstein-2 2 distances at the final time step and the corre- sponding transferred images from SW, CQSW, and RCQSW in Figure 3 The full results for all approximations are given in Figure i0 Appendix [D3 In addition, we provide results for L = 10 in Figure 11 in Appendix D.3 Overall, QSW variants and ROSW perform better than SW in terms
8

---

Published as a conference paper at ICLR 2024
CQSW
Figure Reconstructed point-clouds from SW. CQSW, and ROQSW with L = 100.
of both Wasserstein distance and visualization (brighter transferred images). Comparing QSW and RQSW, the latter yields considerably lower Wasserstein distances. In this task, RQSW variants display quite similar performance. We refer the reader to Appendix D33 for more detail.
4.4 DEEP POINT-CLOUD AUTOENCODER
Setting. We follow the experimental setting in (Nguyen et al., 2023) to train deep point-cloud autoencoders with the SW distance on the ShapeNet Core-55 dataset Chang et al. (2015). We aim
to optimize the following objective min [x))(X) (S,((xx Pa (X))))) where [xX) is our
data distribution, fo and dy are a deep encoder and a deep decoder with Point-Net Qì et al. (2017) conventional MC estimation. QSW, and ROSW
architecture. To optimize the objective, to approximate the gradient V and V.. We then utilize the standard SGD optimizer to train the autoencoder (with embedding size of 256) for 400 epochs with learning rate of 1e-3, batch size of 128, a momentum of 0.9, and a weight decay of 5e-4. To evaluate the quality of trained autoencoders, compute the average reconstruction losses, which are the W2 and SW₂ distances (estimated with 10000 MC samples), on different dataset i.c., ModelNet40 dataset (Wu et al. 2015).
Results. We report the reconstruction losses with L 100 in Table 2 (from three different training times). Interestingly. CQSW performs the best among all approximations i.e., SW, QSW variants, and ROSW variants the last epoch. We have an explanation for this phenomenon. point-cloud interpolation which considers only one pair of point-clouds, we estimate an autoencoder from an entire dataset point-clouds. Therefore, model misspecification might happen here i.e., the family of Point-Net autoencoders may not contain the true data-generaie distribution. Hence, 10 in Table 66
contrast to
100 might be large enough to approximate well with QSW. When we reduce in Appendix 4.4 CQSW and other QSW variants become considerably worse. In this application, we also observe that GQSW suffers from some numerical issues which leads to a very poor performance. As solution, RQSW performs consistently well compared to SW especially random rotation variants. We present some reconstructed point-clouds from SW, CQSW, and RCQSW in Figure 4 and full visualization in Figure 12 13 Overall, we recommend RCQSW for this task safe choice. We
refer the reader to Appendix D.4 for more detail.
CONCLUSION
We presented Quasi-Sliced Wasserstein (QSW) approximation methods, which give rise to better class of numerical estimates for the Sliced Wasserstein (SW) distance based on Quasi-Monte Carlo (QMC) methods. We discussed various ways to construct QMC point sets the unit hypersphere, including the Gaussian-based mapping, the equal area mapping, generalized spiral points, maximizing distance points, and minimizing Coulomb energy points. Moreover, we proposed Randomized Quasi- Sliced Wasserstein (RQSW) approximations, which is family of unbiased estimators of the SW distance based on injecting randomness into deterministic QMC point sets. We showed that QSW methods can reduce approximation error in comparing 3D point clouds. In addition, we showed that QSW variants and RQSW variants provide better gradient approximation for point-cloud interpolation, image-style transfer, and training point-cloud autoencoders. Overall, we recommend RQSW with random rotation of QMC point sets minimizing Coulomb energy, since it gives consistent and stable behavior across tested applications. In the future, plan extending QSW and ROSW approximations to higher dimensions d > 3, and apply QMC to other variants of the SW distance.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
We would like to thank Peter Müller for his insightful discussion during the course of this project. NH acknowledges support from the NSF IFML 201 9849 and the NSF Al Institute for Foundations of Machine Learning. NB acknowledges the financial support by the Bank of Italy's "G. Mortara" scholarship.
REFERENCES
Panos Achlioptas, Olga Diamanti, Ioannis Mitliagkas, and Leonidas Guibas. Learning representations and generative models for 3d point clouds. In International conference on machine learning. pp- 40-49. PMLR, 2018.
Christoph Aistleitner, Johann Brauchart, and Josef Dick. Point sets on the sphere with small spherical cap discrepancy. Discrete & Computational Geometry, 48(4):990-1024, 2012.
Brandon Amos, Samuel Cohen, Giulia Luise, and levgen Redko. Meta optimal transport. International Conference on Machine Learning, 2023.
Kinjal Basu, Quasi-Monte Carlo Methods in Non-Cubical Spaces. Stanford University, 2016.
Clément Bonet, Nicolas Courty, François Septier, and Lucas Drumetz. Efficient gradient flows in FlieedWasseessee space. Transactions on Machine Learning Research, 2022.
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and Radon Wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 1(51):22-455 2015.
Johann Brauchart, E Saff, Sloan, and R Womersley. Qme designs: optimal order quasi monte carlo integration schemes on the sphere. Mathematics of computation, 83(220):2821-2888 2014.
Johann S Brauchart and Josef Dick. Quasi-mont carlo rules for numerical integration over the unit sphere. Numerische Mathematik, 121(3):43-550, 2012.
Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rich 3d model repository. arXiv preprint 112.0003, 2015.
Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution optimal transportation for domain adaptation. In Advances in Neural Information Processing Systems, pp. 3730-3739, 2017.
Roy Cranley and Thomas NL Patterson. Randomization of number theoretic methods for multiple integration. SIAM Journal on Numerical Analysis, 13(6):904-914, 1976.
Henri Faure. Discrépance de suites associées un système de numération (en dimension s). Acta arithmetica, 41(4)3337-351, 1982.
Jean Feydy, Benjamin Charlier, François-XX Fravvors-Xavier Xavier Vialard, and Gabriel Peyré. Optimal transport for diffeomorphic registration. In Medical Image Computing and Computer Assisted Intervention- MICCAI 2017: 20th International Conference, Quebec City, QC, Canada, September 11-13, 2017, Proceedings, Part I 20, pp. 291-299. Springer, 2017.
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021. URL httthttp::/// http:///wwrrrp/app//////////////
html
M Götz. On the distribution of weighted extremal points on a surface in. Potential Analysis, 13(4): 345-359, 2000.
10

---

Published as a conference paper at ICLR 2024
J Halton and G Smith. Radical inverse quasi-random point sequence, algorithm 247. Commun. ACM, 7(12):701, 1964.
John Hammersley. Monte carlo methods. Springer Science & Business Media, 2013.
Doug P Hardin, TJ Michaels, and Edward B Saff. A comparison of popular point configurations on S arXiv preprint arXiv:1607.04590 2016.
Holger Heitsch and René Henrion. An enumerative formula for the spherical cap discrepancy. Journal of Computational and Applied Mathematics, 390: 13409, 2021.
Edmund Hlawka. Funktionen von beschränkter variatiou in der theorie der gleichverteilung, Annali di Matematica Pura ed Applicata, 54(1):325-333) 1961.
Nhat Ho, XuanLong Nguyen, Mikhail Yurochkin, Hung Hai Bui, Viet Huynh, and Dinh Phung. Multilevel clustering via Wasserstein means. In International Conference Machine Learning. pp. 1501-1509, 2017.
Tianxin Huang, Zhonggan Ding, Jiangning Zhang, Ying Tai, Zhenyu Zhang, Mingang Chen, Chengjie Wang, and Yong Liu. Learning to measure the point cloud reconstruction loss in representation space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12208- 12217, 2023.
Stephen Joe and Frances Y Kuo. Remark on algorithm 659: Implementing Sobol's quasirandom sequence generator. ACM Transactions Mathematical Software (TOMS), 29(1):49-57, 2003.
Alexander Keller. A quasi-monte carlo algorithm for the global illumination problem in the radiosity setting. In Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing: Proceedings of conference at the University of Nevada, Las Vegas, Nevada, USA, June 23-25, 1994, pp- 251. Springer, 1995.
Hyeongju Kim, Hyeonseung Lee, Woo Hyun Kang, Joun Yeop Lee, and Nam Soo Kim. Softflow: Probabilistic framework for normalizing flow on manifolds. Advances Neural Information Processing Systems, 1611688866397,,, 2020.
JF Koksma. Een algemeene stelling uit de theorie der gelijkmatige verdeeling modulo 1. Mathematica B (Zutphen), 11(7-11):43, 1942.
Soheil Kolouri, Gustavo K Rohde, and Heiko Hoffmann. Sliced Was Wasserstein distance for learning Gaussian mixture models. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 3427-3436, 2018.
Rongjie Lai and Hongkai Zhao. Multiscale nonrigid point cloud registration using rotation-invariant sliced- Wasserstein distance via laplace- beltrami eigenmap. SIAM Journal on Imaging Sciences, 10(2):449 483, 2017.
Thanh Tung Le, Khai Nguyen, shanlin sun, Kun Han, Nhat Ho, and Xiaohui Xie. Diffeomorphic mesh deformation via efficient optimal transport for cortical surface reconstruction. The Twelfth International Conference Learning Representations, 2024a.
Tung Le, Khai Nguyen, Shanlin Sun, Nhat Ho, and Xiaohui Xie. Integrating efficient optimal transport and functional maps for unsupervised shape correspondence learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2024b.
Chen-Yr Yu Lee, Tanmay Batra, Mohammad Haris Baig, and Daniel Ulbricht. Sliced Wasserstein discrepancy for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. (0285-10295 2019.
Tao Li, Cheng Meng, Jun Yu, and Hongteng Xu. Hilbert curve projection distance for distribution comparison. arXiv preprint arXXv:2205..5055 2022.
Han Lin, Haoxian Chen, Krzysztof M Choromanski, Tianyi Zhang, and Clement Laroche. Demysti- fying orthogonal monte carlo and beyond. Advances in Neural Information Processing Systems, 33:8030-8041 2020.
11

---

Published as a conference paper at ICLR 2024
Pertti Mattila. Geometry of sets and measures in Euclidean spaces: fractals and rectifiability. Number 44. Cambridge university press, 1999.
Robb J Muirhead. Aspects of multivariate statistical theory. John Wiley & Sons, 2009.
Kimia Nadjahi, Alain Durmus, Lénaic Chizat, Soheil Kolouri, Shahin Shahrampour, and Umut Simsekli. Statistical and topological properties of sliced probability divergences. Advances in Neural Information Processing Systems, 33:20802-20812 2020.
Khai Nguyen and Nhat Ho. Energy- based sliced Wasserstein distance. Advances in Neural Informa- lion Processing Systems, 2023.
Khai Nguyen and Nhat Ho. Sliced Wasserstein estimation with control variates. In The Twelfth International Conference on Learning Representations, 2024.
Khai Nguyen, Nhat Ho, Tung Pham, and Hung Bui. Distributional sliced- Biiced-Wasseee Wasserstein and applications to generative modeling. International Conference on Learning Representations, 2021.
Khai Nguyen, Dang Nguyen, and Nhat Ho. Self-attention amortized distributional projection opti- mization for sliced Wasserstein point-cloud reconstruction. Proceedings of the 40th International Conference on Machine Learning, 2023.
Khai Nguyen, Shujian Zhang, Tam Le, and Nhat Ho. Sliced Wasserstein with random-path projecting directions. arXiv preprint arXiv:2401.15888 2024.
Harald Niederreiter. Random number generation and quasi-Monte Carlo methods. SIAM, 1992.
Art B Owen. Randomly permuted (t, m, s)-nets and (t, s)-sequences. In Monte Carlo and Quasi- Monte Carlo Methods in Scientific Computing: Proceedings of a conference the University of Nevada, Las Vegas, Nevada, USA, June 23-25, 1994, pp. 299-317. Springer, 1995.
Art B Owen. Monte carlo theory, methods and examples. 2013.
Lois Paulin, Nicolas Bonneel, David Cocurjolly, Jean-Claude lchl, Antoine Webanck, Mathieu Desbrun, and Victor Ostromoukhov. Sliced optimal transport sampling, ACM Trans. Graph., 39 (4):99, 2020.
Gabriel Peyré and Marco Cuturi. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(5-6):355-60) 2019.
Gabriel Peyré and Marco Cuturi. Computational optimal transport, 2020.
Charles Qi, Hao Su, Kaichun Mo, and Leonidas Guibas. Pointnet: Deep learning on point sets for 3d classification and segmentation. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 652-660, 2017.
Exguenii A Rakhmanov, Edward B Saff, and YM1306011 1 Zhou. Minimal discrete energy on the sphere. Mathematical Research Letters, 166)6647-66, 1994.
Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving GANs using optimal transport. International Conference on Learning Representations, 2018.
Zhengyang Shen, Jean Feydy, Peirong Liu, Ariel H Curiale, Ruben San Jose Estepar, Raul San Jose Estepar, and Mare Niethammer. Accurate point cloud registration with robust optimal transport. Advances in Neural Information Processing Systems, 34:5373-5389, 2021.
I Sobol. The distribution of points in cube and the accurate evaluation of integrals (in russian) zh. Vychisl. Mat. i Mater. Phys, 7:784-802, 1967.
Eloi Tanguy. Convergence of sgd for training neural networks with sliced Wasserstein losses. arXiv preprint arXiv:2307.11714 2023.
Cédric Villani. Optimal transport: Old and New. Springer, 2008
12

---

Published as a conference paper at ICLR 2024
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912-1920, 2015.
Mingxuan Yi and Song Liu. Sliced Wasserstein variational inference. In Fourth Symposium on Advances in Approximate Bayesian Inference, 2021.
13

---

Published as a conference paper at ICLR 2024
Supplement to "Quasi-Monte Carlo for 3D Sliced Wasserstein"
We first provide proofs for theoretical results in the main text in Appendix A Next, we offer additional background information, including the Wasserstein distance, and computational algorithms for SW, QSW, and ROSW variants in Appendix B We then discuss related work in Appendix [ Afterward, present detailed experimental results, which mentioned in the main text for point-cloud interpolation, image style transfer, and deep point-cloud autoencoders in Appendix Finally, we report on the computational infrastructure Appendix B
A PROOFS
A.1 PROOF OF PROPOSITION
We first discuss the asymptotic uniformity of the mentioned QMC point set.
For the Gaussian-based mapping construction, From the construction, we have the function 0
+ (z)
f(x) = o [=)]l Given a Sobol sequence 21,...; IL, the corresponding spherical vectors are
......, Or with 8 = f() for all = 1..... L. Let X ~ Et= 62z- From the low-discrepancy
sequence property of Sobol sequences (Sobol 1967).
have that X converges X 2(00 1) in distribution as L + oc. Since our function [(x) is continuous on [0. 1] using the continuous
mapping theorem, we have that 02 = f(X,) converges to f(X) U1(S-11) in distribution as L + co. For the equal area mapping construction, we refer the reader to Aistleitner et al. (2012) for the proof of uniformity. For the generalized spiral points construction, we refer the reader Hardin et al. (2016) for the proof of uniformity of this construction. Minimizing Coulomb energy is proven to create an asymptotic uniform sequence in Götz (2000).
Now denote " = ELe 56, and 8 ~ U((d-)) )). Given an asymptotically uniform point set have 7/2 3 1) as - co, where S denotes weak convergence of probability
. OL. measures. That is, Eg-yy [0)] + Eg- [()) for all bounded continuous functions g. Thus, by the definition of the SW distance and its QSW approximation, one is left to show that 0 + WT 0iv) is bounded and continuous for any two measures with finite pd moment. We show these properties for (6ttu, 0tv) and then invoke continuity of the real function r> ////
As for boundedness,
the Cauchy- Sehwar-S inequality on Rd to get
W W, 0tv) = [ 10T x -Tyi (dxx, dy)
( inf <ETI(U..))
1/P
1/p
inf xETI(U.))) / vi1-yllp=dxs, dy)
Wp((, v) < 00 for all 0 E gd-1, As for continuity, let (0z)a21 be sequence on 8d-1 converging to 0 E Then [pp(ttun 0.trv= (e 0tv) S Wp(Ottp, 0.gv) (etju 0.tt))
Then
( 0,t0)) (pt(n, 0tv)l
< (0 0,4/4) + (,
where the last inequality is straightforward consequence of the triangle inequality applied to the metric Wp. Let X E {n.D) Then, using again the
inequality, we obtain
( inf (ETTI(A))) (D4A 0c4A)
/ 110T T dy)
1/r
1/p
10, x -Txpp x
1/8
[1=))(\(dz))
110:
A|| +
as 00.
<000
14

---

Published as a conference paper at ICLR 2024
This implies Wp(Ottt,,0tt)) (p((H,,00)) as t - co, proving continuity.
A.2 PROOF OF PROPOSITION
For the Gaussian-based mapping construction, given a Sobol sequence 21,-.., E [0, 11 ap- plying scrambling returns s',,...,'/ ((0, 1]d) Owen 1995). Since f(x) - is the normalized inverse Gaussian CDF, 03 [(x() ~ (S" for all 1....,, I.
: x
For the random rotation construction, given a fixed vector 0 E gd-1 and U (u1 ........ Ua) )(Va(R")), we now prove that UG ~ (((-11). For any U1 E Va(R"). we have UL = U2 with U2 ~ ((Va(R Therefore, only one distribution on gd-1 is invariant to rotation (Theorem 3.7 in (Mattila 1999)) which the uniform distribution, UO (((3-1). Therefore, obtain that .,,..., ',, generated by uniform random rotation of a point set 01..... lr, are uniformly distributed.
have that UO has the same distribution U U.. Since there is
Now, given Ui.....0K 02 U($=11), have
EIROSW (l..,,
;0,)0 E
T.
(W
T
(W = SW,(,,))
L
which completes the proof.
B ADDITIONAL BACKGROUND
Wasserstein distance. Given probability measures J Pp (R.)) and E Pp (RR). and p 2 the Wasserstein distance (Villani 2008 Peyré & Cuturi 2019) between μ and v/ is
1/p
inf W Wp(,,)) xxll((n.)) Rd
|| yllpdT((,,
where 11( v) is the set of all couplings whose marginals μ and Considering the discrete case, namely, μ Ei= asd,, and v = -Ø= B308, with
E as = En= Bj. one obtains:
min (
Tyl k
V.I...
(8)
1=1 ==1
where II( {nt RTX"
a, = 3). Using linear programming, the computational complexity and memory complexity of the Wasserstein distance are On logn) and O(²?).
Algorithms. We first introduce the computational algorithm for Monte Carlo estimation of SW in Algorithm I Next, we provide the algorithm for QMC approximation of SW in Algorithm Finally, we present the algorithms for Randomized QMC estimation of the SW distance with scrambling and random rotation in Algorithms and 4 respectively.
Generation of Sobol sequence. From (oee & Kuo, 2003), for generating a Sobol point set II....,21, Lt. [0, 1]d, we need to follow the following procedure. For the j-th point, we need to choose a primitive polynomial of some degree 81 in the field Z, (set of integer of module 2), that is:
2 01 8- + + ag -1 +
where the coefficients ai.j. Og lo are either 1. then use ai.j...., Us, 1.j to define sequence mijj m2.jj ... Mayy such that:
maj = ma + 2 22 mx .... .... 2 a. - 1.y- + 2 m + Mk-eyd
15

---

Published as a conference paper at ICLR 2024
Algorithm 1 Monte Carlo estimation of the Sliced Wasserstein distance.
Input: Probability measures and v, 1, and the number of projections L.
Set SW (1, vı; L)
SW,,,,
/ to L do
Sample ~ ((8-11)
Compute SW L1 Et= (Fodu()) (=)
(z)
end for Return: SW L,
Algorithm 2 Quasi-Monte Carlo approximation of the sliced Wasserstein distance.
Input: Probability measures y and v, p 1, QMC point set 0I,... 0r gd-
Set QSW (M. w; 01, r,........0.. OL) =
for / to L do
Compute QSW
p (1,, v; ,,.,,,0,1. 0r.) (w, 0r))+ + So Fo ( (x)
end for Return: QSW QSW (u, v; 01.0.......
Algorithm Randomized Quasi-Monte Carlo estimation of the Sliced Wasserstein distance with scrambling.
Input: Probability measures f and v, p > 1, QMC point set Ti,..., JL E [0, 1|". Scramble 21, Zr to obtain ui....,
Compute . 8% = f( f(a/)) for f the Gaussian bassed mapping or the equal area mapping.
Set ROSW (n. v; 07 ...., =0
=0
for 1 L do Compute RQSW (H, v: .r....,07
ROSW (H, 1. So FFotu (2)
Fo: (2) end for Return: ROSW ROSW Wh; 01)
Algorithm The Randomized Quasi-Monte Carlo estimation of sliced Wasserstein distance with random rotation.
Input: Probability measures y and v, p.p 1, QMC point set 0,,..., Sd-1 Sample U ~ (((V((R))
Compute 0g ..,..... Oz UO,,...,,0, U0,
Set RQSW (1, v; 01 ... 02) -0
for 1 = do Compute RQSW" (1, uz ./,....0')) (7)
I IF (z)
end for Return: RQSW (
for k > + and 2 is the bit-by-bit exclusive-OR operator. The initial values of Mi1j m2.11 May.j are chosen freely such that maj. < & < sy is odd and less than 2* After that, direction numbers Vi U2. Uaja are defined as:
Uk.j = ma.j
2
Finally, we have:
Fiij biUi. 62U2,5 1 ..., @b,, Veydi
16

---

Published as a conference paper at ICLR 2024
where b, is the i-th bit from the right when is written in binary .ie. (... byb1) is the binary representation of For greater detail, we refer the reader to (Joe & Kuo 2003) for more detailed and practical algorithms.
Confidence Intervals. Using the discussed methodology, one can obtain M i.d ROSW estimates,
i.., RQSW" (1, vz; -imm- Im) for m 1,..., M. Since ROSW is unbiased estimate of the population SW, the central limit theorem ensures the following:
AM - -SW SWE(um)) v) 4 10,
8M/v
as M + co, where far and åM are the sample mean and standard deviation based on the generated M-size sample. Therefore, 1 a size asymptotic confidence interval for SW v) is readily obtained as
PM 1 20/28 /VM.
with Ex/2 denoting the a/2 quantile of standard normal random variable. Alternatively, by sampling with replacement from the M generated RQSW estimates, fav. say Pas for b = ,,...,,, B, and construct a a bootstrap confidence interval for SW v) as
obtain B bootstrap replications of [a/22 , a1 -2/a/2, where iu denotes the w sample quantile of {p (b)
= 1, I,..., B}.
C RELATED WORKS
Beyond the uniform slicing distribution. Recent works have explored non-uniform slicing distri- butions (Nguyen et al.) 2021 Nguyen & Ho. Ho| 2023). Nevertheless, the uniform distribution remains foundational in constructing the pushforward slicing distribution (Nguyen et al.] (021) and the proposal distribution (Nguyen & Ho 2023). Consequently, Quasi-Monte Carlo methods can also enhance the approximation the unitorm distribution.
Beyond 3D. It is worth noting that the Gaussian-based construction, maximizing distance, and minimizing Coulomb energy can be applied directly in higher dimensions, i.e., d > Similarly, their randomized versions could also be used directly in higher dimensions, However, the quality of QMC point sets in high dimensions and their approximation errors are still open questions and require detailed investigation. Therefore, we will leave this exploration to future work
Scaled Mapping. Quasi-Monte Carlo briefly used for SW in (Lin al.] 2020). In particular, the authors utilize the Halton sequence in the three-dimensional unit cube, then map them to the unit sphere via the scaled mapping (xx) = T l However, this construction is heuristic and lacks meaningful properties. We visualize point sets of sizes 10, 50, 100 in Figure 5 From the figure, is evident that this construction does not exhibit iow-discrepancy behavior, as all points are concentrated in one region of the sphere.
Near Orthogonal Monte Carlo. Motivated by orthogonal Monte Carlo, the authors in (Lin et al. 2020) propose near-orthogonal Monte Carlo, aiming to make the angles between any two samples close to orthogonal. We utilized the published code for optimization-basee approaches available at https://gi thub.. com/ HL- han in. A to generate point sets of size L in three dimensions, where L. chosen from the set 10, 50, 100. For our experiments, we generated only one batch of L points, avoiding the need to specify the second hyperparameter related to the number of batches. We visualize the resulting point sets and their corresponding spherical cap discrepancies in Figure 5 From the figure, it is evident that NOMC yields better spherical cap discrepancies compared to conventional Monte Carlo methods. However, it is important to note that NOMC does not achieve the same level of performance the QMC point sets discuss in this work. In this study, primary focus is on QMC methods, and as such, we leave a detailed investigation of the application of OMC methods for SW future research.
17

---

Published as a conference paper at ICLR 2024
Scaled Mapping with Sequence
Orthogonal
L- 0G 0..330
1-10.. 0
52, 02 0.0002
50.00
-5-
1.02
0.50
0.25
025
0.50
0.75
0.75
-1.03
1.0
68.7 25 b3.3
0,25
0.25
0.25
-2.25
0.75
-0.7
Figure 5: Optimization- based Orthogonal Monte Carlo point set and scaled mapping with Halton Sequence
point set.
Random
Couedarrhaeeed Hagoing
Equa Yenn Mapping
10.0 1272
1- oj
53.0 0.2
30.00 83325
56 D
1,00
1.0
1.0
-535
-44 18 2.
Sp
Nacmiang Ditance
Mitlmaing Coudorb Energy
O C0020
DJ
335
835
606
10
15
Figure 6: point sets on ? with the size of 10, 50, 100 and the corresponding spherical cap discrepancies.
Ro Random
Gausilan baved Masping
Equal Area Mapsing
840
Ganera leed Spina
Necmmtin Datance
Mini Misimiann Couromb Energy
L-2 Visgi1
0.951 29, Togll
0210h
0.5
0.1
Figure Spherical cap discrepancies of different QMC point sets random point set.
18

---

Published as a conference paper at ICLR 2024
Table 3: Summary Wasserstein-2 -2 distances (multiplied by 10") from three different runs.
Estimators
Step 100 (W2 L)
Step (W,
Step
4)
Stop 400/W, 4)
Step 500 (W,
Time (sL)
SW L=10
5.821
0.149
0.203 1 0.012
0.038 1. 0.002
0.017 1 0.001
0.009 1 0.0
2.90
GQSW L=10
9.274
3.776 = 0.0
2.572
2:297 0.0
2.23
2.09
FQSW 10
4.066 0.0
0.576 + 0.0
0.511 + 0.0
0.508 + 0.0
0.508 + 0.0
2.70
SQSW L=10
6.321 0.0
1,083 0.0
0.603
0.539 0.0
0.564 0:64+000
2.68
DOSW 1=10
5.919++00 0.0
0.87 0.0
0.807 0.0
0.593 + 0.0
0.593 + 0.0
2.69
CQSW
5.561
0.793 0.0
0.614
0.606
RGQSW L=10
5,863 = 0.029
0.188 + 0.007
0.035 + 0.002
0.018 + 0.001
0.01 0.001
3.23
RRGOSW L=10
5.781 0.102
0.232 0.031
0.017 0.002
0.03 = 0.002
0.026 0.001
3.02
REQS W L=10
6.733 + 0.19
0.19 0.014
0.034 + 0.003
0.016 0.002
0.008 + 0.002
3.12
RREQSW
5.857 0.058
0.219 0.007
0.001
0.022 0.001
0.014 0.001
RSQSW L=10
5.764
0.028
0.196 + 0.004
0.035 0.002
0.016 + 0.002
0.007 + 0.001
3.00
RDQSW 1--10
0.071 5.835
0.202 0.011
0.036 0.002
0.016 0.001
0.008 0.001
ROQSW L=10
5.794 0.076
0.196 1 0.008
0.037 0.003
0.017 1. 0.002
0.008 1 0.001
3.02
D DETAILED EXPERIMENTS
D.I SPHERICAL CAP DISCREPANCY
We plotted the spherical cap discrepancies of the discussed QMC point sets and added hypothetical lines of CT,-3/1 /Tog(T, I.) for C = 1.6, C= = 1, 0.95 in Figure From the figure, it is evident that QMC point sets derived from generalized spiral points, maximizing distance, and minimizing Coulomb energy exhibit faster convergence rate than (L-33/4 (Vll=///Vlo(())) /log(L)). Consequently, they can be classified low-discrepancy sequences. Regarding the equal-area mapping construction, demonstrates approximately the same convergence rate as O(L 3/4 1144Vlogg LL),(L)), suggesting its potential as a low-discrepancy sequence. However, Gaussian- based mapping QMC point sets and random (MC) point sets do not exhibit low-discrepancy behavior. using generalized spiral points, maximizing distance, and minimizing Coulomb energy point sets for approximating SW when distance values are a critical factor in the application.
summary, we recommend
D.2 POINT-CLOUD INTERPOLATION
Approximate Euler methods. We want to iterate through the curve Z() -nV z(e) [SW2 (tZ P.)]. For each iteration with 1...., T, we first construct point set ....... 0, based on the discussed approaches using MC, QMC methods, and randomized QMC methods. After that, with step size v) 0, we update:
L Σ
1/2
z(t)= = Z(t 1) n V 1(t-1)
w3 (01P2(0-1)001111)
Visualization for l= 100. In addition to the partial visualization in the main text, we provide a full visualization of point-cloud interpolation from all QSW and RQSW variants in Figure We observe that QSW variants cannot produce smooth point clouds at the final time step since they use the same QMC point sets across all time steps. In contrast, ROSW variants expedite the process of achieving a smooth point cloud that closely resembles the target. When compared to RQSW variants, the point cloud at the final time step from SW (the conventional MC) still contains some points that deviate significantly from the main shape.
Results for L 10. We repeated the same experiments with L 10. We have reported the Wasserstein-2 distances for intermediate point-clouds (relative to the target point-cloud) in Table 3 We observed a similar phenomenon as with I, = 100, namely, RQSW outperforms QSW significantly and also performs better than SW. Compared to L = 100, all approximations from L 10 yield higher Wasserstein-2 distances. However, the gaps between QSW variants are wider. Therefore, ROSW variants more robust to the choice of L than QSW.
Results for a different pair of point-clouds, We conduct the same experiments with a different pair of point-clouds, namely, 2 and 3 in Figure I We present summary of Wasserstein-2 distances in Table for L = 100 and Table for L = Io. We observe the same phenomena as in the previous experiments. Firstly, RQSW variants produce shorter curves than QSW variants. Secondly, larger
19

---

Published as a conference paper at ICLR 2024
SW
GQSW
RGQSW
RRGQSW
EQSW
REQSW
RREQSW
SQSW
RSQSW
DQSW
RDQSW
COSW
RCQSW
Figure 8: Point-cloud interpolation from SW, QSW variants, ROSW variants with 100.
20

---

Published as a conference paper at ICLR 2024
Table 4: Summary Wasserstein-2 distances (multiplied by 10") from three different runs.
Estimators
Step 100 (W2 4)
Step 200 (W2 4)
Step 300 (W2 4)
Step 400(W2 4)
Step 500 (W2 4)
SW L=100
2.819 + 0.044
0.23 = 0.002
0,033 = 0.002
0,012 = 0.002
0.006 = 0.001
GQSW 1=100
2,868 +: 0.0
0.281 = 0.0
0.107 + 0.0
0.093 10933:00 0.0
0.091 0.0
FOSW 1=100
2.473 0.0 0.0
0.229 0.0
0.109 + 0.0
0.1
0.098 0.0
SQSW L=100
2.841
0,262
0,109:::
0.098
0.096 0.0
DQSW L=100
0.0
0.262
0.101
0.0
0.091
CQSW L=100
2.696
0.0
1.00
0.0
0.084 0.0
RGQSW L=100
0.017
0.231 0.005
0.031
0.1
0.004 0.001
RRGQSW L=100
2.82
0.233 0.008
0.034
0.013
0.006 0.002
REQSW L=100
2.826
0.220 0.002
0.03 + 0.001
0,01 = 0.0
0.004 0.0
RREQSW L=100
0.015
0.002
0.031 = 0.001
0.011
0.005 = 0.001
RSQSW L=100
0.003
0,224 0.001
0.028 0.002
0.008 0.001
0.003 0.0
RDQSW L=100
2.793 0.002
0.224 0.001
0.028 0.001
0.008 0.001
0.002 0.0
RCQSW L=100
2.794 0.005
0.227 0.002
0.03 0.001
0.01 0.002
0.005 0.002
Table 5: Summary Wasserstein distances (multiplicd by 102) from three different runs.
Estimators
Step 100 (W2 ()
Step 200 (W2 4)
Step 300 (W: L)
Step 400 L)
Step 500 (W2 4)
SW I=10
2.919 0.082
0.262 + 0.018
0.048 + 0.007
0.02 + 0.004
0.01 + 0.003
GQSW L=10
6.576 0.0
2.863 1 0.0
2.305 1 0.0
2.197 1 0.0
2.165 1. 0.0
EOSW L=10
2.391 0.0
0.789 + 0.0
0.617 0.0
0.783 + 0.6 0.0
0.776 0.6
SQSW 1=10
3.498
1.437
0.87 0.0
DQSW L=10
2.9
0.0
0.796
0.754
0.0
CQSW L=10
0.0
1.56
1.199
1.035 = 0.0
1.027
RGQSW L=10
2.979 + 0.048
0.266 + 0.007
0.045 + 0.002
0.019 0.001
0.009 0.001
RRGQSW L=10
2.928=0.055
0.271
0.051 0.003
0.028 0.002
0.022 0.001
REQSW 1=10
2.891 0.089
0.25
0.045 0.002
0.02 + 0.001
0.01 + 0.001
RRFQSW T=10
2.907 2.907+0.103
0.268+
0.055 + 0.003
0.027 - 0.002
0.017 0.001
RSQSW L=10
0.006
0.040
0.0
0.001
0.01 + 0.002
RDQSW L=10
2.769
0.239 0.008
0.044 + 0.004
0.019 0.004
0.009 0.002
RCQSW 1=10
2.761 + 0.101
0.241 + 0.009
0.043 + 0.0
0.018 0.002
0.009 0.001
number of projections is better, and RQSW variants are more robust to changes in than QSW variants. Additionally, we provide visualizations for Z. = 100 in Figure From the figure, we can see consistent qualitative comparisons with the Wasserstein-2 distances reported in the tables.
Recommended variants. Overall, we recommend RSQSW, RDQSW, and RCQSW for the point- cloud interpolation application since they give consistent performance for = 100 and 10 for both tried pairs of point-clouds.
D.3 IMAGE STYLE TRANSFER
Detailed settings. We first reduce the number of colors in the images to 3000 using K-means clustering. Similar to the point-cloud interpolation, we iterate through the curve between the empirical distribution of colors in the source image and the empirical distribution of colors in the target image using the approximate Euler method.
Full results for L = 100. We present style-transferred images and their corresponding Wasserstein-2 distances the target image in of color palettes the last iteration (1000) in Figure To From the figure, it is evident that QSW variants facilitate faster color transfer compared to SW. To elaborate, SW exhibits Wasserstein-2 distance of 458.29, while the highest Wasserstein-2 distance among QSW variants is 158.6, achieved by GQSW. The use of RQSW can further enhance quality; for instance, the highest Wasserstein-2 distance among RQSW variants is 1.45, achieved by RGQSW. The berf-perf variant in this application is RSQSW; however, other ROSW variants are also comparable.
Full results for L - 10. We repeat the experiment with L 10. In all approximations. decreasing L to 10 results in a higher Wasserstein-2 distance, which is understandable based on the approximation error analysis. In this scenario, the performance of some QSW variants (GQSW, EBQSW, SQSW) degrades to the point of being even worse than SW. In contrast, the degradation RQSW variants is negligible, particularly for RCQSW.
21

---

Published as a conference paper at ICLR 2024
SW
GOSW
RGQSW
RRGQSW
EQSW
REQSW
RREQSW
SQSW
RSQSW
DQSW
RDQSW
CQSw
RCQSW
Figure 9: Point-cloud interpolation from SW, QSW variants, RQSW variants with 100.
22

---

Published as a conference paper at ICLR 2024
Source
SW. 45.629
GOSNN, Ws 158.6
RGGSW,
RRGODWW,
EQSW, 41
REQSH W,
KREGSN
S06W,
ASOSW, W,
DONK, 66.
RDOSW, R4 1.04
COSN, W. 148
REgEN N2 - 127
target
Figure 10: Style-transferred images from SW, QSW variants, and ROSW variants with L = 100.
ERSW. Wy 640.17
RECSW. W; 1.99
RREOSW, W2 1.99
SOSW. W) 920.19
RS0EW. W) 2.34
BQSW, N₁.
COSW. W. 432.8
RCOSW W
Target
Figure 11: Style-transferred images from SW, QSW variants, and RQSW variants with L 100.
Recommended variants. Overall, we recommend RCQSW for this application since it performs consistently for both setting of L 100 and L 10.
D.4 DEEP POINT-CLOUD AUTOENCODER
Full visualization for I, = 100. We first visualize reconstructed point-clouds from all approximations, including SW, QSW variants, and RQSW variants in Figure Overall, observe that the sharpness of the reconstructed point-clouds aligns with the reconstruction losses presented in Table 2 However, the point-clouds generated by GQSW lack meaningful structure, likely due to numerical issues encountered during training. These issues may stem from the numerical computation of the inverse CDF for specific projecting directions at certain iterations. Randomized versions GQSW could potentially mitigate such problems, as stochastic gradient training may help avoid undesirable configurations in neural networks.
Results for L 10. We reduce the number of projections L to 10 and subsequently report the reconstruction losses Table 6 Similar to other applications, reducing results increased reconstruction losses, particularly for QSW variants. In this specific application, RQSW variants demonstrate their robustness to the choice of L; the reconstruction losses for 10 are comparable to those for L 100, shown in Table 2 Additionally, we provide visualizations of the reconstructed point-clouds for = 10 in Figure [3 It is evident from the figure that reconstructed point-clouds from QSW variants exhibit significant noise.
23

---

Published as a conference paper at ICLR 2024
Data
GOSW
RGQSW
RRGQSW
EOSW
REQSW
RREQSW
SQSW
RSQSW
DQSW
RDQSW
CQSW
RCQSW
Figure 12: Some reconstructed point-clouds from SW, QSW variants, and RQSW variants with L 100.
24

---

Published as a conference paper at ICLR 2024
Data
GOSW
RGQSW
RRGQSW
EQSW
REQSW
RREQSW
SQSW
RSQSW
DQSW
RDQSW
CQSW
RCQSW
Figure 13: Some reconstructed point-clouds from SW, QSW variants, and ROSW variants with L = 10.
25

---

Published as a conference paper at ICLR 2024
Table 6: Reconstruction errors (multiplied by 100) from three different runs of autoencoders trained by different
approximations of SW with L=10.
Epoch
Epoch
Epoch 400
Distance
SW2()
W2())
2W2 (4)
Wx(1)
SW2 (J)
W2(1)
SW T=10
2.27 0.05
10.60
0.10
2.12
0.04
9.93 +: 0.02
1.95 + 0.06
9.24 0.09
GQSW L=10
11.18 + 0.06
32.64 = 0.06
11.78 + 0.07
33.35 + 0.07
14.85 + 0.03
38.04 = 0.04
FQSW 1=10
2.53 0.07
11.82 0.12
2.29
0.02
11.03 + 0.05
2.11 + 0.08
10.40 0.03
SQSW L=10
2.46 0.04
11.50 0.07
2.23 0.05
10.82 =
2.05 = 0.06
10.15
DOSW L=10
3.10
12.89 0.04
2.86
12.17 0.10
2.50
11.33
CQSW 1.=10
2.60 0.04
11.92 0.02
2.44 0.03
11.29 0.07
2.25 + 0.10
10.59 0.13
RGQSW L=10
2.27
10.00
0.00
9.92
1,95
9.20
RRGQSW I=
2.26 0.02
10.58 0.03
2.06 0.008
9.85
1.89 0.06
9.18 0.07
RFQSW 10
2.26 + 0.06
10.57 + 0.05
2.09 2.09+0.00 0.05
9.91 9
1.91 + 0.01
9.20 0.03
RREQSW L=10
0.04
1.06
2.06
0.04
1.8 0.07
9.17
RSQSW L=10
2.23
1.05
0.03
9.83
1.86 0.03
9.04
RDQSW 1=10
2.24
10.54
0.03
9.85
1.87
9.14+
RCQSW L=10
2.24 0.04
10.55
0.03
9.83
1.7
9.13 0.06
Recommended variants. Overall, we recommend RCQSW for this application since it performs well in both settings of 100 and I. 10 terms of both reconstruction losses and qualitative comparison.
E COMPUTATIONAL INFRASTRUCTURE
We use single NVIDIA V100 GPU to conduct experiments training deep point-cloud autoencoder. Other applications are done on desktop with an Intel core CPU chip.
26


Reviews:
[{"review_id": "0RKOmHQCMP", "reviewer": "Reviewer_QEcr", "summary": "Sliced Wasserstein distance is a commonly used measure of distance between probability measures, whose evaluation involves a usually intractable integral term. Standard evaluation of the integral term is based on Monte Carlo integration, which has an estimation error that depends sub-optimally on the number of samples. This paper fills the hole in literature of computing Sliced Wasserstein distance using Quasi-Monte Carlo methods and Randomized Quasi-Monte Carlo methods. Multiple variants are proposed, and some new ideas for randomization over the sphere are discussed. Adequate experimental results are provided to demonstrate the improvement over Monte Carlo methods.", "questions": "In the numerical experiments, while the reported statistics in the tables typically demonstrate significant improvements, such improvement is hard to see from the visualized figures. What are some observable differences in the figures between SW and QSW (e.g. CQSW)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and mostly clear.\n2. Adequate background and literature review are provided.\n3. The visualizations are very nice.\n4. Lots of numerical experiments are conducted and many of them are realistic data examples.", "weaknesses": "1. The paper is mostly a combination of existing methods, which lacks certain novelty. However, this paper is a helpful reference for people that needs to numerically compute Sliced Wasserstein distance, so it seems worth publishing in ICLR or somewhere similar.\n2. The randomized QMC method for Sliced Wasserstein distance is motivated by stochastic optimization, but it could also be used to obtain confidence intervals on the estimates. This is probably worth discussing, both in theory and with applications.", "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": "", "extra_scores": {}}, {"review_id": "G0lhHKCivP", "reviewer": "Reviewer_Re8P", "summary": "The paper proposes novel quasi-Monte Carlo (QMC) method for sliced Wasserstein distance (SW), which utilizes various QMC point sets to approximate the integration over uniform distribution on the unit sphere that arises from SW. Specifically, the paper investigates the construction of point sets that approximate the uniform distribution on unit sphere, aiming to obtain lower absolute error, compared to naive MC estimator of SW. Furthermore the paper provides methods to randomize the constructed point sets to obtain unbiasedness, in addition to consistency. Lastly the paper provides empirical study of the error of the proposed estimator, and applications of QMC SW that suggests better performance.", "questions": "Please see above (section Weaknesses) for details. Some more questions:\n1. The paper used term 'low-discrepancy' twice w.r.t. 2 different discrepancies, and with different benchmark rates $O(L^{-1}\\log L ^d)$ and $O(L^{-3/4}\\sqrt{\\log L})$. How are they related? And which is applicable to obtain the overall error bound for the proposed estimator?\n2. Integration over the sphere is a classical numerical analysis problem. Another class of method that seems reasonable is cubature, see [1], with the most notable difference being that the weight is not uniform. Is it possible to use this class of method for estimation of SW? It seems the smoothness requirement for cubature is not any worse than that for QMC in the paper.\n\n[1] Hesse, Kerstin, Ian H. Sloan, and Robert S. Womersley. \"Numerical integration on the sphere.\" Handbook of geomathematics. 2010.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper is overall clear and well presented, and the results are original and novel to the knowledge of the reviewer. The strengths of the paper includes:\n1. The absolute error reduction is a novel perspective, as traditional SW estimators only guarantees consistency and unbiasedness, but a bound for the absolute error is usually missing. This paper sheds new light on the faithfulness of SW estimating beyond MC regime.\n2. The paper provides a thorough investigation of the construction of equally-spaced points on the unit sphere, which is of wider interest as it is in general an open problem on 2 dimensions and beyond. The proposed methods all seem promising, and their incorporation into machine learning tasks seems interesting.\n3. The paper provides extensive experiments, which seem sufficient for justifying the practicality of the proposed estimators.", "weaknesses": "Some weaknesses:\n1. The contributions seem limited, as the paper mainly applies existing QMC methods to SW estimation, whereas little was investigated on how QMC and SW interact. Specifically, the paper claims that the Koksma-Hlawka inequality is the main guarantee of lower absolute error. While all listed QMC methods do achieve low discrepancy, on the SW side it does not seem trivial to claim that the SW integrand satisfies the smoothness assumption for the absolute error bound to hold. For instance, for general $\\mu,\\nu$, the integrand $W_p^p(\\theta\\mu,\\theta\\nu)$ only seems to be Lipschitz in $\\theta$, which does not imply bounded HK variation in higher dimensions [1]. The BV condition should be verified before claiming the applicability of the inequality.\n2. Related to the previous item, when applying the Koksma-Hlawka inequality, the discrepancy was empirical CDF error. It is unclear why the paper then switches to spherical cap discrepancy, and how this is connected to the Koksma-Hlawka inequality. The reviewer agrees that this is a better measurement of the uniformity on sphere, but is not sure about how this directly contributes to bounding the absolute error.\n\n[1] Basu, Kinjal, and Art B. Owen. \"Transformations and Hardy--Krause variation.\" SIAM Journal on Numerical Analysis 54.3 (2016): 1946-1966.", "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": "", "extra_scores": {}}, {"review_id": "Q4lsmxbQ91", "reviewer": "Reviewer_UGxf", "summary": "This work proposes several novel approximations for the calculation of Sliced Wasserstein distance. Prior works relied on Monte Carlo approximation of expectation in calculating SW distance. The authors propose to substitute it with Quasi-MC approximation of expectation which results in lower approximation error. The main idea behind it is to pick a deterministic set of uniformly distributed points (low-discrepancy sequences) instead of sampling them randomly as in standard MC. The authors propose and evaluate four different strategies to obtain these low-discrepancy sequences on the unit hypersphere, all suitable for QMC calculation of SW distance. They prove that QSW converges to SW in the case of infinite integration points.\n\nAdditionally, they propose a randomized version of QSW which they prove to be an unbiased estimator of SW, which allows for unbiased estimation of SW gradients, which leads to improved optimization with RQSW objective.\n\nIn the experiments, the authors: (1) show the reduction of the SW approximation error by computing all the different distance approximations between point clouds sampled on the surfaces of 3D shapes; (2) perform point cloud interpolation and image style transfer by interpolation using the gradients of different approximations; (3) train an autoencoder for point clouds using QSW and RQSW as training objectives. (1) and (2) show considerable improvements compared to the baseline SW estimation with MC. For (3) there are improvements but the results seem not to be statistically significant.", "questions": "Related to W.3, empirically, how efficient in terms of time are all the presented approximations?\n\n---\nPost rebuttal:\nI'd like to thank the reviewers for the additional results and clarifications, most of my concerns were covered. I have increased my rating accordingly.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper is well-written and is easy to follow.\n\n2. The proposed methods for SW distance approximation seem to consistently outperform the regular MC SW distance approximation.\n\n3. The authors present the approach in a mathematically rigorous manner and prove the main results of the paper.", "weaknesses": "1. The improved SW approximation seems not to translate its benefits in large-scale training experiments. It might be worthwhile to recheck that with more powerful auto-encoder architectures, which can better benefit from the improved distance approximation.\n\n2. Figure 1 is not very informative (might be moved to supplementary?), some figures are too small (fig 1, 2), and point clouds in all the figures are too small.\n\n3. There is the complexity analysis of approximations in the paper, but it still will be nice to see a computation time comparison for all the different approximations.", "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": "", "extra_scores": {}}, {"review_id": "hqons39dYU", "reviewer": "Reviewer_8GjU", "summary": "In this paper, it is proposed to approximate the Sliced-Wasserstein distance (SW) using Quasi-Monte Carlo methods instead of the usual Monte-Carlo approximation. Authors discuss and compare several methods to generate a point set with low spherical cap discrepancy in order to generate uniform samples on the sphere. Then, they also propose a randomized version which is useful to obtain a better estimate of the gradient. Finally, they show the usefulness of QMC approximation of SW on different tasks such as comparison of point clouds, point-cloud interpolation, image style transfer or deep point-cloud autoencoders.", "questions": "Why is Proposition 1 not valid for the Maximizing distance version?\n\n\"Since the QSW distance does not require resampling the set of projecting directions at each evaluation time, it is faster to compute than the SW distance if QMC point sets have been constructed in advance\": I guess we could also use the same samples for the evaluation of different SW (even though I agree this is not really in the spirit of the computation of SW).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Finding better estimates of the Sliced-Wasserstein distance is a nice problem which can improve the results in applications using SW. This work discusses and compares many different methods to construct point sets to generate uniform samples on the sphere, which is not something very common to the best of my knowledge. Furthermore, the results of the application demonstrate well the superiority of the differents methods compared to the usual Monte-Carlo estimator of SW.\n\n- Discussion of different construction of point sets with low discrepancy and allowing to generate uniform samples on the sphere\n- Application of these different point sets to approximate SW\n- A randomized version to improve the estimate of the gradient\n- Different applications which show well the benefits of the different point sets to approximate SW", "weaknesses": "- The figures are generally too small which makes them hard to read properly (especially Figure 1 and 2)\n- The experiments are only focused on the case $S^2$, which is already nice, but I believe that some of the methods work for higher dimension and could therefore have been tested.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)