Quasi-Monte Carlo for 3D Sliced Wasserstein

We appreciate the time and feedback from the reviewer. We would like to answer the questions as follows:

Q12: The figures are generally too small which makes them hard to read properly (especially Figure 1 and 2)

A12: Thank you for your comments. We have adjusted the figures to be bigger in the revision.

Q13: The experiments are only focused on the case $\mathbb{S}^2$, which is already nice, but I believe that some of the methods work for higher dimension and could therefore have been tested.

A13: For an integrand that satisfies some smoothness conditions, we only need $L>2^d$ to make QMC better than MC. It means that we only need $L>2^3=8$ in 3 dimensions. Although QMC on the unit-hypersphere does not have such a guarantee, it can be conjectured that QMC is still better than MC in relatively low dimensions with a sufficiently large number of samples. Therefore, we focus our study on 2D sphere only in the paper.

Some constructions of QMC point-sets can be used in higher dimensions such as Gaussian-based mapping, maximizing distance, and minimizing Coulomb energy. However, in high-dimension, we will need a very large number of points to make QMC better than MC. For example, $d=10$, we need $L > 2^{10} = 1024$ to get better performance. We acknowledge that SW can be used in high-dimensional applications such as deep generative modeling, domain adaptation, and so on. However, we conjecture that the current framework of QMC for SW might not show a clear improvement compared to MC as shown in 3D applications. However, we would like to recall that 3D data plays a crucial role in a lot of applications such as autonomous driving, metaverse, and so on.

Q14: Why is Proposition 1 not valid for the Maximizing distance version?

A14: In Proposition 1, we show that SW is a continuous and bounded function on the unit-hypersphere. To get the asymptotic convergence of the QMC estimation of SW, we need the used QMC pointset to be asymptotic uniform i.e., when the number of points goes to infinity, the empirical pdf converges to the pdf of uniform distribution. To the best of our knowledge, the point-set created by maximizing distance has not been shown to be asymptotically uniformly distributed. Since this is a problem of numerical analysis, we will leave a careful investigation to future works.

Q15: "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).

A15: Thank you for your insightful comment. We can use a fixed Monte Carlo sample for SW at multiple evaluation times. However, it is equivalent to QMC with a not-good sequence in terms of uniformity as demonstrated in Figure 1 (Figure 5 in the revision). Moreover, we actually do not recommend using deterministic approximation since it is not good for stochastic optimization problems and cannot provide confidence intervals for the population value as mentioned in Q2 by Reviewer QEcr.

First, we would like to express our gratitude for the time and feedback from the reviewer. We would like to address questions as follows:

Q8: 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.

A8: From Table 2, all QSW variants (except GQSW) and RQSW variants give lower reconstruction losses (in Wasserstein-2 distance and Slced Wasserstein-2 distance) than SW in all evaluated epochs. This means that the QMC methods help to improve the approximation of training losses which improves the quality of training neural networks. Using a more powerful neural network can lead to a lower reconstruction loss, however, we believe that the comparative order between RQSW and SW might not be changed. When the autoencoder is very powerful, both RQSW and SW will make the reconstruction losses go to 0 when the number of training iterations goes to infinity. However, model misspecification always happens in practice, hence, the reconstruction losses cannot go down further after several training iterations. In the paper, we show that RQSW also helps to reduce the reconstruction losses at early epochs. For QSW, it is deterministic and it must have a large enough number of points to achieve good results. Overall, we still recommend RQSW for applications, especially deep learning applications.

Q9: 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.

A9: Thank you for your comments. The main goal of Figure 1 is to demonstrate the low-discrepancy property of point sets. From Figure 1, we can see that the conventional Monte Carlo does not give point-sets with good uniformity. In the revision, we have moved Figure 1 to the Appendix and scaled up Figure 1 and Figure 2.

Q10: 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.

A10: Thank you for your suggestion. We have added the computation time to the gradient flow applications in Tables 1-2. For other applications, we omit the computational time since the major computation is not from computing the distance which makes the measurement non-robust to the system noise. However, the comparative comparison should be the same among all applications.

Q11: Related to W.3, empirically, how efficient in terms of time are all the presented approximations?

A11: From the computational time computed as discussed in Q10, we observe that QSW is always faster than SW since it does not require sampling of projecting directions. RQSW is always slower than QSW since it needs to randomize the constructed QMC point-sets. To compare RQSW and SW, for a relatively small value of the number of points $L$ i.e., 10, SW is slightly faster than RQSW since sampling an orthonormal matrix of size $3\times3$ and applying matrix multiplication costs more time than sampling from the uniform distribution over the unit-hyperspher. However, when $L$ is relatively large i.e., 100, RQSW (with random rotation) is slightly faster than SW. The reason could be sampling $3\times 3$ orthonormal matrix is much faster than sampling $100$ vectors on the unit-hypersphere.

First, we would like to thank the reviewer for the time and feedback. We would like to summarize the questions and answer them as below:

Q1: 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.

A1: Thank you for your comments. One of the main goals of our paper is to connect the literature on Monte Carlo Methods, especially Quasi-Monte Carlo (QMC) with the sliced Wasserstein literature. We observe that the application of QMC on the unit-hypersphere is quite limited while they are theoretically deep and challenging. In contrast, Sliced Wasserstein has several applications; however, the default computation is carried out via the conventional Monte Carlo integration. Therefore, the paper could be the bridge that makes QMC on the unit-hypersphere be used more in the machine learning and deep learning community and makes the computation of SW more interesting on the theoretical side. In the paper, we demonstrate the favorable performance of the proposal across various applications, e.g., point-cloud interpolation, image-color transfer, and deep point-cloud compression.

We also would like to recall that the randomized Quasi-Monte Carlo on the unit-hypersphere has not been discussed before. In the paper, we introduce two ways to construct a randomized QMC sequence on the unit-hypersphere i.e., mapping a randomized QMC on the unit-cube and random rotating of a QMC sequence on the unit-sphere. We then show that almost all constructions lead to an unbiased estimate of SW and perform well in 3D applications.

Q2: 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

A2: Thank you for your insightful suggestion. The randomized QMC for SW can be seen as a variance reduction technique for estimating SW. In addition, as in your suggestion, confidence intervals on the estimates of SW could also be obtained.

In more detail, we can obtain $M$ i.i.d RQSW estimates, then the corresponding empirical means and empirical variances. Since RQSW is an unbiased estimate of the population SW, we can use the central limit theorem to obtain the asymptotic normality result. After that, we can form the $1-\alpha$ confidence interval for the population value of SW. Alternatively, we can only use Bootstrap to construct a confident interval. We refer the reviewer to the detailed discussion in the revision of our paper, in Appendix B in blue color.

Q3: 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.

A3: As an example of a visually better performance of QSW and RQSW, we refer the reviewer to Figure 5 (Figure 4 in the revision). In the figure, the reconstructed plane point cloud from SW is quite noisy i.e., some points are far from the main plane. In contrast, the plane from CQSW has only 1 point that is far from the main plane while the plane from RCQSW is not noisy at all. Overall, we agree that it must take a detailed look to see a more favorable performance of QSW and RQSW visually. Therefore, we still recommend using the quantitative result (in Wasserstein-2 distance) as the main comparison between QSW, RQSW, and SW.

First, we would like to thank the reviewer for constructive feedback. We would like to address questions from the reviewer as below:

Q4: 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\sharp \mu,\theta \sharp \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.

A4: Thank you for pointing this out. We agree that the integrand must satisfy the smoothness assumption for the absolute error bound to hold, and - as far as we currently know - SW is only a Lipchitz function [R1] in the L2 norm. Indeed, we do not claim that the Koksma-Hlawka inequality applies in our setting but use it to suggest that QMC methods might improve SW estimation in practice. Due to the lack of such theoretical guarantees in our setting, in Section 4.1 we conduct simulations to show that QMC leads to better approximations of SW.

To elaborate further on this point, checking for the needed smoothness conditions of SW as a function of the projecting direction implies working with appropriate notions of derivative on the unit sphere (see, e.g., [R2]). To the best of our knowledge, the calculation of such derivatives for SW with respect to the projecting direction is highly nontrivial. The hardness of the problem comes from the fact that we do not know the form of the pushforward projected measure and its CDF. Moreover, in the discrete case, the sorting operator is not smooth, hence the calculation is not practical. In addition, SW involves integration on the unit-hypersphere. Therefore, it must be transformed into an integration on the unit cube through a transformation such as the Gaussian-based mapping and equal area mapping, to be considered as a conventional QMC problem. As discussed in Chapter 6 in [R3], the composition of the transformation and SW must satisfy smoothness assumptions for the error bound to hold. Other related approaches to establishing favorable error rates for QMC designs (e.g., [R4]) rely on showing that the integrand belongs to appropriately defined Sobolev spaces of functions over the unit sphere. This involves working with concepts at the intersection of spherical harmonics and functional analyses that are non-trivial to apply to the SW case, even in simple cases (e.g., when \mu and \nu are both Gaussian) for which closed-form expressions for the slice exist. To conclude, we are aware of the importance of deriving theoretical guarantees for QSW estimation and thank the reviewer for further pointing this out. In fact, we are presently considering future research directions to theoretically expand the current work, which nevertheless shows a good practical performance of QMC methods for SW computation.

[R1] Statistical, robustness, and computational guarantees for sliced Wasserstein distances, Nietert et al,

[R2] Spherical harmonics and approximations on the unit sphere: an introduction, Atkinson & Han et al,

[R3] Quasi-Monte Carlo Methods in Non-Cubical Spaces, Basu el al,

[R4] QMC designs: optimal order quasi Monte Carlo integration schemes on the sphere, Brauchart et al,