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: This work concerns the asymptotic behaviours of Gaussian-smoothed 2-Wasserstein distance. In particular, the authors provide bounds on the difference between Wasserstein distances of a pair of discrete measures and their smoothened versions when the variances of Gaussian kernels are small. The authors consider two scenarios, when a perfect matching between two discrete measures exists and when it does not. For the former case, they show that the asymptotic gap decays exponentially in some near-zero regions, and linearly otherwise. For the latter case, they show that the gap is linear even in a region around zero.
strengths_and_weaknesses: Strengths:
- The paper is well-written and well-presented.
- The addressed questions are of theoretical importance, and the given answers to these questions are novel and complete to the best of my knowledge. The authors covers all possible scenarios, and the tools used for proofs (stronger notions of cyclical monotonicity and implementability, robustness of optimality and their relations) are interesting to me.

Weaknesses:
- In the experiment, the toy example is indeed beneficial for understanding, but I think the authors should also verify their theory in large-scale settings (i.e., large $m, n$ - maybe in the one-dimensional space if the design of points statisyfing the uniqueness of optimal plan is an issue).
questions: Minor Comments:
- In the proof of Theorem 3.1 in the Appendix:
  - Should the truncated kernel be $\mathcal{N}(0, \sigma^2 I) \cdot \mathbf{1}\\{\\|X\\| \le \epsilon_*\\} + (1 - p) \delta_0$?
  - At the end of the proof, for the second inequality, it would be more clear if the authors state which couplings are used to bound the Wasserstein distances.

Questions:
- In the toy experiment, if we slightly modify $\nu$ to $\nu'$ using $k \approx 0$, then there is an unique optimal transport plan between $(\mu, \nu')$, but should the asymptotic behaviors of both pairs $(\mu, \nu')$ and $(\mu, \nu)$ be approximately similar?
- If we look at the Gaussian-smoothened version of a discrete measure as a Gaussian mixture, then does the separability between the means (i.e., the discrete support) play some role in the asymptotic behaviors?
- Do you think that the appearance of the uniqueness of the optimal plan in the study of asymptotic behaviors is related to the use of 2-Wasserstein? For example, if we consider the 1-Wasserstein distance between two sets of points on the real line, and suppose there is some overlapping between the sets, then the optimal plan is not unique, but we can simply remove the overlapped points in both sets without affecting the distance (and consequently the asympotatic behavior) and return to the uniqueness case?

Minor Error:
- In the figures, $p$ should be $k$.
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
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 paper provides an approximation rate for Gaussian-smoothed Wasserstein distances for discrete measures. It shows that the approximation rate can be exponential in the perfect-matching plan case (with a phase transition to linear rate if $\sigma$ is large) and is linear otherwise.
strengths_and_weaknesses: **Strength**: The results in this paper are interesting and all the theoretical results are technically correct. 

**Weakness**: The setting considered in the paper appears to be restrictive. Both measures of interest are assumed to have finite number of support points. It makes the developed theory difficult to apply to general setting of Gaussian-smoothed Optimal Transport. 

Some points in presentation that can be improved:

1. In Proposition 1.1., the constant $c$ is dependent on $d$ (dimension) as well. The author should make this point clear so it is coherent with the argument about the curse of dimensionality of the Wasserstein distances. 

2. In the presentation of Section 3 (Case I): We need reasons why you choose to present Proof of Theorem 3.3. but not of other results (like Theorem 3.1, which appears to be one of the main results). If the proof of Theorem 3.1. is not presented in the main text, then why do you present Lemma 3.4.? In general, the writing style in Sections 3 and 4 needs to be improved so that the reader can know what proof is going to be presented and what is deferred to the appendix.  

3. The order of results in the appendix is not consistent. Dividing those results into several small sections may help to keep track of this issue.
questions: 1. The results in the paper are interesting in that the approximation rates for the "perfect-matching" case are much faster than other cases (exponential compared to linear). To complete the story, can you present some sufficient conditions to have perfect matching in OT?

2. The technique used in the paper seems not to be restrictive to discrete measures only. I suggest the author extend these results to arbitrary $\mu$ and $\nu$, as the "perfect-matching" is easier to attain for absolutely continuous probability measure. If it is not possible to do this extension, then it would be helpful to have a paragraph to discuss why. 

3. In the statement of Theorem 3.3., what do you mean by $G(\sigma^*)$ is asymptotically greater than $\sigma^*$? Because $\sigma^*$ here is fixed, I can not see the asymptotic greater sign here with respect to what variables. 
limitations: Because of the restriction of the setting in the paper, it is not obvious to see implications in using Gaussian-smoothed Optimal Transport for general measures. I recommend considering the problem in a more general setting and trying to see if the current approach still works.
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 studies the approximation of the 2-Wasserstein distance between two discrete probability measures $\mu$ and $\nu$ by the 2-Wasserstein distance between the same distributions smoothed by a Gaussian measure, that is called Gaussian-smoothed optimal transport. In particular, they prove the existence of a phase transition in the small noise regime of the variance parameter, which depends on the existence of a perfect matching between the distributions $\mu$ and $\nu$.

strengths_and_weaknesses: Studying the behaviour of Gaussian-smoothed OT distance is particularly interest as it approximates the true transport and does not present a curse of dimensionality in the sampling complexity. In particular proving the curious result of the existence of a phase transition in the context of finitely supported measures $\mu$ and $\nu$ is very nice. Moreover, this paper is well written, the problem and presentation are clear and the choices made for the study (the finitely supported framework) are precisely justified. The proofs, based on strong cyclical monotonicity and perfect matching, are quite elegant. The simulation study is also concise and convincing.

Overall, the results constitute a modest (because limited to Gaussian-smoothed OT distance) but very interesting contribution to the study of approximations of the classical Wasserstein distance.

Minor comments:
- The notations for the parameter $\sigma$ of the Gaussian and the permutation $\sigma$ can be confusing.
- The order and presentation of proofs in the appendix could be improved.
questions: - Could you transpose your results to the case of entropy regularized optimal transport? In this case, the uniqueness of the transport plan is guaranteed but the perfect matching does not make sense anymore for large regularization parameter since the mass of the regularized transport plan is spread out.

- In Proposition 1.1, why is the condition that probability measures are compactly supported essential?

limitations: The authors decided to limit their study to finitely supported measures, which is well justified.
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 presents an analysis of the Gaussian-smoothed Wasserstein distance (GOT) in the framework where the Gaussian kernel parameter $\sigma$ is "small". It is already known that (GOT) approximates the true Wasserstein distance and that the difference between the two is of order $\sigma$. The objective of this paper is to refine this bound and to show, under certain assumptions of uniqueness of the transport plan, that this bound can be improved and that GOT approximates Wasserstein exponentially well in a certain regime. More precisely, the authors show that there is a phase transition on $\sigma$ such that, below, the bound is exponential, and, above, it is linear in $\sigma$. This paper completes the understanding of GOT with respect to $\sigma$, which has already been studied in the $\sigma \to +\infty$ regime.
strengths_and_weaknesses: Overall I find this article quite well written, the thread of definitions and proofs is clear, the ideas are well linked. From a purely theoretical point of view the results are, I think, really interesting. They complete the statistical understanding of GOT with respect to $\sigma$, which is a nice contribution. Moreover, the ideas/tricks introduced and the theorems go far beyond the study of the GOT distance and can certainly be used to establish other theoretical results in optimal transport. In particular I think that the notions of strong implementability/strongly cyclically monotonic and robustness of the transport plans are useful and rich.They allow us to establish the uniqueness of the transport plan, which is, in the discrete case, a key property that is not much addressed by the community as far as I know. The fact of having cleared all these properties around the strong implementability is for me a contribution that is useful in itself. The phase transition of GOT opens also the door to other studies, notably on sample complexity or on approximations of the Wasserstein distance. 

The main criticism I would have is that this article focuses on a really specific and technical problem, related to a sub-problem of optimal transport. For a reader who is interested in GOT the contributions are certainly really interesting, but the article does not discuss the potential applications for optimal transport in general neither for machine learning. To be more precise, the article strings together theoretical results without giving much insight, nor discussing the propositions and theorems. It also lacks a conclusion that could perhaps bring some perspectives around this work. In this context, I think it would be interesting to save space by moving the proof of Theorem 3.3 to an appendix to make a conclusion/perspective part and for discussing the different results and their implications. For example it could be interesting to discuss, even informally, the possible generalization to the case of continuous measures or to explain their implications for the Wasserstein distance approximation. 

Moreover, the numerical results are very succinct and, I find, difficult to read. I find for example that the phase transition, which is the center of the contributions, is not really visible on Figure 2. I think that this part should be more complete, by better illustrating this phase transition or for example the notion of robustness of a transport plan.

For these reasons I rather recommend a weak-accept, but I am ready to change my mind depending on the authors' answer.

Small remark: 
- In terms of notation the $\sigma$ is both used to define a permutation and for the $\sigma$ of the Gaussian kernel.
- Moreover the fact that $\sigma$ is a permutation in Definition 2.4 is not clearly stated in the article.
- Typos: $T$ instead of $\Gamma$ in Proposition 2.12 and 2.13. 
questions: - In Remark 2.14 it is said that condition (5) in the context of residual functions of quadratic type is "easier to verify in pratice". It is not really clear to me how (6) can be verified easily because it depends on $\alpha,\beta$. To check that this condition does not hold we should do it for all $\alpha <\beta$ am I correct ? Can the authors detail this point ?
- The fact that $\Gamma$ is f-strongly implementable seems to be really related to the article [PdC20] of the paper, i.e. to the fact of imposing that the Monge map is the gradient of a smooth and strongly convex potential. Can the authors discuss this connection in more detail? 
- The proof of Theorem 2.7 is rather succinct: "This is a direct application of Theorem 4 in [THG17]". Could the authors give more details about the connection between "$\Gamma$ is strongly implementable" and the results of [THG17] ?
limitations: The authors did not discuss the potential negative societal impacts of their work, however this is not really relevant in this context as the article is quite theoretical and specific. Concerning the limitations: I find that the authors could discuss how, in practice, can we check if we are in the regime of fast approximation (i.e. when the transport plan is unique). 


------- AFTER REBUTTAL -------

As written below I am satisfied with the authors' answer so that I change my score to 7
review_title: null

Meta-review: metareview: All reviewers are in agreement that the main factors (in particular, the results and their presentation) are above the bar for NeurIPS.  No significant concerns remain following the author response and the discussion period.  I encourage the authors to carefully take into account all of the minor comments when preparing the camera-ready version.
confidence: Certain
Decision: Accept