Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper proposes a new method for estimating optimal transport plans and maps among continuous distributions, or discrete distributions with large support size. First, the paper proposes a dual algorithm to estimate Kantorovich plans, i.e. a coupling between two input distributions minimizing a given cost function, using dual functions parameterized as neural networks. Then an algorithm is given to convert a generic plan into a Monge map, a deterministic function from one domain to the other, following the barycenter of the plan. The algorithms are shown to be consistent, and demonstrated to be more efficient than an existing semi-dual algorithm. Initial applications to domain adaptation and generative modeling are also shown.

These algorithms seem to be an improvement over the current state of the art for this problem setting, although more of a discussion of the relationship to the technique of Genevay et al. would be useful: how does your approach compare to the full-dual, continuous case of that paper if you simply replace their ball of RKHS functions with your class of deep networks?

The consistency properties are nice, though they don't provide much insight into the rate at which epsilon should be decreased with n or similar properties. The proofs are clear, and seem correct on a superficial readthrough; I have not carefully verified them.

The proofs are mainly limited in that they don't refer in any way to the class of approximating networks or the optimization algorithm, but rather only to the optimal solution. Although of course proving things about the actual outcomes of optimizing a deep network is extremely difficult, it would be helpful to have some kind of understanding of how the class of networks in use affects the solutions. In this way, your guarantees don't say much more than those of Arjovsky et al., who must assume that their "critic function" reaches the global optimum: essentially you add a regularization term, and show that as the regularization decreases it still works, but under seemingly the same kind of assumptions as Arjovsky et al.'s approach which does not add an explicit regularization term at all. Though it makes sense that your regularization might lead to a better estimator, you don't seem to have shown so either in theory or empirically.

The performance comparison to the algorithm of Genevay et al. is somewhat limited: it is only on one particular problem, with three different hyperparameter settings. Also, since Genevay et al. propose using SAG for their algorithm, it seems strange to use plain SGD; how would the results compare if you used SAG (or SAGA/etc) for both algorithms?

In discussing the domain adaptation results, you mention that the L2 regularization "works very well in practice," but don't highlight that although it slightly outperforms entropy regularization in two of the problems, it does substantially worse in the other. Do you have any guesses as to why this might be?

For generative modeling: you do have guarantees that, *if* your optimization and function parameterization can reach the global optimum, you will obtain the best map relative to the cost function. But it seems that the extent of these guarantees are comparable to those of several other generative models, including WGANs, the Sinkhorn-based models of Genevay et al. (2017, https://arxiv.org/abs/1706.00292/), or e.g. with a different loss function the MMD-based models of Li, Swersky, and Zemel (ICML 2015) / Dziugaite, Roy, and Ghahramani (UAI 2015). The different setting than the fundamental GAN-like setup of those models is intriguing, but specifying a cost function between the source and the target domains feels exceedingly unnatural compared to specifying a cost function just within one domain as in these other models.

Minor:

In (5), what is the purpose of the -1 term in R_e? It seems to just subtract a constant 1 from the regularization term.
review_title: Interesting idea for expanding optimal transport estimation, but some aspects unclear

final_score: rating: 7: Good paper, accept
review_content: Quality
The theoretical results presented in the paper appear to be correct. However, the experimental evaluation is globally limited,  hyperparameter tuning on test which is not fair.

Clarity
The paper is mostly clear, even though some parts deserve more discussion/clarification (algorithm, experimental evaluation).

Originality
The theoretical results are original, and the SGD approach is a priori original as well.

Significance
The relaxed dual formulation and OT/Monge maps convergence results are interesting and can of of interest for researchers in the area, the other aspects of the paper are limited.

Pros:
-Theoretical results on the convergence of OT/Monge maps
-Regularized formulation compatible with SGD
Cons
-Experimental evaluation limited
-The large scale aspect lacks of thorough analysis
-The paper presents 2 contributions but at then end of the day, the development of each of them appears limited

Comments:

-The weak convergence results are interesting. However, the fact that no convergence rate is given makes the result weak. 
In particular, it is possible that the number of examples needed for achieving a given approximation is at least exponential.
This can be coherent with the problem of Domain Adaptation that can be NP-hard even under the co-variate shift assumption (Ben-David&Urner, ALT2012).
Then, I think that the claim of page 6 saying that Domain Adaptation can be performed "nearly optimally" has then to be rephrased.
I think that results show that the approach is theoretically justified but optimality is not here yet.

Theorem 1 is only valid for entropy-based regularizations, what is the difficulty for having a similar result with L2 regularization?

-The experimental evaluation on the running time is limited to one particular problem. If this subject is important, it would have been interesting to compare the approaches on other large scale problems and possibly with other implementations.
It is also surprising that the efficiency the L2-regularized version is not evaluated.
For a paper interesting in large scale aspects, the experimental evaluation is rather weak.
 
The 2 methods compared in Fig 2 reach the same objective values at convergence, but is there any particular difference in the solutions found?

-Algorithm 1 is presented without any discussion about complexity, rate of convergence. Could the authors discuss this aspect?
The presentation of this algo is a bit short and could deserve more space (in the supplementary)

-For the DA application, the considered datasets are classic but not really "large scale", anyway this is a minor remark.
The setup is not completely clear, since the approach is interesting for out of sample data, so I would expect the map to be computed on a small sample of source data, and then all source instances to be projected on target with the learned map. This point is not very clear and we do not know how many source instances are used to compute the mapping - the mapping is incomplete on this point while this is an interesting aspect of the paper: this justifies even more the large scale aspect is the algo need less examples during learning to perform similar or even better classification.
Hyperparameter tuning is another aspect that is not sufficiently precise in the experimental setup: it seems that the parameters are tuned on test (for all methods), which is not fair since target label information will not be available from a practical standpoint.

The authors claim that they did not want to compete with state of the art DA, but the approach of Perrot et al., 2016 seems to a have a similar objective and could be used as a baseline.

Experiments on generative optimal transport are interesting and probably generate more discussion/perspectives.

--
After rebuttal
--
Authors have answered to many of my comments, I think this is an interesting paper, I increase my score.

review_title: The paper presents interestings results about consistency of learning OT/Monge maps although weak and stochastic learning algorithms able to scale, however some parts should deserve more discussion and experimental evaluation is limited.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper explores a new approach to optimal transport. Contributions include a new dual-based algorithm for the fundamental task of computing an optimal transport coupling, the ability to deal with continuous distributions tractably by using a neural net to parameterize the functions which occur in the dual formulation, learning a Monge map parameterized by a neural net allowing extremely tractable mapping of samples from one distribution to another, and a plethora of supporting theoretical results. The paper presents significant, novel work in a straightforward, clear and engaging way. It represents an elegant combination of ideas, and a well-rounded combination of theory and experiments.

I should mention that I'm not sufficiently familiar with the optimal transport literature to verify the detailed claims about where the proposed dual-based algorithm stands in relation to existing algorithms.

Major comments:

No major flaws. The introduction is particular well written, as an extremely clear and succinct introduction to optimal transport.

Minor comments:

In the introduction, for VAEs, it's not the case that f(X) matches the target distribution. There are two levels of sampling: of the latent X and of the observed value given the latent. The second step of sampling is ignored in the description of VAEs in the first paragraph.

In the comparison to previous work, please explicitly mention the EMD algorithm, since it's used in the experiments.

It would've been nice to see an experimental comparison to the algorithm proposed by Arjovsky et al. (2017), since this is mentioned favorably in the introduction.

In (3), R is not defined. Suggest adding a forward reference to (5).

In section 3.1, it would be helpful to cite a reference to support the form of dual problem.

Perhaps the authors have just done a good job of laying the groundwork, but the dual-based approach proposed in section 3.1 seems quite natural. Is there any reason this sort of approach wasn't used previously, even though this vein of thinking was being explored for example in the semi-dual algorithm? If so, it would interesting to highlight the key obstacles that a naive dual-based approach would encounter and how these are overcome.

In algorithm 1, it is confusing to use u to mean both the parameters of the neural net and the function represented by the neural net.

There are many terms in R_e in (5) which appear to have no effect on optimization, such as a(x) and b(y) in the denominator and "- 1". It seems like R_e boils down to just the entropy.

The definition of F_\epsilon is made unnecessarily confusing by the omission of x and y as arguments.

It would be great to mention very briefly any helpful intuition as to why F_\epsilon and H_\epsilon have the forms they do.

In the discussion of Table 1, it would be helpful to spell out the differences between the different Bary proj algorithms, since I would've expected EMD, Sinkhorn and Alg. 1 with R_e to all perform similarly.

In Figure 4 some of the samples are quite non-physical. Is their any helpful intuition about what goes wrong?

What cost is used for generative modeling on MNIST?

For generative modeling on MNIST, "784d vector" is less clear than "784-dimensional vector". The fact that the variable d is equal to 768 is not explicitly stated.

It seems a bit strange to say "The property we gain compared to other generative models is that our generator is a nearly optimal map w.r.t. this cost" as if this was an advantage of the proposed method, since arguably there isn't a really natural cost in the generative modeling case (unlike in the domain adaptation case); the latent variable seems kind of conceptually distinct from observation space.

Appendix A isn't referred to from the main text as far as I could tell. Just merge it into the main text?




review_title: Very strong paper with novel and interesting results presented clearly and engagingly.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper proves the weak convergence of the regularised OT problem to Kantorovich / Monge optimal transport problems.

I like the weak convergence results, but this is just weak convergence. It appears to be an overstatement to claim that the approach "nearly-optimally" transports one distribution to the other (Cf e.g. Conclusion). There is a penalty to pay for choosing a small epsilon -- it seems to be visible from Figure 2. Also, near-optimality would refer to some parameters being chosen in the best possible way. I do not see that from the paper. However, the weak convergence results are good.

A better result, hinting on how "optimal" this can be, would have been to guarantee that the solution to regularised OT is within f(epsilon) from the optimal one, or from within f(epsilon) from the one with a smaller epsilon (more possibilities exist). This is one of the things experimenters would really care about -- the price to pay for regularisation compared to the unknown unregularized optimum. 

I also like the choice of the two regularisers and wonder whether the authors have tried to make this more general, considering other regularisations ? After all, the L2 one is just an approximation of the entropic one.

Typoes:

1- Kanthorovich -> Kantorovich (Intro)
2- Cal C <-> C (eq. 4)
review_title: An interesting paper on large scale optimal transport, though "overstating" some properties 

Meta-review: This paper is generally very strong. I do find myself agreeing with the last reviewer though, that tuning hyperparameters on the test set should not be done, even if others have done it in the past. (I say this having worked on similar problems myself.) I would strongly encourage the authors to re-do their experiments with a better tuning regime.
Decision: Accept (Poster)