Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces a (possibly) cheaper approximation of Sliced Wasserstein (SW) distance. The proposed technique is based on calculating 1D Wasserstein distance between Gaussian projection directions. This is motivated by the fact that Wasserstein distance between Gaussian distributions admits a closed-form solution, which leads to an easy compute of the proposed approximate SW and discard a large number of uniformly sampling random projections for the Monte Carlo approximation of the original SW distance.

main_review: Strengths: the authors propose a new approach for approximate the SW distance using 1D Wasserstein distance between Gaussian distributions. Under mild conditions, the authors provide nonasymptotic guarantees on the error between the original and proposed approximation of SW distance. Overall, I find the exposure being well supported by the theory and the results are important to the field of sliced Wasserstein distances research direction. The paper is clearly written. The authors introduce all the material needed to understand the method. The proofs are well detailed and seem reasonable.

Weaknesses: the rate $d^{-1/8}$ for the nonasymptotical analysis seems (too) slow, whereas some experiments show a decay for this error for reasonable values of $d$. There is one important missing work that should be cited though:

Nguyen, Khai, et al. "Distributional Sliced-Wasserstein and Applications to Generative Modeling." (https://arxiv.org/abs/2002.07367)

where authors proposed the distributional slicing approach which is a general technique to design a probabilistic way to select important direction by finding optimal distribution over explored projections. I really believe this paper could also lead to interesting computational comparisons.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper presents a method to estimate the Sliced-Wasserstein distance. The method is based on the Gaussian approximation of the projected data, thus the SW distance could be approximated through the SW distance between Gaussians which has a closed-form. Hence, the method is better than the Monte Carlo SW distance in term of computational speed. The authors also demonstrate their method on toy data set and real data sets, i.e. MNIST and Celeb A.
main_review: The paper starts with reviewing some results from Reeves that the SW-2 distance between the  projected distribution and the corresponding Gaussian could be bounded by a constants which depends on the mean and covariance matrix. Then in Section 3,  it moves to the SW-2 distance with Gaussian projections, where they proved that  the SW-2 distance using unit projection vector is proportional to the SW-2 distance using Gaussian projection. This result is not surprising, since the way to generate random unit vector from uniform distribution on the sphere based on normalzing a Gaussian vector. From the theoretical point of view, normalzing a Gaussian vector in high dimensional space to form an unit vector will not affect too much to the effect of the SW-2 distance. Because in high dimensional space, a Gaussian vector with independent components has a similar magnitude of length by the law of large number.  Using Gaussian projection might only  have some advantages of playing with the formulas rather than the effectiveness of the projection. 

In section 3.2,  the authors  provide a similar bound for the difference between the SW-2 distance between two probability measures and W-2 distance between the corresponding Gaussian distributions, which is bounded by function of covariance matrices.  Section 3.3 shows the error analysis under the assumption of weak dependence between vector's components and the dependency between vector's component decrease as the gap between components increases.  The reviewer personally finds the condition of weakly dependency quite unrealistic.  It could be realistic in some cases like time series data. But weak dependency is closer to independency, thus the point cloud of the distribution is all over the space, i.e point cloud of Gaussian distribution. It  is quite contradictory to the popular view that the data generally lie in a low dimensional manifold. What could the authors comment about it?

The experiment section starts with a toy example of synthetic data, it is time series  data, so it is quite different from other data sets, because there is an order between components and weakly dependency condition over the order of components. For the real data set, they present 3 methods of  two using the Monte Carlo.  Among them, the Reg-det-SWG obtains a comparable FID score but a much faster processing time. However, the authors have not compared their methods with other methods of selecting important directions for projection.  

Overall, this work is based on approximating the SW-2 distance. The main question is that why on the real data the approximation produces a comparable performance  with  the Monte Carlo method even when the number of the projection for the Monte Carlo method is large and the upper bound for the approximation error is not small? Because of the above-mentioned reasons, I do not believe that the theory of weak dependency is the  explanation for the comparable performance of the method on the real data set. Hence, there needs at least an ablation study to shed some light on the question.
limitations_and_societal_impact: It is fine.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper develops a novel deterministic approximation for the Sliced-Wasserstein Distance (SWD), based on the fact that a random linear projection of a high-dimensional vector has an approximately Gaussian distribution. In many cases, the approximation involves no tuning parameters and can be computed much more quickly than the usual Monte Carlo estimate of SWD, especially for very high-dimensional data. If the $d$ dimensions of the data are not too strongly correlated, then the approximation converges no slower than $d^{-1/8}$ as $d \to \infty$. Experiments with synthetic data validate this theoretical result, as well as the computational benefits of the proposed approximation. Finally, the paper demonstrates an application to image generation.
main_review: Overall, the paper is very clearly written and well-motivated, and the proposed estimator seems novel and useful. From a statistical perspective, I have some concerns about the usefulness of the provided theoretical results.

Main Comments/Questions:
1) The paper bounds the error between the true SWD and the approximation when the true data distributions are used. In reality, empirical distributions over IID data, rather than the true distributions are used. Roughly speaking, the paper bounds the bias of the proposed estimator, but not the variance. Could the authors discuss the rate as which the variance decays as the sample size increases?

2) A convergence rate of d^{-1/8} is quite slow (a decrease by a factor of ~1.3 for each 10-fold increase in dimension). On the other hand, based on the synthetic experiments, it appears that the estimator might converge at a faster rate in practice. Could the authors speculate on whether this theoretical rate is tight (in the worst case) under the given fourth-order weak dependence assumption, and/or under what conditions the convergence rate might be faster? I see that this is noted in Lines 339-342, but it would be nice if the authors could expand on this a bit.

Minor Comments:
1) Line 126: Typo: "whose contributions has" -> "whose contributions have"

2) Line 128, "$\mu_d^X$, the distribution of $X_{1:d}$":  Upon first reading, it wasn't immediately clear to me whether $\mu_d^X$ was the *empirical distribution* of the data, the *population distribution* from which each X_i was drawn IID, or the *joint population distribution* of all d. If I understand correctly, the assumption that $\mu_d^X \in \mathcal{P}_2(\mathbb{R}^d)$ (on Line 129) only really makes sense under the last interpretation, but this distinction could be clearer on Line 128.
limitations_and_societal_impact: The paper briefly discusses an apparent gap between the main theoretical and empirical results. I don't foresee any potential negative societal impact of the work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a new approach to approximate the sliced Wasserstein distance. In particular, the paper extends the central limit theorems for random projections to derive a deterministic approximation of sliced Wasserstein (based on the closed form of Wasserstein distance between two Gaussians) that is efficient (low error) in high dimension under centering assumption (weak dependence assumption). On the experimental side, the paper illustrates the derived theory on the synthetic data and compares the proposed approach to the conventional Monte Carlo approximation of the sliced Wasserstein distance.
main_review: Originality: Gaussian projections were also used in the sliced score matching technique [1], however, the application to the sliced Wasserstein in the paper is original. The deterministic approximation of the sliced Wasserstein that is based on the usage of the central limit theorems for random projections is new and novel.

Quality: The submission is technically sound. The error between the proposed approximation and the true value of the sliced Wasserstein is bounded for both two assumptions. Moreover, the paper haves demonstrated the superiority of the new approximation over the Monte Carlo estimation in terms of both computation complexity and performance in generative modeling experiments.  The authors have also discussed the limitations of the approximation due to the independence (the weak dependence) assumption. The experiments are adequate for showing the faster computational speed of the deterministic sliced Wasserstein.

Clarity: The paper is well-written, easy to follow. The experimental settings are reported enough to reproduce. The proofs are written rigorously and correctly.

Significance: The paper pushes forward the practical applications of the sliced Wasserstein distance, and provides a new insight to understand the distance. However, the convergence rate is slow, hence, the approximation seems only efficient in the case of very high dimensional measures.

[1] Sliced Score Matching: A Scalable Approach to Density and Score Estimation
limitations_and_societal_impact: The weak dependence assumption is not easy to be satisfied in practice, additional experiments on other datasets  (CIFAR-10, LSUN) and other applications (e.g. autoencoders, approximate Bayesian computation) are needed. The approximation seems only work well with high dimensional measures, hence, I think it is necessary to do some experiments on applications that involves low dimensional  measures (latent space of autoencoders, color transfer).

Minor comments: FID scores should also be reported in the middle of the training process (different epochs).

Questions:
1. is it possible to extend the result to derive deterministic approximation for the non-linear projecting (generalized sliced Wasserstein) and other extensions of sliced Wasserstein such as max sliced Wasserstein, k-max sliced Wasserstein and spherical sliced Wasserstein [2]?
2. Can we derive an algorithm to transport a measure to a measure like the iterative distribution transfer algorithm for this type of approximation? 

[2] Improving Relational Regularized Autoencoders with Spherical Sliced Fused Gromov Wasserstein
review_title: null

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

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