Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Summary
=======

Context:
--------

This paper tackles the problem of estimating the rate of convergence of empirical Monge maps
(through its Kantorovich barycentric map approximator) to the true Monge map for 
absolutely continuous Lebesgue measures. 


Contribution
------------

- The authors provide new rates of convergence of the barycentric map using standard 
empirical plug-in estimators (O(n^{-2/d}))
- If the measures are regular enough (Holder smooth), the dependence on the dimension
completely vanishes (which was established for Gaussian distributions https://arxiv.org/pdf/1905.10155.pdf)
- The authors propose to take advantage of this smoothness result to sample from smoothened distributions
(using a Kernel density estimator) and provide the sufficient conditions to obtain a desired rate. Higher
smoothness however requires more samples: a tradeoff between statistical accuracy and computational cost
cannot be avoided.


main_review: review
======

General assessment
------------------

For a purely theoretical paper, this paper is vey well structured and easy to read. Transitions are smooth, and theorems
are fairly well motivated and interpreted. Even though one may wonder whether a journal would have been more appropriate
for this paper, the theoretical contributions of this paper are novel and are certainly valuable for the OT community at Neurips.
My only main concern is the lack of clarity of how can proposition 2.5 hold, which suggests that the rate of convergence of W2
is significantly different when mu = nu (see point (5) below). This is the only point -- pre-rebuttal -- retaining me from increasing my score.
I would appreciate if the authors could shed some light on this: are there any assumptions mismatch between this setting and the one from [119] that would explain this disparity ? Otherwise shifting the samples of a distribution slightly would lead to better convergence rates. 

Specific comments
-----------------

1) In remark 2.1, the authors mention that theorem 2.1 doesn't require compactly supported measures
unlike previous results (of [69]). Still, for all the derived convergence rates (subsequent theorems), at least one 
of the  measures needs to have a compact support for a uniform bound of the potential function. While requiring less
assumptions on the measures to obtain similar stability results is certainly an improvement over the literature, I'm wondering
whether Theorem 2.1 can be used to obtain convergence rates (or any other simpler and interpretable upper bounds)
without assuming compacity of any of the measures. 

2) Still on compacity: how would an assumption on the tail of the measures compare with the compacity assumption ? Could
the uniform norm be substitued with a less stringent norm in the technical derivations so as to generalize the known convergence
rates for Gaussians for example ? 

3) Throughout the paper, T0 is assumed L-lipschitz. However the regularity of T0 can also be seen as a consequence of
the regularity of the measures themselves which begs the question: are there any sufficient conditions on the measures
that guarantee an L-lipschitz T0 without assuming "too much" smoothness on the measures. 

4) The constant C in the corollary seems to be obtained through existence theorems of arbitrary constants C1 and C2. Do we have
any bounds on these constants and their dependence on the parameters of the problem ? Perhaps the diameter of the bounded supports ?

5) in L 248, authors mention that T_m,n of theorem 2.4 cannot be computed from the data, is this because T_m,n is a continuous
barycentric map derived from the continuous measures given by the KDE ? If so, I think the dependence on m,n should be slightly different
(in terms of notation) to distinguish it from the empirical map. 

6) I find the result of proposition 2.5 quite intriguing. [119] provided a lower bound on the convergence rate for the case mu = nu, 
that is a rate that cannot be beaten by any estimator. Prop 2.5 shows that this rate can be improved (significantly) if mu != nu. 
This suggests that If I take a measure mu and shift its mean by a certain
value, I would need less samples to approximate the W2 value. Am I missing something here ? 

7) A minor remark on the appendix: please use a different notation for \bar{nu}, distinguishing it from  \tilde{nu}
is quite challenging specially when verifying the proofs. 

limitations_and_societal_impact: None
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper analyze the statistical behavior of the general plug-in estimators of OT defined by barycentric projections. The authors provide a thorough analysis of the rate of convergence for the transport cost and the transport map. They also consider kernel smoothed plug-in estimators and relate its rate of convergence to the smoothness of the densities, which alleviates the curse of dimensionality suffered by the plug-in estimator.
main_review: Strength:

1. The upper bound on the stability of the transport map defined via barycentric projections is new. The rate of convergence of the smoothed plug-in estimators is quite interesting since it reflects the smoothness of the densities.
2. The paper has an extensive related work section discussing clearly the relationship of their work to previous ones.
3. The paper is technically solid. The theoretical results are well explained and the intuition are nicely conveyed.
4. The authors also design a discretized version of the smoothed plug-in estimator which enjoys the same rate of convergence and can be computed in practice.

Major comments:

1. In the construction of discretized plug-in estimator on line 255, the procedure to obtain samples from the kernel density estimators is not discussed. This should also appear in the complexity analysis of computing $\tilde T_{n,m}$ especially when the ambient dimension is high.
2. In Theorem 2.6, the number of samples M is set to be $n^{\frac{s+2}{2}}$. In practice, the smoothness s is unknown. It would be better to discuss how to select s in practice.
3. An important selling point of this paper is, in my opinion, a discretized plug-in estimator which enjoys a good rate of convergence and can be computed in practice. It is expected to see some experimental results supporting this claim.


Minor comments:

1. On line 227 the squared 2-Wasserstein distance is considered, while the square is dropped in Proposition 2.5.
2. Section 3.2 feels rushed. It would be better to explain more on the intuition behind rHSIC.

-----
Updates: the authors addressed most of my concerns in the response. While I do believe adding the experiments on the discretized plug-in estimator will be a good addition to the paper, I also think the current version is already a good paper. Hence, I am keeping my score.
limitations_and_societal_impact: See comments above for suggestions.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In standard OT problem, marginal distributions of the data are unknown. The current work considers plug-in estimation using Barycentric projection and derived rate of estimation. The idea of Barycentric projection is to plug the estimated marginal distributions of the data in the OT problem. Conditional mean of given us estimated and rate of estimation is derived. Various plug-in estimators of density of are considered such as empirical CDF and kernel density estimator.
main_review: The work is new and results are strong and important. Paper written is clear and of good quality.
limitations_and_societal_impact: The concern is why the smoothness of the densities of are the same? In practice, the densities may have different smoothness degrees. Meanwhile, how to make it adaptive since selection of is a problem. 

Another concern is the motivation of using OT for estimating conditional mean, compared with various nonparametric approaches in literature such as local polynomial, smoothing spline, etc.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of estimating an optimal transport map between two probability distributions on Euclidean space, given IID samples from each of the distributions. The main result (Theorem 2.1) gives a general upper bound, in terms of the dual representation of the 2-Wasserstein distance. This is used to give upper bounds, in probability, on the rate of decay of the estimation risk both for the plugging in empirical distributions in the absence of smoothness assumptions and for kernel estimates under smoothness assumptions. Finally, implications for two applications (Wasserstein barycenter estimation and nonparametric independence testing) are discussed.
main_review: Overall, I think the paper's contributions are clearly sufficiently novel and relevant for acceptance. However, I think the paper would be rather difficult to read for all but a very small subset of the NeurIPS community.

Main Comments:
1) I found the paper rather notationally dense, and, in my opinion, the paper would benefit from providing more intuition in several places, especially around the definition (Definition 1.2) of the barycentric projection, the loss function (Eq. (1.8)), and the main result (Theorem 2.1). It would be helpful, for example, if there was some prose describing why Eq. (1.8) is a good loss function to upper bound, and what the roles of the terms appearing in Inequality (2.1) are.

2) In Theorem 2.4, it seems that the exact rate at which the bandwidth h_n vanishes does not affect the ultimate convergence rate, as long as it is slower than (log(n)/n)^{-1/(2s+d)}. It seems counterintuitive to me that a very large bandwidth, e.g. h_n = 1/log(n), would not slow the convergence rate. Could the authors provide any intuition for this phenomenon?

Minor Comments:
1) Line 40: The sentence "T_{m,n} converges at a rate of m^{-2/d} + n^{-2/d}" isn't really meaningful unless a loss or error metric is specified. Especially for nonparametric problems such as this, different metrics likely lead to different convergence rates. Hence, I suggest adding a brief description of the error metric here, or at least pointing the reader to Eq. (1.8).
2) In several places, such as Eqs. (2.1) and (2.2), it is impossible to visually distinguish the \overline's and \tilde's over \mu and \nu without zooming in quite a bit. This left me confused for a while trying to figure out the difference. Is it possible to make these notations more visually distinct?
3) Line 78: Typo: "distributions on X_1, . . . , X_m" -> "distributions of X_1, . . . , X_m"
4) Could the authors comment on how specific the results in this paper are to 2-Wasserstein, as opposed to general p-Wasserstein, distances?
limitations_and_societal_impact: The paper gives a reasonable discussion of its limitations. I don't foresee any potential negative societal impact of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This article proposes a study on the rates of estimation of Brenier maps using the plug in "barycentric mapping" estimator. As a consequence of this study authors obtain rates of convergence for $W_2^{2}$ in various context (depending on the regularity of the measures and on the setting: discrete-discrete of semi-discrete). They apply their results for Wasserstein barycenter estimation and Nonparametric independence testing.

main_review: On the one hand, from a theoretical point of view, I find the different results very interesting  on the other hand I find that this article does not really fit in the scope of a machine learning conference. Moreover I think that the article could benefit from an improvement in its writing (see below).

Overall the introduction and the problem are well presented. The main result is also quite interesting: it justifies the use of barycentric mapping as an "approximation" of the optimal Monge map. This result has many practical consequences, especially when barycentric mapping is used as a proxy for the Monge map (as in [1,2,3] or in domain adaptation where barycentric mapping is at the heart of many methods e.g. [4]). This opens, in my opinion, many practical perspectives. It also offers new justifications for the recent results concerning the estimation of $W_2^{2}$.

My main criticism concerning this article is that it does not really fit, in my opinion, in the scope of a machine learning conference but is more adapted to a "mathematical journal" format such as Annals of Statistics. First, no experience is given in the paper. I understand the purpose of purely theoretical papers but I think that a ML paper should contain at least one or two small experiments validating/illustrating the different approaches when possible (see my last comment). 

More importantly, the majority of the paper's contributions are in fact in supplementary material which is exclusively made up of proofs, quite specific and complex. So the paper is not really 8 pages long, but more like 20 pages of quite extensive mathematics. Consequently, given the time constraints inherent to NeurIPS, it seems to me quite reasonable to say that most ML reviewers cannot certify that all the proofs in such a paper are correct. Since these proofs are the main core of the paper, it is reasonable to think that it is difficult to judge the quality of the paper in such a setting. This argument would be invalid, however, if the above mentioned proofs were written with care and with a bit of hand-holding. However, the paper contains a lot of proofs without context or discussion and some "proofs by omission" based on other results. 

Indeed, the proofs are not self-contained, making the task of reviewing them very difficult, even for someone used to handling the tools of optimal transport. There are many calls in the proofs to results/equations of other papers without discussion or context. In the different proofs of the supplementary, there are no less than 12 calls to other results, which is, I think, a lot ("see Proposition 2 in [16]", "see Theorem 2.10 in [7]", "Note that by [15, Equation 26]"). Although it is common to write a proof by appealing to other results, this is usually the case when the result is "somewhat known" or by explaining a bit the outline of these results. In many cases here, these results are very specific and are not discussed. It is also difficult to say, without reading the whole articles in question, if the assumptions of the different theorems referred to are really applicable in these specific cases. For example  [13, Theorem 17] for Step I of the supplementary (row 95) calls for a theorem which itself has many assumptions and it is difficult to see if these assumptions are validated here, because no explanation or context is given. Some other proofs are not very elaborated (row 79-80) "The general strategy to bound the term in (A.20) is derived from some intermediate steps in the proofs of [5, Lemmas 3 and 4]. We still present a sketch here for completeness."

Finally, the paper ends  on a theorem without any conclusion, which I find rather clumsy. No discussion or perspective is given about the "Application" part (which is actually another theoretical part). For example, it is rather difficult to understand the interest of the "Nonparametric independence testing" section: what is "the permutation principle as is necessary for the usual HSIC" ? Why understanding "the local power of $\phi_{n,\alpha}$; under "changing sequence of alternatives converging to the null" " is a practical, interesting problem ? 
In this section, for example, it would have been valuable to include a small experiment showing the interest of the main result for this problem. Another question that could be interesting is the practical comparison between the barycentric mapping estimator compared to the "Sinkhorn divergence" one of (Chizat, 2020). It seems to me that it is somehow harder to compute the barycentric mapping, since this is a standard OT problem, while the Sinkhorn divergence is easier due to the regularization and the complexity of Sinkhorn’s algorithm. On the other hand, for real data, maybe the estimator based on the barycentric mapping would better behave ?

For all these reasons I rather recommend rejecting this paper. I find the results interesting but I don't think it is, as it stands, a suitable paper for a Machine Learning conference. I admit that some of my comments are quite subjective ("what a ML paper should be") so I am wiling to change my opinion.

[1] Michaël Perrot, Nicolas Courty, Rémi Flamary, Amaury Habrard. Mapping estimation for discrete optimal transport
[2] Vivien Seguy, Bharath Bhushan Damodaran, Rémi Flamary, Nicolas Courty, Antoine Rolet, Mathieu Blondel. Large-Scale Optimal Transport and Mapping Estimation
[3] Elsa Cazelles, Felipe Tobar, Joaquin Fontbona. Streaming computation of optimal weak transport barycenters
[4] Nicolas Courty, Rémi Flamary, Amaury Habrard, Alain Rakotomamonjy. Joint Distribution Optimal Transportation for Domain Adaptation

----- After Rebuttal -----

I thank the authors for their response. After reading the rebuttal I decided to increase my score to 5. I agree that this paper proposes interesting new theoretical results and I agree with the other reviewers on this point. However, I think it would benefit from a rewrite of the proofs (to be as self-content as possible since it is the core of the paper) and of the "Application" part which does not seem to me to be detailed enough as it is. I also think that this paper deserves a conclusion in order to give some perspective on the different results. That's why I don't increase my final grade more widely. However, I do not object to the acceptance of this paper.
limitations_and_societal_impact: Authors did not provide any potential negative societal impact of their work however, it is difficult for me to foresee these impacts..
review_title: null

Meta-review: All the reviewers insisted on the high quality of the theoretical results, even if some numerical simulations would have been welcome (these could have been provided in the supplementary material). They also appreciated the quality of the rebuttal, which clarified some important questions. Some raised the issue that the part of the proof in the supplementary was lacking clarity and details, and this should be improved in the final version. I thus strongly urge the authors to take into account the feedback of the reviewers to improve the quality of the paper. For these reasons (lacks of numerical simulation and clarity of the proofs), after a discussion with the reviewers and in agreement with them, I decided to support acceptance but not for a spotlight. 
Decision: Accept (Poster)