LARGE-SCALE OPTIMAL TRANSPORT AND MAPPING ESTIMATION
This paper presents a novel two-step approach for the fundamental problem of learning an optimal map from one distribution to another. First, we learn an optimal transport (OT) plan, which can be thought as a one-to-many map between the two distributions. To that end, we propose a stochastic dual approach of regularized OT, and show empirically that it scales better than a recent related approach when the amount of samples is very large. Second, we estimate a Monge map as a deep neural network learned by approximating the barycentric projection of the previously-obtained OT plan. This parameterization allows generalization of the mapping outside the support of the input measure. We prove two theoretical stability results of regularized OT which show that our estimations converge to the OT plan and Monge map between the underlying continuous measures. We showcase our proposed approach on two applications: domain adaptation and generative modeling.
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.