Mapping Estimation for Discrete Optimal Transport
We are interested in the computation of the transport map of an Optimal Transport problem. Most of the computational approaches of Optimal Transport use the Kantorovich relaxation of the problem to learn a probabilistic coupling γ but do not address the problem of learning the underlying transport map T linked to the original Monge problem. Consequently, it lowers the potential usage of such methods in contexts where out-of-samples computations are mandatory. In this paper we propose a new way to jointly learn the coupling and an approximation of the transport map. We use a jointly convex formulation which can be efficiently optimized. Additionally, jointly learning the coupling and the transport map allows to smooth the result of the Optimal Transport and generalize it to out-of-samples examples. Empirically, we show the interest and the relevance of our method in two tasks: domain adaptation and image editing.
The authors study the optimal transport problem, motivated by the desire to come up with a model which better generalizes to unseen examples. Standard techniques do not generalize as the transport map is not defined for new data and needs to be recomputed whenever new data point is obtained. To this effect, the authors propose an optimization model which enables the joint learning of the transport map and the probabilistic coupling. The (visual) advantages of the new model are validated on domain adaptation and image editing (face swapping) problems. The objective/loss function in new model is, by design, jointly convex in the two variables (transport and coupling), and an alternating minimization method is employed to solve it.
1) The paper reads well and the new model for joint optimization of transport and coupling looks promising. The computational approach satisfactorily demonstrate the usefulness of the new model and the solution approach.  2) The authors compare to the work of Perez  et al [28] which dates back to 2003. Was there no progress in the field in the last 13 years? A detailed commentary on why comparison is done against [28] and why not against newer approaches is needed. 3) It should be explained in words what (1) means, also explaining each term appearing in (1).  The current text does not explain the meaning well. It was not explained what notation # means; all used notation should be explained for the paper to be accessible to a wider audience.  4) What is {\cal P} in Line 75? This was not explained – notation is used without any word of warning or advice. 5) Equation (4) should be explained in more detail to a lay audience. What is being mapped to what? Are we mapping index i to   x\in \Omega? What is \Omega (this was never defined)?  6) Line 93: Why do you focus on uniform samplings? What do you mean by uniform samplings? This should be explained at more length as it seems to be a critical assumption/limitation of focus. 7) The choice and meaning of the various constants appearing in the new model (6) is not discussed. For instance, why should one normalize by max(C)? After all, lambda_\gamma can account for this. Why should one normalize the regularizer by d^2? Again, \lambda_T can absorb this term. How about the factor of 1/d in front of the first term?  8) On lines 116-118 it is claimed that since the loss in (6) is jointly convex, alternating optimization will converge to the optimal solution. First of all, you need to prove that an optimal solution exists (first argue boundedness below by 0, and so on). Second, even if optimal solution exists, alternating optimization (or block coordinate descent with 2 blocks) need not converge. A simple example of this is min max{|x_1|, |x_2|}. Starting from  x=(x_1,x_2) = (1,1), no coordinate direction leads to descent. Hence, the method can get stuck at a non-optimal point. This illustrates that additional conditions to convexity are needed for block coordinate descent to work. Are these satisfied for this function? The paper would be much stronger if this was established. 9) I do not understand the assumption on H in Theorem 1. The assumption seems to be a definition of convex combination of 2 functions. Hence, it is not an assumption! What should be assumed is that H is itself convex. 10) The only theoretical result in the paper, Theorem 1, is a trivial observation.  The paper contains a number of typos and English usage issues; some of which are listed below. The authors should re-read the paper and do corrections. In general though, the paper is well written.  1) Line 29: bound -> bounds 2) Line 31: Most of -> Most 3) Line 36: from -> for 4) Line 37: have -> find 5) Line 47: to an -> to 6) Line 51: easily kernelized that -> easily kernelized, which 7) Line 53: evidence on -> evidence for 8) Line 54: interest -> usefulness 9) Line 54: on domain -> in domain 10) Line 56: remaining -> rest 11) Line 71: assuming for -> assuming 12) Line 73: of the -> of 13) Eq (2) should end with a full stop 14) Line 77: writing -> formulation 15) Eq (3) should end with a comma 16) Line 86: computed ->computed, 17) Eq (4) should end with a comma 18) Eq (4): Presumably, \Omega should be replaced by \Omega_{\cal S} 19) Line 93: an -> a 20) Line 93: hence -> , whence 21) Eq (6): Defined max(C) – is this the maximal element in matrix C? This was not defined 22) Eq (6) should end with a comma 23) Line 111: the -> The 24) Line 114: a block -> block 25) Line 114: [16] where -> [16], where 26) Line 122: block coordinates approach -> block coordinate descent approach 27) Line 125: problems -> problem  I stopped checking for typos beyond this – but I expect the same frequency in the rest of the paper. Please correct them all.  I just did a very cursory check beyond this in the Supplementary: 1) Line 3: Theorem -> theorem 2) Line 9: closeness -> proximity 3) Second inequality after line 14 should be an equality  Bibliography:  [5, 6, 14, 21, 27]: wasserstein -> Wasserstein [7]: bregman -> Bregman [16]: capitalize journal name [19]: frank-wolfe -> Frank-Wolfe  Similar issues appear in biblio for the supplementary part.  ---- post-rebuttal remarks -----  I have read the other reviews and the rebuttal and as a result keep my scores unchanged.