Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper uses Lebesgue transform to give the semi-dual Brenier objective as the quantitative criterion for convex potential selection .
This criterion enables parameter tuning and model selection among entropic regularization of OT, input convex neural networks(ICNN) and smooth and strongly convex nearest-Brenier (SSNB) models.
The authors also use this criterion to question the use of OT in Domain-Adaptation.
strengths_and_weaknesses: Strengths: this paper uses Lebesgue transform to give the semi-dual objective as the quantitative criterion . The theoretical derivation and experiments show the effectiveness of the method. 
This paper has been proved by experiment that the map minimizing the semi-dual, hence the closest to the ground truth OT map, is often far from being the one that achieves the best label transfer.
Weakness: (Page 8,paragraph 2)The authors claimed the choice of network structure may lead to poor ICNN performance,which needs more experimental verification. 
questions: How to ensure that the final model selection is accurate if the performance of ICNN is not optimal? 
limitations: They proposed the limitation of their algorithm, but doesn't address the potential negative societal impact .
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: Given two measures $\mu$ and $\nu$, and a set of estimated potentials (from the dual formula in Optimal Transport theory) between them, the paper provides a criterion to select the potential having a corresponding pushforward map (derivative) being closest to the Monge map. Thanks to the assumptions of strong convexity and smoothness of the potentials, and Bernstein-typed of inequalities, we can provide the theoretical bounds for error of this method non-asymptotically (Lemma 1 and Proposition 2). Some experiments and applications are provided to support the method and theory. It also gives a good negative finding to Optimal Transport Domain Adaptation models that the best Domain Adaptation map is not close to the Monge map in several applications.
strengths_and_weaknesses: **Strength**: 

1. The idea of this paper is natural and good. From a naive perspective, it is natural to select the potential as the one optimizing the dual formulation. The theory from this paper supports this viewpoint, and the experiments empirically show it is effective. The take-away lesson in the paper is valuable to Optimal Transport and Domain Adaptation researchers.

2. The presentation of the paper is clear, the story is well-motivated, and the experiments part is carefully carried out.

**Weakness**: 

1. There are still many typos in the manuscript. For example, in the caption of Figure 1: "pic", in line 208: "conidtion", and in line 209: "argmin" (instead of argmax).

2. Some of the arguments and theoretical results appear to be not correct (see Questions).

3. To make the presentation of the paper more fluent, I think the authors should merge Section 4 and Section 5.1 because they both talk about finding potentials. The paragraph "Self-concordant potentials" is not clearly written about how we can obtain the conjugate via the second-order method. It is better to just present the method to find the conjugate and a theoretical result about its sample complexity (combination of Definition 1 and Proposition 7) instead of introducing a new notion (generalized self-concordant). A detailed explanation can be put in the appendix.
questions: 1. The calculation in Proposition 1 seems to be not correct. Because in the OT dual formula, the constraint $\phi(x) + \psi(x) \leq (x-y)^2/2$ only needs to satisfy in the $Support(\mu)\times Support(\nu)$. Similar to constraint of the potentials $f(x) + g(y) \geq xy$. Therefore, in this case, because both the support of $\mu$ and $\nu$ are compact, we can not use the definition of Fenchel-Legendre on the whole domain $\mathbb{R}$ (but with respect to $[-1/2, 1/2]$ only). This potentially relates to other results and proofs in this paper. 

2. Similar to the synthetic experiment, the Domain Adaptation experiment also needs to run with a few replications. The result should be then more reliable. When we learn the transport map $T$ from training data and evaluate potentials on the test data, how can we make sure that the distribution of the training and test data are the same? The experiment description should be more clear in this aspect.
limitations: While the research question is interesting, the approach is good and natural, it appears to have several points that can be improved in this paper, both in terms of theory and experiments (see above). I suggest the authors examine those points carefully and make the paper better.
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 proposes a novel criterion to evaluate how close an estimated (L2 Wasserstein) optimal transport plan between two given measures is close to the true (unknown) optimal transport plan. To do so, the authors rely on the semi-dual formulation of the Kantorovich problem, and prove that the objective function for this formulation (using discrete measures with n points) is highly correlated with the L2 distance between the estimated transport plan and the true one (and give bounds). The authors require that the potential to be estimated has a Lipschitz gradient, and the true potential is strongly convex. When those criteria are met, the semi-dual objective is finite and can be used as a proxy for the distance to the optimal map. The authors show that the map minimizing this criterion are related to the distance between the true map and the closest one, through an inequality involving a factor depending on the regularity of the estimated map. When the regularity criteria are not met, the authors argue that the potentials can be regularized using an additive quadratic term for the semi-dual objective to be computable. The criterion can be used for hyperparameter tuning in various OT algorithms (including Sinkhorn iterations, that do not natively satisfy the requirements), or to evaluate whether performance for a downstream task (here domain adaptation) correlates or not with OT performance. Somewhat surprisingly, performance on a DA task does not correlate with the quality of the OT map.
strengths_and_weaknesses: Strengths :

- The authors propose a conceptually simple way to rank candidate estimated OT maps in terms of how well they approximate the true map, without using the latter. This could be potentially very useful to compare algorithms in the future, or to check on pratical cases whether or not optimal transport is a good constraint to add to improve performance on a given downstream task.

- The theoretical developments are well presented and the empirical results are well illustrated by the experimental results. Namely the regularity in practice of the potentials is well shown (on simple computable examples and when comparing the different algorithms) to be crucial for the proposed semi-dual criterion to be computable and more importantly reliable.

- The approach can be applied in practical case where the semi-dual would normally not be useful (infinite) thanks to small regularizations providing the necessary smoothness and strong convexity. This in particular makes the approach applicable (and tractable thanks to efficent ways to compute the Legendre transform) to Sinkhorn models which are among the most common.

- The Domain Adaptation experiment provides interesting nsight on this problem and answers at least partially to the question of how useful OT is in this situation.

Weaknesses :

- The presentation and motivation foir presenting some of the propositions and theorems could be improved (See below for details on this point)

- The results on domain adaptation, given their potential consequences on the applicability of OT to this problem, would probably have to be confirmed on another case study, either on another real dataset, or maybe a low dimensional toy dataset (where maybe the optimal transformationis knwon) for this result to be strengthened.
questions: - It would be quite informative to check the bound validity on practical cases where everything is known (e.g OT between gaussians, where gamma and M, and T0 can be explicitly computed, or even the synthetic experiments with a quadratic potential). Examples in 1D such as the one illustrated in Fig. 1 (which is never really discussed beyond the introduction, though it brings the point across nicely) could also have been explored in more detail.

- On a related note, the bound provided in equation one is particularly interesting, since even if the function minimizing the semi-dual criterion has a small smoothness coefficient (M), the ratio M/gamma cannot become smaller than one (in the non-stochastic case). This would contradict the optimality of the model in the RHS. Are there results on this or do the authors have some insight on the interplay between the smoothness of f0 and the strong convexity of f1 ? Would it be for example possible to have an idea of the optimal model if only those constants are known, without computing the semi-dual criterion ?

- Why does the number of candidate models vary so much from one model to the next ? There are only 5 hyperparameter values for the Sinkhorn potentials, while the method is quite fast to train and the number of candidate models could have been higher.

- I checked [Caffarelli 2000] but could not find exactly what result was being referenced in theorem 1, but I could have missed something. Can the authors provide the exact reference to the theorem and its proof? Besides, the conclusion that under the hypotheses of this theorem, the Brenier potentials are smooth and strongly convex are not obvious to me and could deserve some explanation (the theorem only states they are convex and C2). Also, what happens for continuous measures with non compact support (e.g. Gaussians) ?

- The counter examples (propositions 1 and 3) are a bit abrupt and would benefit a bit more contextualization. For example, proposition 3 aims at showing in a practical case that the bound is tight in the infinite samples regime. But isn’t this a general result, valid for any case as long as n goes to infinity ? I am not sure what the example brings exactly. 
limitations: The authors point out that the conditions required for the semi dual to be both finite and reliable in terms of correlating with the OT performance may be restrictive in some cases.
For Sinkhorn models, they resolve this in practice via quadratic regularizations and suggest useful bounds could be obtained under less strong regularity conditions. 
They also show experimentally that the critetion may not correlated with OT performance when the regularity of the obtained potentials cannot be controlled (as in ICNNs).
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a sample-based criterion to select the best convex Brenier potential among the list of available ones for the Wasserstein-2 optimal transport. The criterion is based on the theoretical result (lemma 1) which connects the semi-dual Brenier formulation of OT and the L2 error between the gradient of the approximate potential and the OT map. The main idea of the criterion is to simply take the potential for which the empirical semi-dual is the smallest: for this potential, one may guarantee that its gradient will not be far from the best available OT map (Proposition 2). The authors provide some quantitative evaluation in small dimensional spaces to illustrate that the potential selected by their criterion is good (they use SSNB, ICNN-based and Sinkhorn algorithms to get the candidate potentials). Also, they conduct a domain adaptation experiment to show that that the improved accuracy of computing the OT may does not necessarily yield increase in DA accuracy metric.

strengths_and_weaknesses: **Strength.** To my knowledge, there is no closely research related to model selection for optimal transport. The current paper seems to be the first who studies this question and proposes an approach to model selection in W2 optimal transport. It derives an upper bound on the empirical semi-dual error and provides an example showing that it is tight (in the non-stochastic regime).

The domain adaptation experiment also raises an interesting and important question: is it reasonable to apply OT in DA problems? Emphasizing and discussing this question might be interesting to the ML/OT community. The current paper shows that better DA performance not necessarily correlates with the OT performance, which points to a gap between computational OT and downstream applications.

**Weaknesses.** I think the paper has several important flaws.

*(1) Clarity.* The overall exposition, writing and presentation could be improved. First, most of the equations are in-line formulas which makes it hard to read the paper. Next, there is simply no introduction to the optimal transport problem: an unprepared reader without significant experience in OT (especially in W2 OT related to the Brenier formulation) will struggle to understand the message of this paper. In the paper, the OT problem has never been formally defined, only its dual is considered. Due to this, it might be hard to understand how all these derivations are related to the domain adaptation problem studied later (why the gradient of the OT potential is a meaningful mapper for DA problem?). In general, it is not trivial to follow the stream of thoughts of the authors: there is limited discussion of the meaning of propositions/theoretical results and transition between them. For example, in my view, the main criterion is not clearly stated: how to apply it in practice? (Note: this could be understood from the experimental section, but I think the authors should devote a separate paragraph for this to make it clear).

*(2) Main contribution.* While the idea is novel, but one might argue that it is rather straightforward from the theoretical point of view. Indeed, the key proposition 2 follows from lemma 1 (which is a already known result in W2 optimal transport) and Hoeffding lemma (the authors themself note this in line 168).

*(3) Related work.* Most of the related work seems to be resonably covered. However, in some cases whether the provided results are new or they already exist. For example, as a reader, I do not understand whether results in section 4 are novel or it is just a discussion of some related OT background with illustrations. In the discussion of the related methods 246-252, it is not straightforward to come up with the optimization objective of line 248. The authors could have repeated a reference to the original method’s paper. Same applies to SSNB method (253-256). How to optimize this objective? Additional details and clarifications could be useful (in the main text (!), not appendix). Besides, there is a work [1] which is not cited in the current paper although it seems to be closely related as its authors also discuss the necessity to use strongly convex/smooth potentials (which is heavily relied on the current paper). Also, lemma 1 (which the authors use) is also present in [1]. 

[1] Korotin, A., Egiazarian, V., Asadulaev, A., Safin, A., & Burnaev, E. (2021). Wasserstein-2 Generative Networks. In International Conference on Learning Representations.

*(4) Experiments.* The synthetic experiments seem to be a little bit limited. I think the authors should consider more examples and in different dimensions (not only d=8) to study the practical usefulness of their criterion. In the current form, the evaluation (Tables 2, 1, 3) is not sufficiently convincing.

Relevance of DA experiments. As I noted earlier, the OT DA part of the paper raises and discusses an interesting question: is the OT map a valid adaptation map in DA? While the question is important, I would argue that the answer to the question is just obvious: for some dataset pairs OT map may be a meaningful, for some - not. In particular, I have checked three papers that the authors cite [Courty et al., 2017], [Redko et al., 2019], [Xu et al., 2020]. If I understand correctly, the methods are mostly discrete (they are not interested in the dual potentials as functions contrary to the current work) and their authors typically propose costs/regularization to make the mapping obtain desired properties instead of  using the “raw” W2 cost (which is studied here) [between features]. Thus, the DA experiment in the current paper is a nice illustration of their criterion but is note very significant.

To conclude, I think the most serious weaknesses are (1) [clarity] and (4) [experimental evaluation].

questions: Incorporated to the previous part.

**Note:** My assessment is mostly based on the main text. I have looked through the main text + briefly looked through appendices. I did not run the code of the supplementary and did not check the proofs of appendices.
limitations: There is no separate section of paragraph with limitations, but some of them are discussed in the text, e.g., the necessity to consider smooth/strongly convex potentials.

Another important limitation, which seems not to be discussed in the paper, it the fact that the proposed criterion significantly relies on the brenier OT formulation, convexity of the dual potentials, Fenchel transform, etc. Thus,
(1) the same analysis/ideas would presumably not generalize to other OT transport cost functions beyond W2 (quadratic cost);
(2) the application of the criterion requires convex potentials which are in practice are either ICNNs or LSE functions (in the Sinkhorn case), which are both very restrictive. It is unclear whether these architectures will perform perform well in practical tasks.

It would be great if the authors could carefully discuss these important limitations in the answers and speculate on possible ways to overcome them.

**Post-rebuttal:** I increase my score from 4 to 5.
review_title: null

Meta-review: metareview: While there were few misunderstandings, the rebuttal successfully convinced all the reviewers that the paper should be accepted. Please take into account the reviewers' comments in preparing the camera-ready, especially the ones concerning the clarity of the paper.
confidence: Certain
Decision: Accept