Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper is focused on Sliced-Wasserstein (SW) and Max-Sliced-Wasserstein (Max-SW) distances and it provides important theoretical results on three fronts: 1)  empirical convergence rates, 2) robustness to data contamination, and 3) the error rates of Monte Carlo estimator for SW and the computational complexity bound for the subgradient-based local optimization that is often devised to calculate Max-SW distances. The results are well positioned with respect to existing work in the literature, and whether provide tighter bounds or looser assumptions. In particular, for log-concave distributions the authors show: 1) the sample complexity of SW and Max-SW are both $n^{-\frac{1}{max(2,p)}}$, the rate is sharp, and that the constants depend on the dimensionality of the problem, 2) under $\epsilon$ TV-contamination, the p-SW and p-Max-SW distances for the class of distributions with bounded q'th moment projections, and maximum covariance eigenvalue of $\sigma$,  have minimax rates of $\sigma\epsilon^{-\frac{1}{p}-\frac{1}{q}}$, and finally 3) the convergence of the subgradient-based local optimization commonly used for Max-SW distance is $O(\epsilon^{-4})$ and the results are obtained without the entropic regularization used previously in Lin et al. [NeurIPS 2020]. Lastly, all three contributions were numerically confirmed on simple problems.
strengths_and_weaknesses: Strengths: 

* The paper is well written, and well organized, and the authors have done a good job placing their work among the recent literature on this topic.

* The contributions improve the existing bounds/rates with fewer/less-restricted assumptions. 

* The paper provides theoretical contributions on multiple fronts to a topic that is of interest to a broad audience.

Weaknesses:

* Not necessarily a weakness but the experimental section of the paper is on the lighter side, which makes sense given the heavy theoretical contributions. 
questions: Minor editorial: 

Line 114 - "For for a measurable map" must be "For a measurable map."


limitations: Given the more theoretical nature of the work, I do not foresee any potential negative societal impact of this work. 

In addition, the authors have done a good job describing the limitations and future work (the room for improvement), and have been transparent about all assumptions used in their derivations.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The Sliced-Wasserstein distance (SW) has been deployed in various machine learning applications over the past few years as a computationally efficient alternative metric to the Wasserstein distance. Due to its reported empirical success, recent work have studied the theoretical properties of SW to further motivate its use. For instance, SW has been shown to retain some important topological properties of the Wasserstein distance while yielding a dimension-free sample complexity, which justifies its efficiency on high-dimensional settings. On the other hand, a different line of work identified the limitations of SW and proposed solutions, including alternative metrics inspired by SW, such as the maximum Sliced-Wasserstein distance (max-SW). 

This paper is a theoretical analysis of SW and max-SW, which refines existing guarantees for these metrics and explores unsolved questions. The contributions are described more precisely below.

1) Convergence rates of empirical distributions to the "true" distributions under SW or max-SW are derived (Section 3), assuming the true distributions are log-concave (Theorem 1) or supported on compact domains (Theorem 2). Empirical convergence rates under SW or max-SW have already been established in the literature under different assumptions. The authors argue that, as compared to prior work, their rates are faster or reflect more explicitly the influence of the data dimension (Remarks 1 and 2).

2) The robustness of SW/max-SW to outliers is also studied (Section 4): the minimax risk for robust estimation under SW/max-SW for a corrupted distribution (according to "total variation contamination") is characterized (Theorem 2, Corollary 1), under assumptions on the corruption level and on the moments of the projected distributions. The authors state their result is another confirmation that SW does not suffer from the curse of dimensionality, since the minimax risk does not contain a factor of $\sqrt{d}$ as opposed to the Wasserstein distance (Remark 4). Additionally, the "resilience" condition (which bounds the difference between the means of $\mu, \nu$ for $\nu \leq \frac{\mu}{1-\varepsilon}$) is shown to be equivalent to controlling max-SW$(\mu,\nu)$ (max-SW is of order 1) for $\nu \leq \frac{\mu}{1-\varepsilon}$ (Proposition 2). This allows the authors to extend algorithmic guarantees for robsut mean estimation (under the resilience condition) to robust estimation with max-SW.

3) Then, guarantees on the errors induced by the approximation of SW or max-SW are established (Section 5). First, the error associated to the Monte Carlo estimation of SW is bounded, assuming the distributions are log-concave -- which, similarly to Section 2, helps derive rates that are explicit in the parameters of the problems ($n, m, d, p$), as opposed to existing error bounds in related work (Remark 5). Then, convergence guarantees on a subgradient method used to approximate max-SW of order 2 (Algorithm 1) are derived (Proposition 4), provided $log(n) \leq \sqrt{d}$ and $\mu, \nu$ are log-concave. As discussed in Remark 7, some algorithms have been proposed in the literature and shown to be faster, but they are less used than the subgradient method and slower in practice (Figure 2). Note that these results rely on the fact that the Wasserstein distance between projections of distributions (as a function of the projection direction) is Lipschitz (Lemma 1).

4) Finally, the authors conduct a set of experiments on synthetic data in order to illustrate their theoretical findings (Section 6).
strengths_and_weaknesses: This work adequately addresses some important theoretical questions raised by the increasing use of Sliced-Wasserstein distance and its variants in machine learning applications. The contributions are mostly theoretical and have clear practical implications: they help quantify the efficiency and robustness of SW and max-SW according to the problem setting (i.e. in terms of data dimension and nature of distributions), or evaluate the quality of the traditional estimates of SW or max-SW. In that sense, I believe this work is significant and useful. 

I find the paper very well written and clear. I strongly appreciate that the authors put effort into providing interpretations on their theoretical findings as well as discussions on their advantages and limitations over prior related work. Overall, the contributions of this paper, namely the theoretical results, their proofs and their empirical illustration, look sound to me. The proof techniques do not seem particularly original (e.g., they are direct consequences of existing results on one-dimensional Wasserstein distances derived in [5] or consist in assuming a specific structure for the distributions, i.e. log-concavity, a common practice in statistics), but they provide answers to relevant questions on SW in a simple and elegant manner.

The main weakness of this paper is that it is too dense. I am quite familiar with the questions addressed in this work and related work, which strongly helped me understand the main conclusions of the contributions, but I could not thoroughly check all the proofs in the supplement document. Besides, some aspects of the paper are unclear to me: more details are given in the "Questions" section of my review.

On the other hand, one important related work is missing and should be discussed as compared to the contributions: "Minimax Confidence Intervals for the Sliced Wasserstein Distance", Manole et al., 2019.
questions: Besides adding a discussion to [*] "Minimax Confidence Intervals for the Sliced Wasserstein Distance" (Manole et al., 2019), I encourage the authors to clarify the following points. 

Theorem 1:
- Equation (2a): according to the proof, if I am not mistaken, $log(n)$ should be $log(n)^{1/2}$.
- Proof of Lemma 3(ii): For $p \geq 2$, $n^{1/2}$ is missing when bounding the RHS, since $|| u - u' ||_1 \leq n^{1/2} || u - u' ||_2$ (to verify).

Remark 2: the case $\Sigma = I_d$, whose norm indeed does not depend on $d$, is not realistic since components of a data point are more likely to depend on each other. Could the authors provide a more realistic example to illustrate the dependence on $d$ in their rates?

Proposition 1: 
- Such rates were already established in the literature (e.g., [Section 4, 34] or [*]). Could the authors precise what is new in Proposition 1 as compared to prior work?
- Proof (end of Appendix D.2): it is unclear to me why the rates for SW$^p$ (or max-SW$^p$) can be applied to SW (or max-SW): how to get rid of $b^{1-p}$?

Remark 4: "slicing eliminates a $\sqrt{d}$ factor" This is true for max-SW, but not for SW whose minimax risk can contain such factor depending on the value of $d/q$ and $p/d$ (see Theorem 2). Could the authors clarify this aspect?

Proof of Lemma 1 (Appendix D.8): "the last step uses the optimal transportation cost formulation of $W_p$", this step is confusing to me. Could the authors explain why they can bound the sum of one-dimensional Wasserstein distances by the product of $||\theta_1 - \theta_2||$ and a sup over $\theta$? 

Proposition 3: Could the authors confirm if the second term in the RHS is in $n^{p/2}$ when $p > 2$? It seems like it should be in $n^{-1}$ according to the proof of Proposition 3 and Theorem 1.

Section 6, "Projection and sample complexity": The increase of the errors with $d$ for Model (2) is not obvious on Figure 1(b). I think the authors should give more detailed explanations on why this behavior is expected (for both models) given Proposition 3: the provided explanations are quite vague (due to a lack of space, I guess).

Minor comments:
- Typos: l.114 "For for", l.122 "nongenerate", l.211 $\mathcal{R}^d$, Algorithm 1: in the title, $\tilde{\omega_2}^2$ but in the loop, $\tilde{\omega}_p^p$, l.290 "in not necessary", l.383: "providing rigorous justification the perceived scalability"
- l.91: the definition $\omega_p^p$ should be precised here. Same for $\omega_2(\theta)$ (l.98)
- The following operators should be defined: $\lesssim_p$, $poly(d)$, $\asymp$, $Conv$
- l.187: $\sigma$ is already used to denote the uniform distribution on the sphere.
- l.219: Unclear definition for $\delta_{\mathbb{B}^d}$
- The uncertainty of the empirical results is not reported and the authors say in Appendix E that error bars will be added in the final version of this paper. This aspect is important and should have been included in this version.
- Appendix D.9: Add a reference for the dual form of $W_p^p$


limitations: The limitations of the theoretical results are adequately discussed throughout the paper. The potential negative societal impact is not addressed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper provides a comprehensive theoretical analysis on the scalability, convergence rates, and robustness of sliced Wasserstein distances and max-sliced Wasserstein distances. Specifically, the paper established sharp empirical convergence rate for sliced Wasserstein distances which is sharp up to log factors over the log-concave class. In addition, this work also investigated the robustness of (max) sliced Wasserstein distances to data contamination. For the computational guarantees, the Monte Carlo error bound of the sliced Wasserstein distance using finite slices was derived. Regarding the max sliced Wasserstein distances, although without formal computational guarantees, this paper analysed a subgradient-based local optimisation algorithm used in previous literature and proved a computational complexity bound for it. The experiment section validates the above theoretical analysis, including the projection and sample complexity, the computational cost of the subgradient max sliced Wasserstein distance, and the robustness of max sliced Wasserstein distance to data contamination.
strengths_and_weaknesses: Strength:
1. This paper is well-written and well-structured, provided an in-depth analysis of the statistical properties, robustness to data contamination, and computational guarantees for sliced Wasserstein distances and max sliced Wasserstein distances.

2. The derivations are theoretically sound and provides a good reference for the community working on sliced Wasserstein distances.

Weakness:
Although not entirely a weakness due to the nature of theoretical work, the technical part of the paper, including notations and equations, are dense. It will be helpful if the paper can be made more accessible, so that researchers working on algorithmic work rather than theoretical work of SWDs can more easily extract conclusions from the theoretical results derived in the paper.
questions: 1. In Theorem 1, it is assumed that measure μ is log-concave, is this a common assumption in ML applications? What if this assumption does not hold?

2. What are “one sample” and “two sample” the paper refers to? I guess they refer to the case where the compared distributions are the same and the compared distributions are different, respectively. The author would better explain it to avoid confusion.

3. Is it possible to show the improved robustness of max sliced Wasserstein distances upon classic Wasserstein distances in a ML model?
limitations: Future work including improved complexity bounds for the subgradient methods for computing max-sliced Wasserstein distances are mentioned, although limitations of the work are barely mentioned.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors' contribution is threefold: computing empirical convergence rates, robustness to data contamination and improving computational methods of SW distances.
strengths_and_weaknesses: Strengths:
- Multiple new theoretical results are given and rates seem to be sharp.

Weaknesses:
- Empirical results are sparse, more could have been expected, for more complicated distributions/datasets, to show the theory is robust.
- I don't have the feeling that the authors compare Theorem 1 to other convergence rates (for instance Equation 7.120 of https://tel.archives-ouvertes.fr/tel-03533097/document ).
- The authors should develop more on the log-concave assumption: what are the practical implications for ML practitioners? 
- I feel like the three parts of the papers do not have much in common and could each deserve a study on their own.
- What about distributional SW? Is it possible to compute such theorems for this distance?

I am willing to increase my score if I find the author's answer satisfying.
questions: No questions
limitations: no limitations or negative societal impact
review_title: null

Meta-review: metareview: All the reviewers are positive about the paper, they found that it is well written and provides very interesting theoretical as well as practical contributions which are relevant for the machine learning practice. 
confidence: Certain
Decision: Accept