Extremal Domain Translation with Neural Optimal Transport
Authors: Milena Gazdieva
Alexander Korotin
Daniil Selikhanovych
Evgeny Burnaev
Venue: NeurIPS 2023 poster (2023)
Keywords: optimal transport
partial optimal transport
neural networks
domain translation

Abstract: In many unpaired image domain translation problems, e.g., style transfer or super-resolution, it is important to keep the translated image similar to its respective input image. We propose the extremal transport (ET) which is a mathematical formalization of the theoretically best possible unpaired translation between a pair of domains w.r.t. the given similarity function. Inspired by the recent advances in neural optimal transport (OT), we propose a scalable algorithm to approximate ET maps as a limit of partial OT maps. We test our algorithm on toy examples and on the unpaired image-to-image translation task. The code is publicly available at https://github.com/milenagazdieva/ExtremalNeuralOptimalTransport

Extremal Domain Translation with Neural Optimal Transport
Milena Gazdieva'
Alexander Korotin'
Skolkovo Institute of Science and Technology
Skolkovo Institute of Science and Technology Artificial Intelligence Research Institute Moscow, Russia
Moscow, Russia
milena. waleeaaaaazdieea@aakoteeee
a. wwkokiinskolteehhhcc.o
Daniil Selikhanovych
Evgeny Burnaev
Skolkovo Institute of Science and Technology
Skolkovo Institute of Science and Technology Artificial Intelligence Research Institute Moscow, Russia
Moscow, Russia
s0l1khanoovychaani1@@g.al..
e. burnaev@skoltech.c.. ru
Abstract
In many unpaired image domain translation problems, e.g., style transfer or super- resolution, it is important keep the translated image similar to its respective input image. We propose the extremal transport (ET) which a mathematical formalization of the theoretically best possible unpaired translation between pair of domains w.r.t. the given similarity function. Inspired by the recent advances in neural optimal transport (OT), we propose scalable algorithm approximate ET maps as a limit partial OT maps. We test our algorithm on toy examples and on the unpaired image-to-image translation task. The code is publicly available at
https: htt::///iiie //tthub..tt..../// com/ htw.ll/gggeatioottttt/maaaaaaaaa
X-P
x
700)
W -1
1
f(x)
w =
fix)
W. -2
T(x)
I' similarity
w
f(x)
T(x)
w
W
Tux)
W 8
T(x)
W = 8
(a) Handbag + shoes (128 x 128).
(b) Celeba (female) - anime (64 64).
Figure I: (Nearly) extremal transport with our Algorithm 1 Higher yields bigger similarity and T(xx) 82
Introduction
The unpaired translation task 72 Fig. 2] to find a map + T(x), usually neural network. which transports the samples from the given source domain to the target domain. The key challenge
Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

here is that the correspondence between available data samples z from the source and from target domains is not given. Thus, the task is ambiguous as there might exist multiple suitable T.
When solving the task, many methods regular- ize the translated samples T(x:) to inherit spe- cific attributes of the respective input samples x. In the popular unpaired translation [72 Fig. 9] and enhancement [99 Equation 3] tasks for images, it is common to use additional unsuper-
0.0
c.5
vised identity losses, e.g.. [[T(z) 2 to make the translated output (z) similar to the input images x. The same applies, e.g., to audio trans- lation [1.. Therefore, the learning objectives of such methods usually have two components. The first component is the domaín loss (main) enforcing the translated sample T(x) to look like the samples y from the target domain. The second component is the similarity loss (regularizer, optional) stimulating the translated (xx) to inherit certain attributes of input z. A question arises: can one obtain the maximal similarity of T(x) to but still ensure that T(x) is indeed from the target domain? A straightforward "yes, just increase the weight of the similarity loss" may work but only to a limited extent. We demonstrate this in Appendix C
-20-
Irout x
-5
Target
Mapuoaily mag
-1.0
0.0
-10 -0.5
10
Figure 2: Learned transport map (w 2) in 'Accept' task.
Contributions. In this paper, we propose the extremal transport (ET, (3.1) which is a rigorous mathematical task formulation describing the theoretically best possible unpaired domain translation w.r.t. the given similarity function. We explicitly characterize ET maps and plans by establishing an intuitive connection to the nearest neighbors (NN). We show that ET maps can be learned as limit ($3.3) of specific partial optimal transport (OT) problem which we call incomplete transport (IT, $3.2p. For IT, we derive the duality formula yielding an efficient computational algorithm ($3.4). We test our algorithm on toy 2D examples and high- nigh-dimensional unpaired image translation ($5)
Notation. We consider compact Polish spaces (X, Ilx). (2,, I1ll)) and use P(X), P()") to denote the sets of Radon probability measures on them. We use (+) C CM(X) to denote the sets of finite non-negative and finite signed (Radon) measures on X. respectively. They both contain P(X) as a subset. For a non-negative μ E MM its support is denoted by Supp(H) C. X. It is a closed X' for which every open neighbourhood A a satisfies u(A) > 0. We use C(X) to denote the set of continuous functions X + R equipped with || -1.so norm. Its dual space is M(X) equipped with the ||- ||х norm. A sequence μl, P2, E M(X) is said to be weakly-* * converging to μ E M(X)) if for every f E C(X) it holds that lim Jx f(x) Sx J (x))de' (x)) For probability measure π E P(X's x )), we use T. E P(X) and Ty E PPY)) denote its projections onto X, V. respectively. Disintegration of x yields dz y) = dr (y)d( where π (y]a:)) denotes the conditional distribution of y ) for given x E X. For J, E M()). we write μ S V if for all measurable A C y it holds that μ(A) I v(A). For a measurable map T: X - D, we use Ttt denote the associated pushforward operator P(X) P(Y).
set consisting of all points
2 Background on Optimal Transport
In this section, we give an overview of the OT theory concepts related to our paper. For details on OT, we refer to (62 65 56), partial OT [22 [0].
Standard OT formulation. Let c X' x y + R be a continuous cost function. For IP E P(()),
Q E P()), the OT cost between them given by
Cost(IP, Q)
def
inf T1==Q / (())
where inf is taken over measurable T X + y pushing IP to Q (transport maps), see Fig. Problem ( is called the Monge's OT problem, and its minimizer T is called an OT map.
3a
In some cases, there may be no minimizer T' of (.. Therefore, it is common to consider Kan- torovich's 's relaxation:
(P, Q) def
inf / c(x, V)d (x, xEII(P.0)
xxx
where inf is taken over т E P(X x y) satisfying Te = P and Fy = Q, respectively. A minimizer
n E IIP, Q) in Q always exists and is called an OT plan. A widely used example of OT cost for
X y = d is the Wasserstein-1 I distance (W1). 1). i.c., OT cost (2) for c(2, v) = || bll.
2

---

fc(x)x)dntty1c)
c(x:.T(x:))
X1
T(x:)
X1
n(yp)))
c(Xe,T(X:))
P
T(xa)
Q
P
X2
X2
T(x.)
m(y)x,)
X
Xn
c(x,.T(X.))
(a) Monge's OT formulation.
(b) Kantorovich's OT formulation.
Figure 3: Classic optimal transport (OT) formulations.
To provide an intuition behind (2). we disintegrate d' (z. v) - dr (x))
inf TEU((..O) J {// c(2,, ((d,)))(
dP(x)
(3)
dm (xr)
i.e. (2) can be viewed as an extension of ① allowing to split the mass of input points P (Fig. (b))
With mild assumptions on P, Q, the OT cost value (2) coincides with [ see [62 Theorem 1.33].
Partial OT formulation. Let wo,w! 2 m O. We consider
inf m.a S Swiq 2
c(x, [mT] (2,
Xxy
where inf is taken over P(X x )) satisfying the inequality constraints mm,, S wolf P and may I wi Q. Minimizers H² of (4) are called partial OT plans (Fig. 4
Here the inputs are two measures wilP and w1 Q with masses Wp and w1. Intuitively, we need to match a m -th fraction mT, of the first measure woP with -th fraction myy of the second measure wi Q (Fig.
mTTr
c(xI.y1)
y1
Wi IP
W Q
choosing Tz: Fy is also part of this problem. The key difference from problem (4) is that the constraints w1. problem (4) reduces to (2) as the inequality constraints
c(Xa.yn)
are inequalities. In the particular case m
Figure Partial optimal transport formulation.
can be replaced by equalities.
3 Main Results
First, we formulate the extremal transport (ET) problem (33.1). Next, we prove that ET maps can be recovered as a limit of incomplete transport (IT) maps ($3.2 3.3). Then we propose an algorithm to solve the IT problem ($3.4). We provide the proofs for all the theorems in Appendix F
3.1 Extremal Transport Problem
Popular unpaired translation methods, e.g., 72, S3.1] and 333 53]. de-facto assume that available samples x, y from the input and output domains come from the data distributions P. Q P(X)) As result, in their optimization objectives, the domain loss compares the translated T(xx) ~ T;P and target samples y Q by using metric for comparing probability measures, e.g., GAN loss 27 Thus, the target domain is identified with the probability measure Q
We pick different approach define what the domain is. We still assume that the available data comes from data distributions, i.e., I ~ P, y ~ Q. However, we say that the target domain is the part of y where the probability mass of + lives Namely, it is (Q) V. We say that map T translates the domains if Supp(T Supp(Q) This requirement is weaker than the usual THP- T Q.
Assume that c(x, y) is a function estimating the dissimilarity between æ,, y. We would like to pick T(x) E Supp(Q) which is maximally similar to x in terms of c(x, y). This preference of T can be formalized follows: Cost
def
/ c(x: T(P)).
inf Supp(T Supp(Q) where the inf is taken over measurable T: + y which map the probability mass Supp QQ).
(5)
We say that (5) is the (Monge's s) extremal transport (ET) problem.
Following the standard manifold hypothesis 21. real data distribution Q is usually supported on a small- dimensional manifold M -Supp(Q) C [-11,]] occupying tiny part of the ambient space [-1, 1|"

---

((x),T(x:))
(c(x,,)dn(ylx))
X1
T(Xi)
X:
n(vxx))
c(xe,T(X=))
P X2
T(X2) Q
P X2
n(vlx))
(vlx)))
T(X.)
Xn
Xn Jc(x):)ddn())s)
c(x,,.(Xx))
(a) Monge's ET formulation.
(b) Kantorovich's ET formulation.
Figure 5: Extremal transport (ET) formulations.
Problem (5) atypical for the common OT framework. For example, the usual measure- pressrrvi constraint 7PP Q in ① is replaced with Supp(THP) C Supp(Q) which is more tricky. Importantly, measure Q can be replaced with any other Q E P()) with the same support yielding the same inf.
Below we analyse the minimizers T (5) We define e" ("x)) def
mingyespp(()) c(x, y). Here the min indeed attained (for all X) because c(z, y) is continuous and Supp( QQ C C a compact set. The value c² (z) can be understood as the lowest possible transport cost when mapping the mass of point x to the support Q For any admissible T (). holds (I-almost surely):
(x))
cl,, v) S (xx)). (ESupp(Q)
min
Proposition 1 (Continuity of c*). It holds that c* C(X).
As a consequence of Proposition ! we see that c* is measurable. We integrate 66 w.r.t. x ~ P and take inf over all feasible T. This yields lower bound Cost (IP Q):
Cost (F.CQ
J (x)))P()) S
I c(x, (x)))
inf Supp(THP) Supp((Q
There exists admissible T making 7 the equality. Indeed, let NN(x) def {y E Supp(Q) s.t. c(z, y) c* {x)} be the set of points which attain min in the definition of c". These points are the closest to points Q w.r.t. the cost c(x, y). We call them the nearest neighbors of x. From this perspective, we see that ( turns to equality if and only if T(x) ENN(x) holds for P-almost all
X, i.e., T maps points x x~ll to their nearest neighbors Supp (Q). We need make sure that such measurable 7 exists (Fig. 5ap.
Theorem 1 (Existence of ET maps). There exists at least one measurable map T : X + y minimizing (5) For P-almost all x E X holds that T (x) NN(x). Besides,
Cost (P, (P. / c² (x)dP(x).
We say that Cost (T, Q is the extremal cost because one can not obtain smaller cost when moving the mass of P to Supp(Q). In turn, we say that minimizers T" are ET maps.
One may extend the ET problem 8 in the Kantorovich's 's manner by allowing the mass splitting and stochastic plans:
Costoc (P, daf
inf TI TEI (3,0) Jxxy c(2, c(z,8)d7(x,))
(8)
where I1 (P, Q) are probability measures π E P(X x J) s.t. ne = I and Supp(Ty) C. Supp QQ).
To understand the structure of minimizers in (8) it is more convenient to disintegrate dr y) dr ( dx)
/ [ c( (ylo)) dP(x)
Cost (P, Q inf
=EII (P.Q)
(d)
Thus, computing 8 boils down to computing family of conditional measures (+|ax) minimizing As for any π E (P, Q), it holds (for P-almost all x E X)) that
c(x, v) S / clx, v) (y(æz)
c" (x))
min (e
(10)
because π redistributes the mass of to Supp (Q) By integrating 1T) w.r.t. r P n. and taking inf over all admissible plans n, we derive that fx (x)dP(x) is a lower bound for (8) In particular,

---

T
fcix):Vddntylx)
(xx).
X1
mlyl),)
X1
T(xx) wQQ
((xa)
P
P X
X2
mx,))
-((x))
Xn
X
((Xa.(XX)))
dnityk))
(a) Monge's IT formulation.
(b) Kantorovich's 's IT formulation.
Figure 6: Incomplete transport (IT) formulations.
the bound tight for x' =ylax) x) (x)( where 7** is the ET map from our Theorem Therefore,
the value (8) is the same as but possibly admits more minimizers. We call the minimizers x² of (8) the ET plens (Fig. 5b).
From 10) and the definition of (N()), we see that minimizers 'T" are the plans for which n (y/2) redistributes the mass of among the nearest neighbors y NN(x) of (for IP-almost all X). As result, r²" (ylæz) can be viewed as stochastic nearest neighbor assignment between the probability mass of P and the support of Q.
3.2 Incomplete Transport Problem
In practice, solving extremal problem (5) is challenging because it is hard to enforce SupP(THIP) C Supp(Q) (Q)) To avoid enforcing this constraint, replace it and consider the following problem with finite parameter w 2 1:
Cost (P, def inf TiPS
f c(1,, T(x)) (P)).
(11)
We call (1 Monge's incomplete transport (IT) problem (Fig. bap. With the increase of w, admissible
maps 7 obtain more ways to redistribute the mass of IP among Supp QQ) Informally, when - oc, the constraint TjP w in TT tends to the constraint Supp(T Supp(Q) (5). i.e 11 itself tends to ET problem
We will formalize this statement few paragraphs later (in $3.3
As in (T). problem may have no minimizer T or even may have the empty feasible Therefore, it is natural to relax problem (TT) in the Kantorovich's 's manner:
Cost (IP, Q def
inf FEIl (P.Q) Xxx clz, v)dT(z v).
(12)
where the inf is taken over the set 1I" (P, Q of probability measures и P(X' y) whose first marginal is Te = P. and the second marginal satisfies Ny I wQ (Fig. 6bb.
We note that IT problem 12 special
of partial OT with we (12). one may actually replace inf with min, see our proposition below.
and w1 w. In Proposition (Existence of IT plans). Problem 12) admits at least one minimizer x* E 11 Q).
We say that minimizers of 12 lower bounds Monge's counterpart [I]). Below we show that they coincide in the practically most interesting Euclidean case.
IT' plans. In the general case, Kantorovich's IT cost 12 always
Proposition 3 (Equivalence of Monge's, Kantorovich's 's IT costs). Let X RDD be two compact sets, E (()) be atomless, E ())). Then Monge's [1] and Kantorovich's 's (2) IT costs coincide.
However, it is not guaranteed that inf in Monge's problem [1] attained even in the Euclidean case. Still for general Polish spaces X, ) it is clear that if there exists deterministic IT plan in Kantorovich's problem [2) of the form x² lidx, T*), then 7 is an IT map (TT), and the IT Monge's [ and Kantorovich's 's (12 costs coincide. Henceforth, for simplicity, we assume that coincide, e.g., those from Prop. 3
X,Y, e, Q are such that (IT) and
IT problem 12) can be viewed as an interpolation between OT and ET problems (8). Indeed, when w 1. the constraint ny S Q is equivalent to ny Q as there only one probability measure which is < Q, and it is C itself. Thus, IT (12) with w coincides with OT (2). In the next section, we show that for w oo one recovers ET from IT.
3.3 Link between Incomplete and Extremal Transport
Now connect incomplete I2 and extremal g transport tasks.
5

---

Theorem 2 (IT costs converge to the ET cost when w - oc). Function w H Cost (P, Q) is convex,
non-increasing in w [1, +00) and
lim Co (P, Q) Costao (P, Q)- 100000
A natural subsequent question here is whether IT plans in (2) converge to ET plans ( when w + 0o.
Our following result sheds the light on this question.
Theorem 3 (IT plans converge to ET plans when ur - oc). Consider w1, W2, Wa, ... 2 satisfying
lim Wn o0. Let nh I1 (P, Q) be sequence of IT plans solving (22 with W
respectively. Then it has (weakly- *) converging sub-sequence. Every such sub-sequence of IT plans
converges to an ET plan π E - (P, Q).
In general, there may be sub-sequences of IT plans converging to different ET plans x' E II (P, Q). However, our following corollary shows that with the increase of weight w, elements of any sub- sequence become closer to the set of ET plans.
Corollary (IT plans become closer the set of ET plans when 00). For all 3w(() [1, 00) such that Vu 2 w(e) and V IT plan x E Th (P, Q)) solving Kantorovich 's IT problem 12) there exists an ET plan xt' which e-close π in W L.e., W WI(T", S 8.
Providing a stronger convergence result here is challenging, and we leave this theoretical question open for future studies. Our Theorems 2 and [ that to obtain fine approximation of an ET plan (w = oc), one may use an plan for sufhciently large finite w. In Appendix G.I we empirically demonstrate this observation through an experiment where the ground-truth deterministic ET plan is analytically known. Below we develop a neural algorithm to compute IT plans.
3.4 Computational Algorithm for Incomplete Transport
To begin with, for IT 12 we derive the dual problem. Theorem 4 (Dual problem for IT). It holds
Cost (P, Q = max / [1))) w w/ f(y)d(())
(13)
150 x
where the max is taken over non-positive f C()) and (x) def
min fc(a, y) ff (v)}
NEY
We call the function f potential. In the definition of fc, min is attained because c, f are continuous and y is compact. The function f is called the c-transform f.
The difference of formula (13) from usual c-transform-bant duality formulas for OT 2 see 622 S1.2], [65] 55), is that f is required be non-positive and the second term is multiplied by w >
We rewrite the term Jx (x)) in [33:
/ (<))d
inf / (c(2,T(x)) T:X
min
min (c(z. v) NEY
f(v))dP(z) ((ul:))-(u))ddPa)))
dx (14)
x
Here we the interchange between the integral and inf 59 Theorem 3A]: in 14 the inf is taken over measurable maps. Since (r, y) + c(x,,) - f(v) is continuous function on a compact set, it admits a measurable selection T(x) arg min { c(x,, y) f(y) minimizing (4). see
( Theorem 18..9]. Thus, inf can be replaced by min. We combine [1 and 13 and obtain equivalent saddle point problem:
Cost (P. Q = max min L(f.T),
(15)
1 T-X-y
where the functional L(f,T) T) is defined by
C(f.T) def [
dP(x) / F(T(=))dP(z) / f()) (
(16)
Functional L(f, T) can be viewed as Lagrangian with f < 0 being a multiplier for the constraint TIP wQ < 0. By solving (15), one may obtain maps.
Theorem 5 (IT maps contained in optimal saddle points). Let f be any maximizer in 13 "" E 11 II", Q) a deterministic IT plan, i.e., it solves (12) and has the form π = [id T FP for
some measurable T : X + Y, then
T arg min L(f", T:X+y

---

Algorithm 1: Procedure to compute the IT map between IP and Q for transport cost c(z, y) and weight w.
Input :distributions P, Q accessible by samples; mapper To X V potential fa :X' R transport cost c: X' y - IR; weight 2 1; number Kr of inner iterations;
:ampuut:aproximaa IT map (Tp) S wQ:
repeat
Sample batches X ~ P.P. Q
Ly - [8
Σ yEY
fo(v) XT
E (T((())):
mex
Update 1 by using for bo = -1,2.... Kr do Sample batch X IP; Cr+ + 1 Σ [c(2,To(z)) - (To())))
OLc maximize Ly; Be
Update 0 by using aCr as
to minimize Dr;
until not converged;
Our Theorem 5 states that in some optimal saddle points (f*, .") of (15) it holds that T is the IT map between P. Q. In general, the arg inf.- set for optimal f might contain not only IT maps T*, but other functions as well (fake solutions), see limitations in Appendix A
We solve the optimization problem (15) by approximating the map T and potential f with neural networks Ta and fur respectively. To make fy non-positive, we use æ + |2| as the last layer. The nets are trained using random batches from P, Q and stochastic gradient ascent-descent, We detail the optimization procedure in Algorithm
4 Related work
OT in generative models. A popular way to apply OT in generative models is to use the OT cost as the loss function to update the generator 28 22 see 41 for survey. These methods are nor relevant to our study as they do not learn an OT map but only compute the OT cost.
Recent works the possibility learn the OT maps (or plans) via solving saddle point optimization problems derived from the standard c-transform-base duality formulas for OT. The underlying principle of our objective
20
29 are the most related to our study. These papers show
(15) is analogous theirs. The key difference is that they consider OT problems ([).
(2 and enforce the equality costraints, c.g., TiP- = Q, while our approach enforces the inequality constraint TrP < wQ allowing to partially align the measures. We provide detailed discussion
of relation with these works as well as with the fundamental OT ( and partial OT 4 literature Appendix F see bibliographic remarks after the proofs of Theorems and S.
22 10
For completeness, we also mention other existing neural OT methods 25 63
39] These
works are less related to our work because they either underperform compared to the Ahooe--entione saddle point methods, see [40] for evaluation, or they solve specific OT formulations, e.g., entropic
OT (56] 84], which are not relevant to our study.
The papers [66, 47 19 slightly more related our work. They propose neural methods for unbalanced OT 14] which can also be used to partially align measures. As we will see in Appendix UOT is hardly suitable for ET (8) as it is not easy control how it spreads the probability mass. Besides, these methods consider OT between dime--iimensoonal datasets or in latent spaces. is not
B
clear whether they scale high-dimensions, e.g., images.
Discrete OT methods, including partial OT are not relevant to us, see Appendix D for details.
Unpaired domain translation 3 is a generic problem which includes image super-resolution [1]. inpainting [71]. style translation [+ tasks, etc. Hence, we do not mention all of the existing approaches but focus on their common main features instead. many applications, it is important to preserve semantic information during the translation, e.g., the image content. In most cases, to do this it sufficient to use convolutional neural networks. They preserve the image content thanks to their design which is targeted to only locally change the image [18). However, in some of the tasks
7

---

Mapped Tlx)
Mapped y Tud
Hasped Tar
efe Ba PERRO aNd SN
Taract
10-
85
-05-
005
15
10 (b) IT map, = 3.
0.0 0.5
15
10
(a) Input, target measures.
(c) IT map, w=
(d) IT map, =
Figure 7: Incomplete transport (IT) maps learned by our Algorithm in 'WiFFi' experiment.
Mapond
Vagsed
Heeped y
(a) Input measure.
(b) IT map, 8.
(c) IT map, w =.
(d) IT w= 2.
(c) IT map, w Target measure.
Figure 8: PCA projections of input F~ mapped ( THP and target y Q test samples
(handbag- sshoes experiment).
additional image properties must be kept, e.g., image colors in super-resolution. Typical approaches to such problems are based on GANs and use additional similarity losses, e.g., the basic CycleGAN [72] enforces ll similarity. Such methods are mostly related to work. However, without additional modifications most of these approaches only partially maintain the image properties, see [44] Figure 5]. As we show in experiments (Appendix C. IT achieves better similarity than popular CycleGAN, StarGAN-v2 15 methods, both default and modified to better preserve the image content.
5
Evaluation
In 1 we provide illustrative toy 2D examples. In $5.2 we evaluate our method on the unpaired image-to-image translation task. Technical training details (architectures, learning rates, etc.) are given Appendix E The code written using Pyforch framework and is publicly available
Transport costs. We experiment with the quadratic cost c(x, y) = (xr, y) as this cost already provides reasonable performance. We slightly abuse the notation and use f to denote the squared error normalized by the dimension. Experiments with the perceptual cost are given in Appendix G.3
5.1 Toy 2D experiments
In this section, we provide 'Wi-F7' and 'Accept' examples in 2D to show how the choice of w affects the fraction of the target measure Q to which the probability mass of the input mapped. both cases, measure P is Gaussian. In Appendix B demonstrate how other methods perform these
'Wi-Fi' and 'Accept' toy examples.
In 'Wi-Fi' experiment (Fig. [] target Q contains 3 arcs. We provide the learned IT maps for w E [1, 2, 3). The results show that by varying
is possible to control the fraction of Q which the mass of IP will be mapped. In Fig. 7 we see that for = 1 our IT method learns all 3 arcs. For
w = 2. it captures ares, i.e., R 2 of Q For w 3, it learns are which corresponds to 1 of Q. 3
3
In 'Accept' experiment (Fig. 2) target Q is a two-line text. Here we put w = 2 and, as expected, our method captures only one line of the text which the closest to IP in 82
5.2 Unpaired Image-to-image Translation
Here we learn IT maps between various pairs of datasets. We test w E (1, (1,2,4 2,8.8 all experiments. For completeness, consider bigger weights w E {16, 32) in Appendix G.4
8

---

x-P
T(x)
T(x
w-1
W
T(X) W 2
T(X)
TUXi
W 4
T W= 44
T(x)
W 8
T(x)
(a) IT results for textures chairs (64x64).
(b) IT results for ffhq + comics (128x 128).
Figure 9: Unpaired Translation with our Incomplete Transport
Experiment 0.297
Experiment
celoba anime
0.154
0,133
0.094
celeba + anime
14.65
20.79
22.18
22.84
handbog- + shoes
0.368
0.320
0.259
0.252
handbog + shoes
27.10
29.70
42.90
53.80
fexturer chairs
0.603
0.516
textumes choirs
comics
0.224
0.220
0,200
0.196
comics
20.95
22.38
22.77
23.67
(a) Test ee transport cost of our learned IT maps.
(b) Test FID of our learned IT maps.
Table I: Test l cost and FID of our learned IT maps.
Image datasets. We utilize the following publicly available datasets P, Q: celebrity faces [46]. aligned anime faces fickr-faces-HQ, (36), comic face Amazon handbags from LSUN dataset [68], shoes [67]. textures [16] and chairs from Bonn furniture styles dataset [1]. The sizes of datasets are from 5K to 500K samples. We work with 64 x 64 and 128 x 128 images.
Train-test split. We use 90% of each dataset for training. The remaining 10% are held for test. All the presented qualitative and quantitative results are obtained for test images.
Experimental results. Our evaluation shows that with the increase of w the images T(x)) translated by our IT method become more similar to the respective inputs w.r.t. L In Table la we quantify this effect. Namely, we show that the test transport cost increase of w which empirically verifies our Theorem
Nam Nos n= c(x, (z)) decreases with the
We qualitatively demonstrate this effect in Fig. 1b la
and In celeba (female) anime (Fig. Tb). the hair and background colors of the learned anime images become closer to celebrity faces' colors with the increase of w. For example, in the 4th column of Fig. Tb] the anime hair color changes from green to brown, which is close to that of the respective celebrity. In the 6th column, the background is getting darker. In handbag-+shoe (Fig. Lap. the color, texture and size of the shoes become closer to that of handbag. Additionally, for this experiment we plot the projections of the learned IT maps to the first 2 principal components of (Fig. 8). We see that projections are close to Q for = 1 and become closer to P with the increase of w. In -coohiss the changes mostly affect facial expressions and individual characteristics. In rextures-tchate
the changes are mostly related to chairs' size which is expected since we use pixel-wise l as the cost function. Additional qualitative results are given Appendix G.5 (Fig. 24
25 9a).
For completeness, we measure test FID 32 of the translated samples, see Table Tb We do not calculate FID in the handbag -cchirss experiment because of too small sizes of the test parts of the datasets (500 textures, 2K chairs). However, we emphasize that FID is not representative when to > 1. In this case, IT maps learn by construction only part of the target measure Q. At the same time, FID tests how well the transported samples represent the entire target distribution and is very sensitive mode dropping [48] Fig. 1b]. Therefore, while the cost decreases with the growth of w, FID, on the contrary, increases. This is expected since IT maps to smaller part of Q. Importantly, the visual quality of the translated images T(x) is not decreasing.

---

we compare our IT method with other image-to- to-iaage translation methods and show that IT better preserves the input-output similarity.
In Appendix C
6 Potential Impact
Inequality constraints for generative models. The majority of optimization objectives in generative models (GANs, diffusion models, normalizing flows, etc.) enforce the equality constraints, e.g., THP = Q where TBP is the generated measure and Q is the data measure. Our work demonstrates that it is possible to enforce inequality constraints, e.g.. 7:P S wQ, and apply them to a large-scale problem. While in this work we primarily focus the amage-to-image translation task, believe that the ideas presented in our paper have several visible prospects for further improvement and applications. We list them below.
(1) Partial OT. Learning alignments between measures of unequal mass is a pervasive topic which has already perspective applications in biology to single-cell data [66 47 19]. The mentioned works use unbalanced OT [1]]. This is an unconstrained problem where the mass spread is softly controlled by the regularization. Therefore, may be hard to control how the mass is actually distributed. Using partial OT which enforces hard inequality constraints might potentially soften this issue. Our IT problem (12) is particular case of partial OT (4) We believe that our study is useful for future development of partial OT methods.
(2) Generative nearest neighbors. NNs play an important role in machine learning applications such as, e.g., image retrieval [6]. These methods typically rely on fast discrete approximate NN [50] 35 and perform matching with the latent codes of the train samples. In contrast, nowadays, with the rapid growth of large generative models such as DALL-E [58], CLIP [57], GPT-3 19. it becomes relevant to perform out-of- of-sample estimation, e.g., map the latent vectors new vectors which are not present in the train set to generate new data. Our IT approach (for w - oo) is theoretically justified way to learn approximate NN maps exclusively from samples. We think our approach might acquire applications here as well, especially since there already exist ways to apply OT in latent spaces of such models 20)
(3) Robustness and outlier detection. Our IT aligns the input measure IP only with a part of the target measure Q This property might be potentially used to make the learning robust, e.g., ignore outliers in the target dataset. Importantly, the choice of outliers and contamination level are tunable via c(2, y) and but their selection may be not obvious. At the same time, the potential f vanishes on the outliers, ie., samples in Supp(Q) to which the mass is not transported.
Proposition 4 (The potential vanishes at outliers). Under the assuptions of Theorem (") = 0 holds for all y E Supp( (Q) Suppp("=FF)
S the equality
We empirically illustrate this statement in Appendix A As result of this proposition, a possible byproduct of our method is an outlier-score (") for the target data. Such applications of OT are promising and there already exist works [52 7 54 developing approaches to make OT more robust.
Limitations, societal impact. We discuss limitations, societal impact of our study in Appendix
ACKNOWLEDGEMENNTS This work was partially supported by Skoltech NGP Program "Skoltec-MIT joint project).
References
[1] D. Aggarwal, E. Valiyev, F. Sener, and A. Yao. Learning style compatibility for furniture. In German Conference on Pattern Recognition, pages 552-566. Springer, 2018.
[2] C. D. Aliprantis and K. C. Border. Infinite dimensional analysis. Technical report, Springer, 2006.
[3] A. Alotaibi. Deep generative adversarial networks for image-to-image translation: A review. Symmetry, (2(10):1705, 2020.
[4] M. Arjovsky, S. Chintala, and L. Bottou. Wasserstein generative adversarial networks. In
International conference machine learning, pages 214-223. PMLR, 2017.
10

---

[5] A. Asadulaev, A. Korotin, V. Egiazarian, and E. Burnaev. Neural optimal transport with general cost functionals, arXiv preprint wrXiv:2205.554000 2022.
[6] A. Babenko, A. Slesarev, A. Chigorin, and V. Lempitsky. Neural codes for image retrieval. In European conference on computer vision, pages 584-599. Springer, 2014.
[7] Y. Balaji, R. Chellappa, and S. Feizi. Robust optimal transport with applications in generative modeling and domain adaptation. Advances in Neural Information Processing Systems, 33: 12934-12944, 2020.
[8] M. Binkowski, D. J. Sutherland, M. Arbel, and A. Gretton. Demystifying mmd gans. In International Conference Learning Representations, 2018.
[9] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[10] L. Caffarelli and J. McCann. Free boundaries optimal transport and monge-ampere obstacle problems. Annals of mathematics, pages 673-730, 2010.
[11] L.. Chapel, M. Z. Alaya, and Gasso. Partial optimal tranport with applications on positive- unlabeled learning. Advances in Neural Information Processing Systems, 33:2903-2911, 2020.
[12] H. Chen, X. He, L. Qing, Wu, C. Ren, R. E. Sheriff, and C. Zhu. Real-world single image super-resolution: A brief review. Information Fusion, 79: 124-145,, 2022.
[13] X. Chen and C. Jia. An overview of image-to-image translation using generative adversarial networks. In International Conference on Pattern Recognition, pages 366-380. Springer, 2021.
[14] L. Chizat. Unbalanced optimal transport: Models, numerical methods, applications. PhD thesis, Université Paris sciences lettres, 2017.
[15] Y. Choi, Y. Uh, J. Yoo, and J.-W. Ha. Stargan v2: Diverse image synthesis for multiple domains. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 8 8188-8197, 2020.
[16] M. Cimpoi, S. Maji. Kokkinos, S. Mohamed, and A. Vedaldi. Describing textures in the wild. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2014.
[17] M. Daniels, T. Maunu, and P. Hand. Score-based generative neural networks for large-scale scale optimal transport. Advances in neural information processing systems, 14:12555-12265, 2021.
[18] E. de Bézenac, I. Ayed, and P. Gallinari. Cyclegan through the lens of (dynamical) optimal transport. In Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings. Part I1 21, pages 132-147. Springer, 2021.
[19] L. V. Eyring, D. Klein, G. Palla, S. Becker, Weiler, N. Kilbertus, and F. Theis. Modeling single-cell dynamics using unbalanced parameterized monge maps. bioRxiv, 2022.
[20] J. Fan, S. Liu, S. Ma, H.-M. Zhou, and Y. Chen. Neural monge map estimation and its applications. Transactions Machine Learning Research, 2023. ISSN 2835-8856. URL https://openreviet net: httffformmmii 21S221222222m Featured Certification.
[21] C. Fefferman, S. Mitter, and H. Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 2944)98331104, 2016.
[22] A. Figalli, The optimal partial transport problem. Archive for rational mechanics and analysis, 195(2):533-560 2010.
[23] G. B. Folland, Real analysis: modern techniques and their applications, volume 40. John Wiley & Sons, 1999.
11

---

[24] M. Gazdieva, L. Rout, A. Korotin, A. Kravchenko, A. Filippov, and E. Burnaev. An optimal transport perspective on unpaired image super-resolution. arXiv preprint arXiv:2202.01116 2022.
[25] A. Genevay, M. Cuturi, G. Peyré, and F. Bach. Stochastic optimization for large-scale optimal transport. In Advances in neural information processing systems, pages 3440-3443 2016.
[26] A. Genevay, G. Peyré, and M. Cuturi. Learning generative models with sinkhorn divergences. In International Conference on Artificial Intelligence and Statistics, pages 1608-1617. PMLR, 1018.
[27] I. Goodfellow, J. Pouget- Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial nets, In Advances neural information processing systems, pages 2672-2680, 2014.
[28] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training of Wasserstein GANs. In Advances in Neural Information Processing Systems, pages 5767-5777, 2017.
[29] N. Gushchin, A. Kolesov, A. Korotin, D. Vetrov, and E. Burnaev. Entropic neural optimal transport via diffusion processes. In Advances in Neural Information Processing Systems, 2023.
[30] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[31] P. Henry-Labordere. (martingale) optimal transport and anomaly detection with neural networks: primal-dual algorithm. arXiv preprint arXiv: 1904. 04546, 2019.
[32] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter. GANs trained by a two time-scale update rule converge to local nash equilibrium. In Advances in neural information processing systems, pages
2017.
[33] X. Huang, M.-Y. Liu, S. Belongie, and J. Kautz. Multimodal unsupervised image-to-image translation. In Proceedings of the European conference on computer vision (ECCV), pages 172-189, 2018.
[34] Y. Jing, Y. Yang, Z. Feng, J. Ye, Y. Yu, and M. Song. Neural style transfer: A review. IEEE transactions on visualization and computer graphics, 26(11):3365-338 2019.
[35] Johnson, M. Douze, and H. Jégou. Billion-scale similarity search with gpus. IEEE Transac- tions on Big Data, 7(3):535-547) 2019.
[36] T. Karras, S. Laine, and T. Aila. A style-based generator architecture for generative adversar- ial networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401-4410, 2019.
[37] W. Karush. Minima of functions of several variables with inequalities side conditions. In Traces and Emergence of Nonlinear Programming, pages 217-245. Springer, 2014.
[38] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv:1412.6988) 2014.
arXiv preprint
[39] A. Korotin, V. Egiazarian, A. Asadulaev, A. Safin, and E. Burnaev. Wasserstein-2 generative networks. In International Conference Learning Representations, 2021. URL https
//openreview net.fformmidd-boox. EXsa
[40] A. Korotin, L. Li, A. Genevay, J. M. Solomon, A. Filippov, and E. Burnaev. Do neural optimal transport solvers work? continuous wasserstein-2 benchmark. Advances in Neural Information Processing Systems, 34:14593-14605, 2021.
[41] A. Korotin, A. Kolesov, and E. Burnaev. Kantorovich strikes back! wasserstein gans are not optimal transport? In siih Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022.
12

---

[42] A. Korotin, D. Selikhanovych, and E. Burnaev. Kernel neural optimal transport. In International Conference on Learning Representations, 2023. URL httpp:://pperrriien wtwp:/rrwwiiie.eeffuuueee net/forum?
id=Zuc MHtUma4
[43] A. Korotin, D. Selikhanovych, and E. Burnaev. Neural transoor,, In International Conference on Learning Representations, 2023. URL htt.ttssp///ppeeeeieeeeee http://ppenrriiee..eet/rtrrmm net/forum? id=dBCBRIWNkqH
transport.
[44] Z. Li, Xu, N. Zhao, Y. Zhou, Y. Liu, D. Lin, and S. He. farsing-conditionee anime translation: A new dataset and method. ACM Transactions on Graphics, 42(3):1-14, 2023.
[45] H. Liu, X. Gu, and D. Samaras. Wasserstein GAN with quadratic transport cost. In Proceedings of the IEEE International Conference on Computer Vision, pages 4832-4841, 2019.
[46] Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
[47] F. Lübeek, C. Bunne, G. Gut, J. del Castillo, L. Pelkmans, and D. Alearez-Melis. Neural unbal- anced optimal transport via cycle- syllecconsistent semi-couplings. arXiv preprint 20Xiv:2209.16621, 2022.
[48] M. Lucic, K. Kurach, M. Michalski, S. Gelly, and O. Bousquet. Are GANs created equal? a large-scale study. In Advances in neural information processing systems, pages 700-709, 2018.
[49] A. Makkuva, A. Taghvaei, S. Oh, and J. Lee. Optimal transport mapping via input convex neural networks. In International Conference on Machine Learning, pages 6672-6683 PMLR, 2020.
[50] Y. A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4))824-836, 2018.
[51] A. Mathur, A. Isopoussu, F. Kawsar, N. Berthouze, and N. D. Lane. Mic2mic: using cycle- consistent generative adversarial networks to overcome microphone variability in speech sys- tems. In Proceedings of the 18th international conference on information processing in sensor networks, pages 169-180, 2019.
[52] D. Mukherjee, A. Guha, J. M. Solomon, Y. Sun, and M. Yurochkin. Outlier-rbuust optimal transport. In International Conference on Machine Learning, pages 7850-7860. PMLR, 2021.
[53] Q H. Nhan Dam, T. Le, D. Nguyen, H. Bui, and D. Phung. Threeplayer Wasserstein GAN via amortised duality. In Proc. of the 28th Int. Joint Conf. on Artificial Intelligence (IJCAI), 2019.
[54] S. Nietert, Z. Goldfeld, and R. Cummings. Outlier-robust optimal transport: Duality, structure, and statistical analysis. In International Conference on Artificial Intelligence and Statistics, pages 11691-11719. PMLR, 2022.
[55] Y. Pang, J. Lin, T. Qin, and Z. Chen, Image-to-image translation: Methods and applications. IEEE Transactions on Multimedia, 2021.
[56] G. Peyré, M. Cuturi, et al. Computational optimal transport. Foundations and Trends@ in Machine Learning, 11 11(5-)):355 607, 2019.
[57] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages 8748-8763. PMLR, 2021.
[58] A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06/22 2022.
[59] R. T. Rockafellar. Integral functionals, normal integrands and measurable selections. In Nonlinear operators and the calculus of variations, pages 157-207. Springer, 1976.
13

---

[60] O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedical image segmentation. International Conference on Medical image computing and computer-assisted intervention, pages 234 241. Springer, 2015.
[61] L. Rout, A. Korotin, and E. Burnaev. Generative modeling with optimal transport maps. In International Conference on Learning Representations, 2022.
[62] Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):94,
2015.
[63] V. Seguy, B. B. Damodaran, R. Flamary, N. Courty, A. Rolet, and M. Blondel. Large scale optimal transport and mapping estimation. In International Conference on Learning Represen- tations, 2018.
[64] Terkelsen. Some minimax theorems. Mathematica Scandinavica, 31(2):405 1972.
[65] C. Villani. Optimal transport: old and new, volume 338. Springer Science Business Media, 2008.
[66] K. D. Yang and C. Uhler. Scalable unbalanced optimal transport using generative adversarial networks. International Conference on Learning Representations, 2018.
[67] A. Yu and K. Grauman. Fine-grained visual comparisons with local learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 192-199, 2014.
[68] Yu, A. Seff, Y. Zhang, S. Song. T. Funkhouser, and J. Xiao. Lsun: Construction of large-scale image dataset using deep learning with humans in the loop. arXiv preprint arXiv: 03360, 2015.
[69] Y. Yuan, S. Liu, Zhang, Y. bing Zhang, C. Dong, and Lin. Unsupervised image super- resolution using cycle-in-cycle generative adversarial networks. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 314-81409, 2018.
[70] R. Zhang, P. Isola, A. A. Efros, E. Shechtman, and O. Wang. The unreasonable effectiveness of deep features perceptual metric. In CVPR, 2018.
[71] X. Zhang, D. Zhai, T. Li, Y. Zhou, and Y. Lin. Image inpainting based deep learning: A review. Information Fusion, 2022.
[72] J.-Y. Zhu, T. Park, P. Isola, and A. A. Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference on computer vision, pages 2223-2232, 2017.
14

---

A Limitations
Transport costs. Our theoretical results hold true for any continuous cost function c(z, y), but our experimental study uses E as it already yields reasonable performance in many cases. Considering more semantically meaningful costs for image translation, e.g., perceptual 77 is a promising future research direction.
Intersecting supports. ET the nearest neighbor assignment ($3.1) Using ET may unreasonable when X' 3 and (Ppp(P) intersects with Supp(Q). For example, if c(x, y) attains minimum over y E y for given a E X' at x = y, c.g., C = then there exists a ET plan satisfying x (y(xz) = 6 for all E (IP n Supp Q) It does not move the mass of points æ in this intersection. We provide an illustrative toy 2D example in Fig. 10b
Limited diversity. It is theoretically impossible to preserve input-output similarity better than ET maps. Still one should understand that in some cases these maps may yield degenerate solutions. In Fig. [0a] we provide toy 2D example of an IT map (w 8) which maps all inputs to nearly the same point. In Fig. 9a (texture - chuir translation), we see that with the increase of the IT map produces less small chairs but more large armchairs. In particular, when = 8, only armchairs appear, see Fig. 9a This is because they are closer (in e²) to textures due to having smaller white background area.
1.5
Viput -P
Mapped Tix]
Inputx--p
Input Happed y 120
1.0
Target
1.
Targetio
0.5
34
0.0
0.-
-0.5
-05
00%
8
-1.0
-1.5
-25
0.0
10
1,915
-1.0
-0.5
2.0
(a) Limited diversity. The true ET map is degenerate: it maps the entire P to a single vertex of the triangle Q
(b) Intersecting supports The true ET map is the identity map: it does not move the probability mass of F. The example shows the learned IT map with high in 8 approximating the ET map.
The example shows the learned IT map with high w = 20 approximating the ET map.
Figure 10: Toy 2D examples showing two (potential) limitations of IT maps.
Unused samples. Doing experiments, we noticed that the model training slows down with the increase of w. A possible cause of this is that some samples from Q become non-informative for training (this follows from our Proposition g. Intuitively, the part of Supp(Q) to which the samples of IP will not be mapped to is not informative for training. We illustrate this effect on toy 'Wi-Fi' example and plot the histogram of values of f* in Fig. [] One possible negative of this observation is that the training of IT maps or, more generally, partial OT maps, may naturally require larger training datasets.
2.
Irputx-P
Mapcedy Tix!
15-
Negredy Tial
10-
12.5
5.-
25-
-10
-03
80
05
10
15
20
-14
-03
00
03
10
15
1.0
-as
00
03
28
1.3
2.0
-10 -0.5
-26
-04
-0.2 00
((y)
(a) Surface of f (trained with
(b) Surface of l (trained with w 2)
(c) Surface of f
(d) Histograms of values of (3) for y @
1).
(trained with w 3).
Figure 11: Illutrationn the unused samples. In Figures Ia learned potential f on the 'Wi-Fi' example and w E [1, 2.3
Ilb
[cc
we visualize the surface of the
Figures 11b 11c the potential vanishes on the arcs of Q to which the mass of P is not mapped, i.e., ( = In Figure 1id we plot the distribution of values of f*((y) for y ~ Q. For w E {3 3). we see large pikes around f (v) = 0 further demonstrating that the potential equals to zero on a certain part of Q
15

---

Limited quantitative metrics. In experiments (e we use a limited amount of quantitative metrics. This is because existing unpaired metrics, e.g.. FID B2]. KID [ etc., are not suitable for our setup. They aim to test equalities, such as T:P Q. while our learned maps disobey it by the construction (they capture only a part of Q). Developing quality metrics for partial generative models is an important future research direction. Meanwhile, for our method, we have provided toy 21) analysis ($5.T) and explanatory metrics ($5.2). such as the transport cost (Table Ia).
Inexistent IT maps. The actual ITT plans between I,, Q may be non-deterministic, while our approach only learns a deterministic map T. Nevertheless, thanks to our Proposition B for every c > there
always exists a 1-to-1 1 map TxP I wp which provides c-sub-optimal cost x c(x, (P)) S Co (P, Q) + 6. Thus, ITT cost (12) can be approached arbitrary well with deterministic transport maps. A potential way modify our algorithm is learn stochastic plans is to add random noise to generator T(x z) as input, although this approach may suffer from ignoring 2, see 43 55.1].
Fake solutions and instabilities. Lagrangian objectives such as 15) may potentially have optimal saddle points (f", (*) in which T is not an OT map. Such T are dalleffaee solutions [42] and may be one of the causes of training instabilities. Fake solutions can be removed by considering OT
with strictly convex weak costs functions 43 Appendix H], see Appendix G.2 for examples.
Potential societal impact. Neural OT methods and, more generally, generative models are developing research direction. They find applications such as style translation and realistic content generation. We expect that our method may improve existing applications of generative models and add new directions of neural OT usage like outlier detection. However, it should be taken into account that generative models can also be used for negative purposes such creating fake faces.
B Toy 2D Illustrations of Other Methods
In this section, we demonstrate how the other methods perform in 'Wi-Fi' and 'Accept' experiments. We start with 'Wi-F?'. Assume that we would like to map IP to the closest 3-rd fraction of Q, i.e., we aim to learn 2 of 3 arcs in Q (as in Fig. 7cp.
In Fig. 12d we show the discrete partial OT W1
with parameters wo m corresponding to IT (12) with w = To obtain the discrete matching, we run ot partiall..... partial.partial watrriall_wsserteeenn222 from POT As expected, it matches the input P with 3 of Q and can viewed as the ground truth (coinciding with our Fig. (c).
First, we show the GAN (77 endowed with additional e loss with weight À = 0.5 (in Fig. 12a Next, we consider discrete unbalanced OT [14] with the quadratic cost c (2. In Fig. 12b we show the results of the matching obtained by ot. unbalanced with parameters m = 1, reg = U.1, regm = 1. num]termar 200000. Additionally, in Fig. 12c we show the result of neural unbalanced OT method 66 M To make their unbalanced setup maximally similar to our IT, we set to zero their regularization parameters. The rest parameters are default except for Ag = 0.02 (62 loss parameter), d2 = 5 (input and target measures" variation parameter).
We that G2 (Fig. 12ap and unbalanced OT (Fig. 12b and 12ch indeed match P with only part of the target measure + The transported mass is mostly concentrated in the two small ares of Q which are closest to I w.r.t. e2 cost. The issue here that some mass of spreads over the third (biggest) are of Q yielding outliers. This happens because unbalanced OT (GAN can be viewed as its particular case) is an unconstrained problem: the mass spreading controlled via soft penalization (f -fviieereence loss term). The lack of hard constraints, such as those in partial OT 44) or IT (2). makes it challenging to strictly control how the mass in unbalanced OT actually spreads.
For completeness, we also show the results of these methods applied to 'Accept' experiment, see Fig. 13 Here we tested various hyperparameters for these methods but did not achieve the desired behaviour, i.e., learning only the text 'Accept'. Moreover, we noted that GAN+ for large À yields undesirable artifacts (Fig. 13ab. This is because GAN and g losses contradict to each other and still the models tried to minimize them both. We further discuss in Appendix C below.
ppthonot. srtchonot.github.io
github.
16

---

15
Mapped
Mippad y Tix)
Mappody-
Masped T(rl
Cip a
10-
molo
03
00-
-05
-05
15
1.0
0.0
20-10
1.0
(a) GAN+E2
(b) Discrete unbalanced
(c) Scalable unbalanced
(d) Diserete Partial OT
OT.
OT.
(desired ground truth).
Figure 12: Transport maps learned by various methods in 'Wi-Fi" experiment (Fig. 7ap.
6.0
RV:
ACCEPT
Macood
Mapped
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
-1.
-0.5
10
-1.0
-0.5
0.5
1.0
(a)
+
(b) Discrete unbalanced
(c) Scalable unbalanced
(d) Discrete Partial OT (desired ground truth).
OT.
OT.
Figure 13: Transport maps learned by various methods in 'Accept' experiment.
C
Comparison with Other Image-to-Image Translation Methods
Recall that ET by design is the best translation between pair of domains w.r.t. the given dissimilarity function c(x; y)- Our IT maps with the increase of w provide better input-output similarity and recover ET when w co (3.)). A reader may naturally ask: (a) How else
recover ET maps? (b) To which extent one can control the input-output similarity in existing translation methods? (c)
Can these methods be used approximate ET? We discuss these aspects below.
Many translation methods are based on GANs, see 55 usually combined of several loss terms:
13
for a survey. Their learning objectives
def Doom (T) + X Lsim (T) (other terms).
Toaal
(17)
In 17). the domain loss Dom is usually the vanilla GAN loss involving a discriminator
27 ensuring
that the learned map x + Txx transforms inputs x ~ P to the samples from the target data distri- bution Q The similarity loss Lsim (with À 2 0) is usually the identity loss fx ||æ T(x) dz)) More generally, it can be arbitrary unsupervised loss of the form fxx c(x; (x))) stimulat- ing the output sample T(x) to look like the input samples w.r.t. given dissimilarity function e.g., el e, f., perceptual, etc. The other terms in (17) involve model-specific terms (e.g., cycle consistency loss in CycleGAN) which not related to our study.
When learning a model via optimizing 17), a natural way to get better similarity of x and (xx) in (17) is to simply increase weight À of the corresponding loss term. This is straightforward approach but has a visible limitation. When is high, the term À Lsim dominates over the other terms such as LDmms and the model T simply learns to minimize this loss ignoring the fact that the output sample should be from the target data distribution Q. In other words, in (T7) there is a nasty trade-off between T(x) belonging to the target data distribution Q and input-output similarity of z and T(x). The parameter À 2 0 controls this realism-similare trade-off, and we study how it affects the learned map T below.
We pick CycleGAN 72 as base model for evaluation since is known as one of the principal models to solve the unpaired translation problem. We use el the similar- ity loss as the CycleGAN's authors originally used in their paper] We consider parameter A [0, 50, 100, 200, 250, 300, 350, 500).
We also conducted separate experiment to train CycleGAN with e identity loss. However, in this case CycleGAN's training turned to be less stable and, importantly, yielded (mostly) worse FID. Surprisingly.
17

---

Additionally, we perform comparison with more recent StarGAN-v2 [15] model. By default, StarGAN-v2 does not use any similarity loss and does not enforee the output to be similar to the input. Therefore, analogously to CycleGAN, we endow the model with an additional e similarity loss and consider E [0. 1, 10, 50, 100, 200, 500).
We train both models on celeba + anime (64 x 64) and handbags - shoes (128 x 128) translation with various and report the qualitative and quantitative results below. In all the cases, we report both E and El transport costs and FID on the test samples. Tables 2 3 show transport costs and FII of GANs. FIID and 12 metrics for our method are given in the main text (Tables 1b Ta and e
cost is given in Table 6 below. For convenience, we visualize (FID) Cost) pairs for our method and GANs in Fig. [1]]
Results and discussion (CycleGAN). Interestingly, we see that for CycleGAN adding small identity loss À = 50 yields not only decrease of the transport cost (compared of FID as well. Still we see that the transport cost in CycleGAN naturally decreases with the increase of weight X. Unfortunately, this decrease is accompanied by the decrease of the visual image quality, see Fig.
0), but some improvement
15 While for large À the cost for CycleGAN is really small, the model is practically useless since poors image quality. For very large X, CycleGAN simply learn the identity map, as expected.
For À providing acceptable visual quality, CycleGAN yields transport cost which is bigger than that of standard OT (w = 1). Our result for w = 8 is unachievable for it. Note that in most cases FII of our IT method is smaller than that of CycleGAN.
Results and discussion (StarGAN-v2), In the celeba-vanime experiment, StarGAN-v2 results are similar to CycleGAN ones. Our IT with w = 2 casily provides smaller transport cost (better similarity) than StarGAN-v2. In the handbags + shoes translation, we have encountered surprising observations. We see that starting from À = 10 the model fails to translate some of the handbags to shoes, i.e., these handbags remain nearly unchanged. We notice the similar behaviour for vanilla GAN in 'Accept' experiment, see Fig. 13a This explains the low cost for StarGAN-v2 model (A 2 10). Surprisingly to us, for À = 10, FID metric is also low despite the fact that model frequently produces failures, see the highlighted results in Fig. [6] Note that while FID is a widely used metric, it still could produce misleading estimations which we observe in the latter case.
Additionally, we provide a large set of randomly generated images for À = 10 to qualitatively show that the stated issue is indeed notable, see Fig. 17 These failures demonstrate the limited practical usage of the model. Our IT method does not suffer from this issue which we qualitatively demonstrate on the same set of images for different weights w, see Fig. 25
Experiment
Cost
X
= 0
X =
50
A = 100
X = 200
À = 250
À = 300
X = 350
X = 500
celeba anime handbag + shoes
0.48
0.48
0.39
0.26
0.09
0.09
0.09
0.09
0.42
0.36
0.34
0.31
0.32
0.22
0.16
0.07
celeba + anime
0.33
0.32
0.24
0.11
0.01
0.02
0.02
0.01
e
handbag + shoes
0.51
0.43
0.41
0.35
0.37
0.22
0.14
0.02
Table 2: Test é! and e transport cost of CycleGAN.
Experiment
À 0
A
50
x 100
A
200
250
X
300
À 350
500
celeba + anime
22.9
20.8
35.2
88.8
122.2
123.5
120.0
122.8
handbag + shoes
27.8
23.4
23.6
37.4
38.5
105.6
144.9
152.9
Table 3: Test FID of CycleGAN.
Experiment
Cost
A=
0
x=
== 10
À 50
x= = 100
À 200
À = 500
celeba - anime
0.672
0.355
0.210
0.076
0.050
0.030
0.029
handbag - shoes
0.562
0.465
0.244
0.087
0.068
0.054
0.048
celebu + anime
0.686
0,216
0.094
0.017
0.006
0.002
0.002
handbag shoes
0.739
0.584
0.244
0.040
0.023
0.015
0.012
Table 4: Test el
and 8 transport costs of StarGAN-v2.
Experiment
x=
A
=
= 10
= 50
= 100
X 200
À = 500
celeba - anime
19.55
22.40
42.30
99.68
123.76
137.8
139.11
handbag - shoes
25.45
45.13
22.36
131.8
149.8
155.8
158.8
Table 5: Test FID of StarGAN-v2.
observed higher test transport costs (both e² and ét). Therefore, not to overload the exposition, we decided to keep only the experiment with CycleGAN trained with el identity loss.
18

---

celeba anime
handbag + shoes
celaba anime
handbag - shohes
CycluG6N StarGAM vZ
CycloGAN
CydlGGA SterGiA (ours)
CycleGAN StarGiiev22 (ours)
50
D2rGAN
10
20g
10
Aw100
Ton
30
Am1
10-
0U
6.1
0.
0.1
014
0.0
022
U.4
0.6
6.0
0.2
0.4
0.6
0.1
0.2
0.3
9,4
03
1 cost
F cost
cost
cast
(a) Test e transport cost.
(b) Test ed transport cost.
Figure 14: Comparison of test FID and transport costs (E² and (*)) of our IT method and CycleGAN.
Experiment
u
2
w 4
8
celeba + anime
0.447
0,309
0.275
0.225
handbag + shoes
0.327
0.328
0.263
0.264
Table 6: Test El transport cost of our IT maps (learned with E transport cost).
Concluding remarks. Our algorithm with w - oc allows us to achieve better similarity without the decrease of the image quality. At the same time, GANs fail do this when À oc. Why?
We again emphasize that typical GAN objective stimulates the model attain certain properties (realism, similarity the input, etc.). These terms, in general, contradict each other as they have different minima T. This yields the nasty trade-off between the loss terms. Our analysis shows that conceptually there is significant difference between CycleGAN and a more recent StarGAN-v2 model. More generally, any GAN-based method inherits realism-simiienn similarity tradcoff issue. GANs' differences are mostly related to the use of other architectures or additional losses. Therefore, we think that additional comparisons are excessive since they may not provide any new insights.
consists of several loss terms. Each term
In contrast, our method is not a sum of losses. Our objective (55) may look like a direct sum of a transport cost with an adversarial loss; method does have generator (transport maps T`) and discriminator (potential f) which are trained via the saddle-poin optimization objective max, miny. Yet, this visible similarity to GAN-hased methods is deceptive. Our objective max y minr can be viewed as a I Lagrangian and is atypical for GANs: the generator is in the inner optimization problem miny while in GANs the objective is minT maxy- In case, similar other neural dual OT methods, the generator is adversarial to the discriminator but not vice versa, as in GANs. Please consult 43 84.3], (24]
(00 for further discussion about OT methods.
GANs aim to balance loss terms Lpom and Lsi-- Our optimization objective enforces the constraint THP < wQ via learning the potential f (a.k.a. Lagrange multiplier) and among admissible maps T searches for the one providing the smallest transport cost. There is no realism- similarrty trade-off. emphasize that when
For completeness, decrease of the image quality, but because our method covers the less part of Q. FID negatively reacts to this 48 Fig. 1b].
oc, FID in Table Tb does not drop because of the
D Relation and Comparison with Discrete Partial OT Methods
The goal of domain translation is recover the map We approach this problem by approximating T with a neural network trained on the empirical samples X {z1.-... xN), Y = (y1, .v,,...,Bl. (us)) }. i.e., train datasets. Our method generalizes new (previously unseen, test) input samples Fnew ~ P, i.e, our learned map T can be applied to new input samples to generate new target samples T(xpew).
T(z) between two domains P. Q.
In contrast, discrete OT methods (including discrete partial OT) perform matching between the empirical distributions PPx >EN= 8e,,, Qas = Σm= 6 0g.. Thus, they do not provide out-of- sample estimation of the transport plan T neew) or map T(xnew). The reader may naturally wonder; why not to interpolate the solutions of discrete OT? For example, a common strategy is to derive barycentric projections T(x)= = fy ydx of the discrete OT plan æ and then learn
network (z) R T(x) to approximate them Below we study this approach and show that does not provide reasonable performance.
19

---

X-P
X-
T(x)
λ=0
T(x
λ=
A=50
1=50
T(x)
==100
Tux)
==100
==00
T1x1
T(x)
T(x)
A 3 30000 =
A=200
T(x
T(x)
T(x) A=500 A=300
T(x)
Tixi T(x)
Celeba (female) anime (64 64).
(b) Handbags shoes (128 x 128).
Figure 15: Unpaired translation via CycleGAN endowed with el identity loss with various weights X.
Pbo
4-0
A=0
1=1
1
A- 54
T50 50
-- 320
T1x1
100
2-200
A- 500
500
Celeba (female) anime (64x64)
Handbagy shoes (128x 128).
Figure 16: Unpaired translation via StarGAN-v2 endowed with e identity loss with various weights X.
20

---

TLx A=
A=
TUx
A=
10
Tik
Figure 17: Unpaired translation of handbags to shoes (128 x 128) via StarGAN-v2 endowed with el identity loss (A 10). Since StarGAN-v2 v2 is stochastic (one-to-many approach, visualize several generated samples for different noise vectors 2. Failures (poorly translated handbags which remain nearly unchanged) highlighted with red.
We perform evaluation of the BP approach on -animmee translation. We solve the discrete partial OT (DOT) between the parts of the train data X (1IK samples). Y (50K samples) We use ot. tt.parrill. paraalaaraaal....mmmammaa ppartaallasseerseeseaaalaaleleee wasserstein algorithm with parameters wp = m = 1 and vary w E w1. Then regress
{1, 2, 4, 8). see the notation in 4 This corresponds our IT (12) with UNet Ta to recover the barycentric projection T. We also simulate the case of w: oo by learning the discrete NNs the train dataset using NearestNei ghbors algorithm from sklearn. beearnnneiigtt neighbors. We experiment with using MSE or VGG-based perceptual errof as the loss function for regression. We visualize the obtained results Fig. 18 and report average test transport cost, FID Table
BP methods are known not to work well in large scale problems such as unpaired translation because of the averaging effect, see Figure 3 and large FID values BP in Table 1 of [17]. Indeed, one may learn a barycentric projection network Tg (x) fy ydn (y)zz) over the discrete OT plan I,
Metrics
2
4
W (pere.)
8 cost
0.298
0.199
0.184
0.167
0.158
0.165
FID
185.35
137.53
82.67
82.19
82.24
82.45
Table 7: Test e cost, FID of the DOT+BB BP method trained with 6 or perceptual loss function.
yet it is clear that fy sydd(yyla (:) direct weighted average of several images y, i.e., some blurry average image of poor quality. It is not satisfactory for practical applications.
Our qualitative results indeed show that BP approach for small leads to the averaging effect. We see that the train dataset this effect disappears with the increase of w, see Fig. [Sb] is expected, since with the increase of weight the conditional distribution of
175
UDI +UP
DOT+ (perc.)
150
(ouns
300
plan क (y(x) tends to a degenerate distribution concentrated at the nearest neighbor N (æ) of in the train dataset, i.c., (y)22) 5NN(()) when w - oc. This means, that in the limit the barycentric projection point x is its nearest neighbor NN.)..
25
0.10
0.20
0.25
0.30
However, the learned network (w = oo) does not generalize well unseen test samples and produces images of insufficient quality which is much worse than for the train samples, see Fig. 18a Despite the fact that test e cost and FID decrease with the increase of w, see
Figure 19: Test FID, L cost of our IT vs. DOT+BP.
We not use the whole datasets since computing discrete OT between them computationally infeasible. github. http:////..oaaaooooootott///aaaa http:////..ccttteeeteeeeeeeeette
21

---

X-PP
X-F
FIXI
W
T00
W8-
700
My 8
TOO
Foo (perc.l
Ti (penc.)
(a) Results on
(b) Results train set.
Figure 18: Unpaired translation with DOT+BP in celeba-+ anime experiment
visualized on test, train partitions.
Table 7 Fig. 19 generated test images have poor quality for all weights w. Yet, the FID scores as well as the e costs are much bigger than in our method in all the cases.
As the MSE error for regression is known not to work well in image tasks, we also conduct an experiment using the perceptual error function to learn Tg- Unfortunately, training the neural network with perceptual error does not lead to meaningful improvements, see the bottom lines of Fig. [8b] 18a Table This confirms that the origins of DOT+BP method's poor performance lie not in the regression part, but in the entire methodology based on barycentric projections.
To conclude, discrete OT methods not competitors work there is no straightforward and well-performin way to make oft-of-sample DOT estimation in large scale image processing tasks.
E
Experimental Details
Pre-processing. For all datasets, we rescale images' RGB channels to [-1, 1]. As in 40), we rescale aligned anime face images 512x512. Then do 256x256 crop with the center located 14 pixels above the image center to get the face. Finally, for all datasets except the textures dataset, we resize the images to the required size (64x64 128x 128). We apply random horizontal flipping augmentation to the comic faces and chairs datasets. Analogously to [42), we rescale describable textures to minimal border size of 300, do the random resized crop (from 128 300 pixels) and random horizontal, vertical flips. Next, we resize images to the required size (64 x 64 or 128 x 128).
Neural networks. In 5.1 we use fully connected networks both for the mapping Ta and potential fg. In $.2 we use UNet [60] architecture for the transport map Tg. We use WGAN-QC's [45 potential fø. We add additional final layer + x to f to make its outputs non-positive.
ResNet 30 discriminator
Optimization. We employ Adam 38 optimizer with the default betas both for To and fa. The learning rate is Ir = 10-4, We use the MultSSteLLR scheduler which decreases (r by 2 after (,,+-ww)K, (20+5-))K, (40+5-w)K, (70+5-w)K) iterations of fa where parameter. The batch size is X = 256 for toy 'Wi-Fi' |X] 4096 for toy Accept, and [X| = 64 for image-to-image translation experiments. The number of inner To iterations ky 10. In toy experiments, we observe convergence in = 30K total iterations of fø for 'Wi-Fi', in ~ 70K for Accept. In the image-to-image translation, we RS 70K iterations for 128 128 datasets, x 40K iterations for 64 x64 datasets. In the experiments with image-to-image translation experiments, we gradually increase w for 20K first iterations of fp. We start from w and linearly increase it to the desired (2, or 8).
21, 4, 8) a weight
22

---

Computational complexity. The complexity of training IT maps depends on the dataset, size of images and weight w. Convergence time increases with the increase of w: possible reasons for this are discussed in the unused samples limitation (Appendix A). In general, it takes from 2 (for 1) up to (for w 8) days on single Tesla V100 GPU.
Reproducibility. We provide the code for the experiments and will provide the trained models, see README.md. md.
F Proofs
Proof of Proposition 7 Since continuous is defined compact set X x y, it is uniformly continuous on X' x y. This means that there exists modulus of continuity w : [0, +oo) + [0, x))
such that for all (2,, y). (x', w²) X Y' it holds
c((: v) c(x', s/) S w|| 2'11x + 1ly v/ Iy);
and function w is monotone, continuous 0 with w0) = 0. In particular, for y y we have lc(x, u) c(x', y)1 I w(|lx - x' [xx) Thus, for c² (xx = mupp()) c(2, y). we have |c"
(xx)) < w (| - x' x1x), see 66 Box 1.8]. This means that c* : X - R is (uniformly) continuous.
Proof of Theorem D Since function (x.y) +> c(x, y) is continuous, there exists measurable se- lection T X + y from the set-valued map arg millyesupp()) c(x, y). see [2] Theorem 18.19). This map for all E X satisfies c(x; T(x)) = min dxr (a)) As a result, Sx c(, ((x) = fx e² (x) and is tight.
yESupp(Q)
Lemma 1. (Distinctness) Let μr M()).. Then p holds and only for every f E C())) satisfying J S 0 it holds that Jy ((y)dp(y) 2 ly f(y)dd(y).
Proof of Lemma If μ S v, then the incquality fy fz)d(( - ()) 2 0 for every (measurable)
S 0 follows from the definition of the Lebesgue integral. Below we prove the statement in the other direction.
p. The latter means there exists a measurable A C Y satisfying m(A) > v(A). Let = (p(A)- > 0. Consider the negative indicator function fA which equals - if E A and when y & A. Consider variation measure IV μ (M)) Thanks to (23) Proposition 7.9]. the continuous functions C(V) are dense in the space C (Iμ v1). Therefore, there exists a function fA,e E C(V) satisfying Sx (v) - (v)
Assume the opposite, i... fy f(y)d(u - vv) 2 for every continuous S but still ž
vl() < 6. We define (v) def non-positive continuous function, and for y E 3/ it holds that (s^(w) - [v) 2 (fa (v)) because fA takes only non-positive values {0, 11. We derive
< 0. This is
=v(A) ((A))-(A))-22
I (hcl))dl--v(e ( -)(()+ J - - fa(u))d(u u)
[a(o)d((
-2e / (15mc(0)) -fa-v) dlp vl(0)) s -2e / (fA.(()) - -f((V) -
--= 0,
which is a contradiction to the fact that fy f())d(w - vv))) 2 0 for every continuous f S 0. Thus, # S v.
Proof of Proposition To begin with, we prove that (I,, Q) is weak * compact set. Pick any sequence n. E T Q). It is bounded as all n, are probability measures ([]T^ | = Hence by the Manach-Alaogle theorem (62 Box 1.2], there exists subsequence nn, weakly-* converging to
some E MMX y). It remains to check that 11 (P, Q). Let (May Unn)) denote the marginals
23

---

of Tne and (1., v) be the marginals of x. Pick any f E C()) with f < O. Since THe E II", Q), it holds that I Vnn I w w ly ( f(v)d((w) S Sy dy)ddn (v) 00 (Lemma Db. We have
((Daaau))) - |
- ((V)dT = lim / |xzy d (I, - lim / f(y)dum (v). k
k-200
The latter limit is 2 w [ (V)dd(()) and I O. As this holds for every continuous - 0, we conclude that S 1/- S w By the analogous analysis one may prove that μ = and πT 2 0. Thus, 11 (P, Q) and (P, Q) is weak-* * compact.
The functional π + SxxY c(z, y) (x) y) continuous in the space M x )) equipped with weak-* topology because c: X' xx + RR is continuous. Since II (P, Q) is compact set, there exists x² E (P, ) attaining the minimum value theorem and ends the proof.
(P, Q). This follows from the Weierstrass extreme
Bibliographical remark. The results showing the existence of minimizers x² in partial OT already exist, see [10] Lemma 2.2] or [22 82]. They also provide the existence of minimizers in our IT problem [2]. Yet, the authors study the particular case when P. Q have densities on X C R For completeness, we include a separate proof of existence as we do not require the absolute continuity assumption. The proof is performed via the usual technique based on weak.* compactness in dual spaces and is analogous to [62] Theorem 1.4] which proves the existence of minimizers for OT problem (2) Our proof is slightly more technical due to the incquality constraint.
Proof of Proposition T
Let n² EII Q be an IT plan. Consider the OT problem between P and
min xE (g)) xxy
c(a, ())
(18)
turns out that n" is minimizer here. Assume the contrary, i.e., that there exists a more optimal r' E II(P, my) satisfying
J xxy dz,y)dT'(z, < f c(z, y)dd"("x,
(= Cost Q)).
(19)
xxx
This plan by the definition of [T(,, mg) satisfies T'a = TP and mi = = S wQ, i.e., T' E IT (P, Q). However, [19 contradicts the fact that x² is an IT plan in (8) as x provides smaller cost. Thus, min in (18) equals Cost,, Q) in (12).
Thanks to 62 Theorem 1.33], problem problem
18 has the same minimal value as the inf in the Monge's
inf / czz, T(x))d((xx)
(20)
TtP=a;
i... for every e > there exists T. X + y satisfying T.PP- म and (P, Q) + e. It remains to substitute this T. Monge's IT problem (II) get an e-close
transport cost to Kantorovich's 's IT cost ([2). As this works for every > 0, we conclude that min in 12) the same as inf in (II.
Proof of Theorem 2 The fact that + Cost,, (P, Q) is non non-increasing follows from the inclusion m (P. Q)
II "
(P. Q) for w1 < W2. This inclusion means that for larger values of w, the
minimization in (12) is performed over larger set of admissible plans. As for convexity, take any IT
plans "h E m (P, Q), T E u[= (I,, Q) for w1, W2, respectively. For any a [0, 1] consider the
mixture x' = az + a Note that Th = any th + (1 - a)m S awn Q + (1 a)w2Q=
(aw1 + (1 aawa Q. Therefore, n' Now (1-a)a (I. Q). We derive
Costaw +(1-))+11aaap) (P,
c(a,y)dT' (x,
xxX
[ c(z, (Ix,8)dT (z. + (1- / xxx
xxy c(z, y) (I,
aCostwr (I, + (1 - a Costun (P. Q),
(21)
24

---

which shows the convexity of w + Cost (P, Q).
Now prove that lim Cost, (P, Q) Co (PP, Q). For every 2 1 and a E [I,, Q) it holds that Ty S wQQ. This means that Su)p(Ty) C Supp(Q). As a result, we see that IT (TP, Q) c IT Q) i.e., Cost. (P, Q) 2 Cost (IP, Q). We already know that w + Cost (P,(Q is non-
increasing, so it suffices to show that for every > 0 there exists w = w(E) E [1, +20) such that
Cost, (P', Q) < Co (IP, Q + E. This will provide that lim Cost (P,, Q) Co (IP, Q).
Pick any > 0. Consider the set S del {(I,, 2) X x Y such that y E NN(2)). It is compact set. To see this, we pick any sequence (In: Mn. E S. It is contained in compact X x V. Therefore, has sub-sequence ( Ung) converging some (I, y) X x V. It remains check that (z, y) E S. Since Supp(Q) is compact and yn, E (N C Supp(Q). we have y E Supp(QQ as well. At the same time, by the continuity of c* (Proposition D and c, have
czz - c² (x) = lim {c(Tmg Yon)) c" [2mm))}= = lim 0 = 0,
1--000
k+000
which means that E (N()) and (x, v) E i.e. S is compact.
Since (z, y) + c( y) e* (x) is continuous function, for each (I,y) E S there exists open neighborhood Up x V2, c X x of (x,y) such that for all (x', (x'.")) E Un x V,, it holds that c(x', v/) - (x') < or, equivalently, ((x'.2/) < c* (x') + E. Since U U(ay)s U2 x Vy is open coverage of the compact set S, there exists a finite sub-coverage U UR, x Vyn of In particular, X' x== U Uz,. For convenience, we simplify the notation and put Un def Uz.. and Vn def Vyn..
Now we put U/ def U1 and iteratively define U,, def Un \ for 2 2. By the construction, holds that the entire space X is disjoint union of U", i.e., X' = - U", Some of U/r may be empty, so we just remove them from the sequence and for convenience assume that each U,, is not empty. Now consider the measure x E P(X x 3)) which is given by
def π
N
Pluy
X
Qlv. Q(V..)
(22)
Here for U E (x),,++++00) we use x to denote their product measure μ X V E EM(X x y). In turn, for measurable A C X,
μa|A to denote the restriction of μ to A, i.e., measure u' E (M)) satisfying n' = ((An B) for every measurable C X. Note that Σm PPu; and Σm= IP(()) = Ex= Plu: (UK) by the construction of U², At the same time, for each it holds that Q/v, ((V.)) is probability measure because of the normalization Q(V,). Note that this normalization is necessarily positive because V,, is a neighborhood of a point in Supp(Q). Therefore,
since sets U/ are disjoint and cover X, we have a En=
Pl Pluz 2==
N
P. Now let us show that there P(U VV
exists w such that Ty S wQ suffices to take w m- measurable A C y we have
Indeed, in this case for every
((NV))) Ty Ty(A) P(U)) (Vv.)
>ΣPUS P(U)) Q(A)
P(U)) Q(V,)) S wQ(A),
((v.)) S ((A)
Σ
which yields ny S w and means that a E (P, Q) for our chosen w. Now let us compute the cost of .:
N J C(I,U)dT(Z -
1 {
/1 c(x, v) c(c,))dallv (x) dP (1))
n=1
N
N
Q(v)) / (c)(z) + +c) () dQlv. (v) dP dPloz (xr) = -// Vv
00 (c)
==1
UA
==1
(x)+
/
Cost (P, + (23)
To finish the proof it remains to note that this plan is not necessarily a minimizer for 12 i.e. Jxxy c(z, (), y) is an upper bound on Cost (IP, Q). Therefore, we have Cost, (P. Costco (IP, Q) + e for our chosen w w(e).
<
25

---

Bibliographical remark. There exist seemingly related but actually different results in the fundamental OT literature. see [22 Lemma 2.1] or [T0 $3). There the authors study partial OT problem 4 and study how the partial OT plan and OT cost evolve when the marginals wolP and wrQ Q are fixed and the required mass amount to transport changes from 0 to min min(wo: w In our study, the first marginal wop and the amount of mass to transport m are fixed (wo = m 1), and we study how the OT cost changes when w1 + 0o in the IT problem.
Proof of Theorem 3 Note that P(x 3) is (weak-*) compact. This can be derived from the Banach- Alaoglu theorem analogously to the compactness of II (P, Q) in the proof of Theorem (2) Therefore, any sequence in P(X x ))) has converging uub-sequence, In our case, for brevity, we assume that T. E 1 (P. Q) itself weakly-* converges to some x C. P(x x y). Since T = IP for all n, we also have T P. As =0 Wn oo, we conclude from Theorem 2 that
Costoo (P, Q)- = lim Cost (P, lim / c(x, y)d "n (x, n n-700
"(,,)) = Sx JxXx cl, y(, (a, v),
n-000 xxxy
(24)
where the last equality holds since "h (weakly-*) converges to '². From 24 we see that the cost of n" is perfect and it remains to check that Supp(#;)) C Supp(Q). Assume the opposite and pick any y² Supp(mī) such that y* & Supp(Q). By the definition of the support, there exists 0 and a neighhorhood U = {y E y such that |1y y" Iyy < of y satisfying mī > 0 and
U' (upp(() (Q) = O. Let h(y) def max e- - |ly - y/ ]by)). From Th" I w (for all n), it follows that Supp( (m"") ) C Supp(() Therefore, F. (U) = 0 for all n. Since π converges to n²,, we have
lim / Myyd " (v) I M(y)dr(()) 12 R=+00
(25)
The left part is zero because hly) vanishes outside U and for h(y)dT" (y) 0 as T th (U) = 0. The
right part equals fer h(y)d==*()) (v) and is positive as xt (U) > 0 and h(y) > 0 for y E U. This is a contradiction. Therefore, Supp(=t) C Supp(Q). Now we see that ''" 1I (P, Q) is a perfect plan as its cost matches the perfect cost.
Proof of Corollary 7 Assume the inverse. Then 3e such that Vu(E) Ee 2 w[() and IT plan T" E I (P, Q) solving [12 such that V ET plan π², it holds that W1 (TT", x²) 2 E. This means that there exists an increasing sequence W1, 02 ..., Wn. - 0o and the corresponding sequence of IT plans x _ n2, ...., W', .... such that for every ET plan x² it holds that W, ( ","",, TT) 2 e for all n. At the same time, from Theorem 3 this sequence of plans must have a sub-sequence {n fr"" which is (weakly-*) converging to some ET plan x": x="** + 'T.. Recall that the convergence in Wi coicides with the weak convergence (for compact V), see [62] Theorem 5.9]. Hence, the sub-sequence
should also converge to xt in W, but it is not since W, (T TT) 2 E. This is a contradiction.
Proof Theorem Let (IP)) C P(X x y) denote the subset of probability measures æ E P(X x )) satistying Te = P. Consider a functional I II(P) + {0, +oo} defined by
I(T) def sup Jy (w (0o0(---(())))))))))) where the sup is taken over non-positive f E C()).
From Lemma we have I(TT) = 0 when x E (P, Q) and I(T) +oo otherwise. Indeed, if there exists a non-positive function satisfying fy ((y)d(u - (v) > O, then function Cf (for C > 0) also satisfies this condition and provides C'times bigger value which tends to co with C + co. We use ((T) incorporate the right constraint Ty I wQ in π E (IP Q) to the objective and obtain the equivalent to (12) problem:
/ xxy
clx, (d) min rell(P) { / ct,, (dr.)) + 16m)
min (FII(((.Q)
xxx
(x.v))d(Z,.l v) + sup / fly)d(wQ - f
-5
min <EII(P)
150. y
Xxy
/ c(xx,) ((x,))dT(T.))) / sly)d(wQ - m0)( (1)))(((==))() (26)
min sup (El(P)) fgo
Xxy
3
26

---

/ xxy
c(x, (). v)+ / flu)d(we- F(W)d((aR= m0)(00 (27)
sup min 150 xEll(F)
3
f(y)dTy(() (v)) + s(osaacco))
sup 550
min { (EIT(P)
(Zz
Xxy
y
I
f(y)dT(2, v) + [mmaainn (28)
sup rsu
min TELl(F)
c( c(r,y)dm (2,
Xxy
xxy
{ {
f
/1
[(y)d dP(x)) } + w [mmaaiin (29)
sup f50 xell(F)
min
clz, y)d
(TP()))
y
=dn=(2) x y
{
(c(x,)) y
+ w [())d(()) (30)
sup
min fgu (E)
In transition from 26 to (7 we use the minimax theorem to swap sup and min [64 Corollary 2]. This is possible because the expression in (26) is a bilinear functional of (T, f). Thus, is convex in π and concave in f. At the same time, II((P) is convex and (weak-*) compact set. The latter can be derived analogously to the compactness of IT (P, Q) in the proof of Theorem [ In transition from (28 to (29). we use the measure disintegration theorem to represent dz(x;, y) as the marginal
dr (x)
dP x and a family of conditional measures d' (y]x)) on V. We note that
min ! =ET(TT x y
(c(2r, v) - ((v)) (w))) (1)))d((()))))()) 2 min (c(s, ((v)) d((x)). yEy
(31)
=f)(2)
On the other hand, consider the measurable selection T X' + y for the set-valued map x + arg min (c(z. 9) f(y).. exists thanks to [2 Theorem 18.19]. As a result, for the deterministic
plan x [id, TiP, the minimum in (31 is indeed attained. Therefore, (31 is the equality. We combine (30) and 31 and obtain
I ((x.))dT(E,))) sup
{ ( $50
(LW))D((n) (32)
min Cost (P, (P.Q) xxy
It remains to prove that sup in the right part is actually attained some non-positive 1 C()).
Let fI, f2. C()?) be sequence of non-positive functions for which lim (sx (K()ddP())
w Jy fn (v)) = Cost (P, Q). For g E C(X), we define the (ra-)-tr (g) def
min [min (c(x,)) v) g(x)). 0J S O. It yields (uniformly) continuous non nos-positive function satisfy-
-.EX ing (v) - g (s/)) < w (Il - y |ly) where w is the modulus of continuity of c(x, v). This statement can be derived analogously to the proof of Proposition 1
Before going further, let us highlight two important facts which we are going to use below. Consider
any E C(X) and 0 > h E C()') satisfying g(x) + +(y)) S c(x, v) for all (z, v) E X x ). First, from the definition of (c, -transform, one can see that for all (z, v) E X x y it holds that 0 2 g(c-) > h and
g(x) + h(y) S g(x) + (2) S c(x,y))
(33)
i.e. (g. glc--))))))))))))) also satisfies the assumptions of (g, h)) Second, from the definition of c-transform, holds that h 2 g and
g(x) h(v) S (x) + h(y) c(x, w),
(34)
i... the pair (h h) satisfies the same assumptions (g. h).
Now we get back to our sequence fi, f2,... For each n and (I, y) E X' x Y, we have f2( +
fa(v) S v). Next,
fa(x) + fa(2)= f1(z) (1))()))))
(3))))
[ <<c(z (35)
27

---

where we first used (33) with (g. h) = (f% fn) and then used (34) with (g. h) = (fr: (fr) ( In
particular, we have fm _ ((1))(-))) and fn I (fa) We sum these inequalities with weights 1 and wo and for all (x, X x y obtain
(+()) + w = ((1R) + w (0- - (2(()) + (y),
(36)
where for convenience we denote hn def (U))(e)). Integrating (36) with (I, ~ P x Q yields
Jx (((z)d((x) + (.(()))00) - J h (z)dP(2)) / hnn (v)
(37)
This means that potential hn provides not smaller dual objective value than fn. As a result, sequence h1 h2... also satisfies lim (fx (x)d((()) + w Iy (v)dQ((())) Cost, (I,, Q). Now n-xcc forget about [1, J2,.. and work with l1,, h2,....
All the functions hn are uniformly equicontinuous they share the same modulus of continuity because they are (c, -) transforms by their definition. Let on (3) def hy) maxy'y h (y'). This function is also non-positive and uniformly continuous as well. Note that ea provides the same dual objective value as hy. This follows from the definition of of h + max hn (y'). Here the additive constant vanishes, i.e., (xr + Un (y) = (x) + hn,(v) At the same time, 6n are all uniformly bounded. Indeed, let yn y be any point where on (y)) 0. Then for all y E y holds that (.,, [v) (v) en (yn)) I (Ily yully) S w (ddiam)))). Therefore, by the Arzela-Ascoli theorem, there exists subsequence Vng uniformly converging to some / E C(X). As all Un, S O, holds that f S 0 as well. remains to check that f" attains the supremum in (32).
To begin with, we prove that e uniformly converges to (f*).. Denote || (x. v) E X' x V, we have
f = Ek. For all
c(r,N) - (v) Ek S c(I,1) Une (v) S c(a,, 1) v) - (") +
(38)
since Uvn - (-00 S | 11 < e. We take minyey in 38 and obtain (f)) - Fk= S
"n (ar) S (f)))()) + ck. As this holds for all x E X, we have just proved that I| )11 11 <
This means that of uniformly converges to (f*) as well since lim | f0100 = lim C Thanks to the uniform convergence, we have
lim {{
(om (())))))))))))))) + I ( + r
un / (mm.0))000))
Cost, (P,Q)
k0000
(39)
We conclude that f is maximizer of (32) that we seek for.
Bibliographical remark. There exists a duality formula for partial OT (4). see [10 $2] which can be reduced duality formula to IT problem (12). However, it is hard to relate the resulting formula with ours [3). We do not know how to derive one formula from the other. More importantly. it is unclear how to turn their formula the computational algorithm. Our formula provides an opportunity to do this by using the saddle point reformulation of the dual problem which nowadays becomes standard for neural OT, see 43 20 6T). We will give further comments after the next proof. The second part of the derivation of our formula (existence of maximizer f**) is inspired by the 62 Proposition 1.11] which shows the existence of maximizers for standard OT (2).
Proof of Theorem 5
By the definition of f*, we have
Cost (P,
min C(f", -T)= = min / ((), - Txx+y
f(()) S (40)
T:x
x / (f)
-
((())((()) = (41)
- (v) + w ((())((()))
28

---

Cost (IP, Q) / f (v)ddwQ TPI (v) < Cost (I, Q)
(42)
20 (Temma
This means that all the inequalities in 44)--42) are equalities. Since (40)
equals 41 we have
T E arg min (()"
Tx-+y
Bibliographic remark (theoretical part). The idea of the theorem is similar that of [6 Lemma 4.2], [24] Lemma 3). [43] Lemma 4], [20] Theorem 2] which prove that their respective saddle point objectives m miny C(f can be used recover optimal ' from some optimal saddle points (f*, Our functional (15) differs, and we have the constraint f S O. We again emphasize here that not for all the saddle points (f",T*) ) necessarily holds that T is the IT map, see the discussion in limitations (Appendix A
Bibliographic remark (algorithmic part). To derive our saddle point optimization problem (15). we use the c-transform expansion proposed by [53] in the context of Wasserstein GANs and later explored by [40 43 61
20 24 31 in the context of learning OT maps. That is, our resulting
algorithm | overlaps with the standard maximin neural OT solver, see, e.g., 24 Algorithm IJ. The
difference is in the constraint f < 0 and the additional multiplier w 2
Proof of Proposition From the proof of Theorem we see that fy (e (y) uQ - T'P (v) O. Recall that f* S 0. This means that ( for y E Supp uQ - TT) Indeed, assume the opposite, i.e., there exists some y E Supp Qw - TP) for which f() < 0. In this case, the same holds for all y/ in a small neighboorhood U of y as ʃ continuous. At the same time, Jy (y)d [ (v) I fo (")d (w)d(wQQTTH) (v) 0 since [WQ-T*HP is non-negative measure satisfying [wiQ - TPP (U) > 0 by the definition the support. This contradiction. To finish the proof remains note that Supp(() (Q) Supp(T"=PP) C. Supp(wQ TP),, i... f(y) for y E Supp(()) \ Supp(T* HP) as well.
Bibliographical remark. Treating functional C(f. T") in (16) Lagrangian, Proposition 4 can be viewed as a consequence of the complementary slackness in the Karush-Kulle Muhn-Tucker conditions
37
G
Additional Experimental Illustrations
G.1
Comparison with the Closed-form Solution for ET
In this section, we conduct Swiss2Ball experiment 2D demonstrating that for the sufficiently large parameter w. IT maps become fine approximations of the ground-truth ET map. We define source measure IP as uniform distribution on swiss roll centered (0, 0). Target measure Q is uniform distribution on ball centered at (0, 0) with radius R 0.5, i.e., Supp Q)) B(0, 0.5). We note that the supports of source and target measures are partially overlapping.
the proposed setup, the x (((00)).0.5) see
solution to ET problem (5) has a closed form: T(x) = x 1 (((.00))).. .r- R
Fig. 20f We provide the learned IT maps for w E {1, 3/2, 2, 32). see Fig. 20b 20e The qualitative and quantitative results show that with the increase of w our IT maps become closer and closer to the ground-truie -trutt ET one, see Table g
(a) Input, target measures.
(b) IT map, w=1.
(c) IT map, w w= 3/2.
(d) IT map, w w= 2.
(e) IT map,
(l) Extremal transport map.
w 32.
Figure 20: Incomplete Transport (IT) maps learned with c(x, v) = || Ell transport cost
and ground-truth Extremal Transport (ET) map in SSiss22all experiment.
29

---

w
3/2
2
32
MSE(T, T))
0.0136
0.0026
0.0009
7.98e-06
Table 8: MSE(T, T*) between learned IT maps T (w 2,,3)) and ground-truth ET map T".
G.2 Solving Fake Solutions Issue with Weak Kernel Cost
As we discuss in Appendix A saddle-point neural OT methods (including our IT algorithm) may suffer from,fak solutions issue. As it is proved in 422 this issue can be eliminated by considering OT with the so-called weak kernel cost functions. this section, we test the effect of using them in our IT algorithm. Specifically, we demonstrate the example where IT algorithm with the cost function c(x; y) = | - u//2 struggles from fake solutions, while with the same cost endowed with weak kernel regularization, i.e., kernel cost 42 Equation (16) with parameters = 1,7 = 0.4, resolves the issue. Following [42]. we consider stochastie version IT map Tzx; 2) using noise = ~ (O, T) as additional input.
We design the Ball2Circle example in 2D, where input P is uniform distribution on a ball and target Q on a ring embracing the ball. The solution of ET problem is an internal circuit of a ring, see Fig. 21a We learn IT maps for c(z, y) || vll2. with (y 0.4) or without (y 0) kernel regularization for weights w E 21,2,32)
-10
(a) Input, target
(b) IT map.w=1 (c) IT map.
(d) IT map, w= (e) IT map. W 2 (iter=7K)
(1) IT map, w= ==
measures.
(iter=7K) w= (iter=8K)
(iter=8K).
Figure 21: Incomplete Transport (IT) maps learned with c(r, y) | yll transport cost in 'Ball2Circle' experiment. We observe that training is highly unstable for w E {1. 2}, see the
solutions for nearby iterations of training (b-c) and (d-e) respectively. Increase of the weight w helps to improve the stability (f).
6.75
map
Mipoeed y- Tox
Mapped - TIV)
Mapped TM ET map
Tarcel y
0.50
0.5
0.00-
0.25
-030
0.75
-0.5
0.0
0.5
-05
0.0
0.
-05
0.0
0.5
-25
0.0
0.5
(a) Input, target measures and ET map.
(b) IT map. w 1.
(c) IT map.
(d) map,
W w=2 2.
w = 32.
Figure 22: Incomplete transport (IT) maps learned with weak kernel cost in 'Ball2Circle' experiment for a fixed noise z. Usage of the kernel regularization + stochastic map T(x, 2) helps to overcome instability issues for weights w E (1,2).
method / weight w/o kerne regularization
w =
w
w 32
0.0022
with kemnel regularization
0.1377
0.0730
0.0495
Table 9; MSE(T, T between IT maps (w {1, 2, 32)) learned with c(2, y) = || - -y y11
(with and without weak kernel regularization) and the ground -ruth ET map. MSE for IT map learned with kernel regularization is larger (see = 32) than without the regularization since it introduces small bias to the optimization.
30

---

Discussion. We observe that without kernel regularization training of IT method is highly unstable (for {1, see Fig. 21b 21d Interestingly, with the increase of the weight w, the issue disappears and for w 32, IT map is close to the ground-truth ET one (Fig. 21r
The usage of kernel regularization helps to improve stability of the method, see Fig. 22 However, while MSE between learned and ground-truth ET map drops with the increase of w, for w 32 it is bigger than that of learned IT maps without regularization. It is expected, since using regularizations usually leads to some bias in the solutions.
Thus, the example shows that (a) fake solutions may be problem, (b) kernel regularization from 42 may help to deal with them. However, further studying this aspect is out the scope of the paper.
G.3 Perceptual Cost
In this section, we show that the stated conclusions hold true for the transport costs other than L For this purpose, we perform additional experiments using perceptual transport cost from [24). We use the same hyperparameters as in our experiments with l cost.
X-
7(x)
W
T(x)
w 2
Tux)
Tod)
8
Figure 23: Celeba (female) - anime (64 64 image size, perceptual cost).
Metries
2
8
Test
9.21
12.98
17.24
22.08
Test perceptual cost
0.954
0.794
0.667
0.545
Test l cost
0.303
0.209
0.153
0.103
Table 10: Test FID and 2
perceptual transport costs of our IT maps (learned with perceptual transport cost).
Experimental results. Qualitative results show that that similarity of input images æ and the images F(x) translated by our IT method trained with perceptual cost grows with the increase the parameter w, Figure 23 In 10 quantitatively verify these observations by showing that both perceptual and l mean transport costs between input and translated images decrease with the increase w. Interestingly, see that IT trained with perceptual cost yields smaller FID than IT method trained with l cost.
G.4 Bigger Weight Parameters
In this section, we present the results of IT method trained with e cost and parameters 16, 32. We see that in contrast to CycleGAN which does not translate face images to anime images in case of big parameters X, our IT method continues to translate faces to anime even for big parameters We quantify the obtained results in Table [I] As expected, mean transport costs are decreasing with the increase of while FID is slightly increasing. We present the qualitative results for additional weights Figure
31

---

Main results
Additional results
Metrics
w
8
w
w
Test FID
14.65
20.79
22.18
22.84
24.86
28.28
Test C cost
0.297
0.154
0.133
0.094
0.091
0.083
Table 11: Test FID and l transport costs of our IT maps.
G.5
Additional Results for e² Cost
71x)
1
7(x)
2
f(x)
W 4
T(x)
W 8
W 16
f(x)
32
7(x)
Figure 24: Celeba (female) + anime (64 x 64).
T(X)
TeX)
7100
W
Figure 25: Handbag - shoes (128x 128).
32

---

X-2
100
W #=1 1
W 2
TXX)
W 4
TUX) w=B
Figure 26: Textures - chairs x64x64).
X-
TXX
W
W
T0X
W
TOO
Figure 27: Ffhq + comics (128 128).
33


Reviews:
[{"review_id": "lNMOANhR4v", "reviewer": "Reviewer_iXGC", "summary": "This paper proposes a novel notion of extremal transport, which relaxes the optimal transport problem by only requiring the support of the pushed-forward distribution to be a subset of the support of the target distribution. To solve this problem, the authors propose a novel approximation approach to find the solution from a subsequence of a series of incomplete OT problems (where T#P = Q is relaxed to T#P < wQ, w >= 1, when w=1 this is the traditional OT problem). Then the author derives novel dual formulations of the incomplete OT problems, which the author proposes to solve by using neural networks to approximate the potential and c-transform solutions. The authors apply the method to toy sets and image translation examples to demonstrate the scalability of the method. FID results on the image translation example prove the concept of the method. \n\nThe authors carefully compare their results with related works and establish their theoretic novelty. The presentation of the results are clear and potential impacts are well discussed.", "questions": "One question: in theorem 3, it only guarantees the existence of a subsequence. In practice, if we found a sequence of solutions by Alg. 1, how can we make sure whether it is the desired ET solution?", "limitations": "The limitation of the paper is adequately addressed by the authors. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper proves several strong theoretical results on the relaxed versions of OT problems (i.e. ET and IT). The theoretic study of the solutions to these problems is fruitful. This opens up a new domain of study area in the optimal transport area. ", "weaknesses": "Overall the theoretic results are rigorous and novel. To solve the solution of the dual formulation of IT, the authors propose to use neural networks to approximate the transport map (necessary for solving large-scale problems). One concern I have is that in the traditional OT problem, the OT map is in general discontinuous. This proposes difficulties in using DNN to approximate the OT map. It would be very welcomed if results on the regularity of the IT maps are presented, and/or how well the neural network can approximate such maps. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your comments. Here are the answers to your questions.\n\n**(1) In the traditional OT problem, the OT map is in general discontinuous. This proposes difficulties in using DNN to approximate the OT map. It would be very welcomed if results on the regularity of the IT maps are presented, and/or how well the neural network can approximate such maps.**\n\n**Regularity.** In the proof of Proposition 3 (Appendix F, line 772), we derive an auxiliary statement that if $\\pi^* \\in\\Pi^w(\\mathbb{P},\\mathbb{Q})$ is an IT plan between $\\mathbb{P}$ and $\\mathbb{Q}$, then it is an OT plan between $\\mathbb{P}$ and $\\pi_{y}^{\\*}$. This also leads to the fact that IT maps $T^{*}$ between $\\mathbb{P}$ and $\\mathbb{Q}$ are the OT maps between $\\mathbb{P}$ and $T^{\\*}_{\\sharp}\\mathbb{P}$. Hence, it seems like the results on their regularity may be potentially derived from the general regularity properties of OT maps, see [1], but this requires further studies.\n\n**DNN approximation.** Fortunately, from the practical point of view, we can show that IT maps **can** be approximated with neural networks. As it is shown in [2, Theorem 1], assuming that the target distribution has finite second moment, neural networks can arbitrary well approximate the OT map (and hence our IT map) w.r.t. the $\\mathcal{L}^2(\\mathbb{P})$ norm. The authors provided a concise proof for stochastic OT maps but there are no significant changes when we turn to the deterministic case.\n\nTo conclude, neural networks can arbitrarily well approximate IT maps.\n\n**(2) In theorem 3, it only guarantees the existence of a subsequence. In practice, if we found a sequence of solutions by Alg. 1, how can we make sure whether it is the desired ET solution?**\n\nIndeed, different sub-sequences might converge to different ET plans and whole sequence might be non-converging itself. To address your question, we provide a short corollary from our Theorem 3 showing that with the increase of weight $w$, elements of any such sequence become closer to **set** of ET plans.  \n\n*Corollary.* $\\forall\\varepsilon>0$ $ \\exists w(\\varepsilon)\\in[1,\\infty)$ such that $\\forall w \\geq w(\\varepsilon)$ and $\\forall$ IT plan $\\pi^w\\in\\Pi_w(\\mathbb{P}, \\mathbb{Q})$ solving Kantorovich's IT problem (equation (12) in our paper), there exists a ET plan $\\pi^\\*$ which is $\\varepsilon$-close to $\\pi^w$ in $\\mathbb{W}_1$, i.e., $\\mathbb{W}_1(\\pi^\\*, \\pi^w)\\leq \\varepsilon$.\n\n*Proof.* Assume the inverse. Then $\\exists \\varepsilon$ such that $\\forall w(\\varepsilon)$ $\\exists w \\geq w(\\varepsilon)$ and $\\exists$ IT plan $\\pi^w\\in \\Pi_w(\\mathbb{P}, \\mathbb{Q})$ solving (12) such that $\\forall$ ET plan $\\pi^\\*$, it holds that $\\mathbb{W}\\_1 (\\pi^w, \\pi^\\*)\\geq \\varepsilon$. Pick a sequence $w_1, w_2, ..., w_n \\rightarrow \\infty$ and the corresponding sequence of IT plans $\\pi^{w_1}, \\pi^{w_2}, ..., \\pi^{w_n}$.  From Theorem 3, it has a sub-sequence (weakly-*) converging to some ET plan $\\pi^\\*$: $\\pi^{w^{n_k}}\\rightarrow \\pi^\\*$. However, $\\forall n_k$ $\\exists w \\geq w_{n_k}$, such that $\\mathbb{W}\\_1(\\pi^{w^{n_k}}, \\pi^{\\*}) \\geq \\mathbb{W}\\_1(\\pi^{w}, \\pi^{\\*}) \\geq \\varepsilon$. Hence, the sub-sequence does not converge to $\\pi^{\\*}$ in $\\mathbb{W}\\_{1}$. \nRecall that the convergence in $\\mathbb{W}\\_{1}$ coicides with the weak-$\\*$ convergence (for compact $\\mathcal{X},\\mathcal{Y}$), see [3, Theorem 5.9]. Hence, the subsequence also does not weakly-* converge to $\\pi^{\\*}$ which is a contradiction. $\\square$\n\n\n**Concluding remarks**. Please respond to our post to let us know if the clarifications above suitably address your concerns about our work. We are happy to address any remaining points during the discussion phase; if the responses above are sufficient, we kindly ask that you consider raising your score.\n\n**References.** \n\n[1] De Philippis, G., & Figalli, A. (2015). Partial regularity for optimal transport maps. Publications mathématiques de l'IHÉS, 121(1), 81-112.\n\n[2] Korotin, A., Selikhanovych, D., & Burnaev, E. (2022, September). Neural Optimal Transport. In The Eleventh International Conference on Learning Representations.\n\n[3] Santambrogio, F. (2015). Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63), 94."}, {"review_id": "KbuPuubRii", "reviewer": "Reviewer_Mz3K", "summary": "This paper introduces the concept of extremal Optimal Transport (OT) and proposes the use of incomplete OT as a solution to the extremal OT problem. The authors present a duality method to address the incomplete OT problem and validate this approach using a toy 2D dataset and image translation tasks.", "questions": "Figure 5b may not be as illustrative as intended. In this case, it seems that pi would still uniquely correspond to a certain deterministic transport map. Perhaps it would be more instructive to provide an example where (8) admits multiple minimizers, such as a scenario where the support is not convex?", "limitations": ".", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The authors offer the analysis of the proposed problems and algorithms, including the existence of Extremal Transport (ET), the presence of Incomplete Transport (IT), and the convergence of IT plans to the ET plans.\n\nThey test their algorithms on several image translation datasets, demonstrating the ability to manipulate the similarity between the source image and the generated image by adjusting the weight parameter $w$.\n\nTheir algorithm exhibits the capability to map the data towards a portion of the target distribution's support.\n", "weaknesses": "## Motivation\n\nFirstly, the paper's logic doesn't fully convince me. The authors initially propose to solve the Extremal Transport (ET) problem, but then shift to solving the Incomplete Transport (IT) problem, presumably because the ET problem is too challenging. However, based on their experimental results, it seems more logical to propose solving the IT problem directly, as most of their visualizations demonstrate that adjusting the weight parameter $w$ controls the similarity between the source image and the generated image. If the authors are indeed intent on solving the ET problem, could they provide experimental evidence to support this? For instance, they could design some distributions that have a closed-form solution for ET, and then compare the ground truth minimum value of problem (5) with their simulation results.\n\nRegarding the motivation for problem (11): the authors state that \"In practice, solving the extremal problem (5) is challenging because it is hard to enforce Supp($T \\sharp P$) $\\subset$ Supp($Q$)\", but isn't this relatively straightforward for image tasks? Since images are typically scaled to a certain range like [-1,1], we can simply scale the images to meet this support requirement.\n\nI believe that the application of incomplete OT or extremal OT could be limited in image tasks, especially extremal OT, as multiple data points could be mapped to the same data point, resulting in generated images with limited diversity.\n\n## Method\n\nRegarding the relaxation from problem 5 to 11, it seems to me that the constraint in 11 is not a softened version, but rather a stronger one. To satisfy the constraint in (11), one must also satisfy the constraint in (5). This is because in the constraint of (11), if Q=0, then regardless of the value of $w$, $T\\sharp P$ must also be zero, which aligns with the constraint in (5). Why is it not feasible to design a dual formula for ET directly?\n\nThe authors mention the issue of fake solutions. Could they consider borrowing ideas from the Kernel Neural OT paper? It seems that using a similar cost from Kernel Neural OT could enhance this paper, and it seems not that difficult?\n\n## Results\n\nGiven that the motivation of this paper is to solve the extremal OT problem, could the authors clarify under what conditions their method can recover the solution to extremal OT? Specifically, how large does the value of $w$ need to be? It's possible that this information is already included, and I may have overlooked it.\n\nThe authors acknowledge that the FID is not particularly meaningful when $w>1$, yet it appears to be the primary metric used in this paper. If the authors believe that FID is not representative, why do they present so many FID results? They also claim that the image quality of the translated image does not decrease with increasing $w$. Is there a way to verify this quantitatively, perhaps with a metric based on the image itself rather than the image distribution?\n\nSome of the results presented in this paper seem less than satisfactory. For instance, in Figure 24, even when $w$ is large, some images fail to preserve hair colors. In Figure 22, as $w$ increases, some images exhibit unrealistic artifacts (e.g., the first grey shoe and the black saddle have strange bands on them), likely because the generated image is forced to share more similarity with the source image. Could this be a limitation of the proposed method?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your comments. Here are the answers to your questions.\n\n**(1) Design distributions that have a closed-for ET solution. Compare simulation results with the ground truth.**\n\nWe conduct *Swiss2Ball* experiment in 2D, see Fig. 1, Table 1 in **the attached PDF file**. Here the supports of source and target measures are partially overlapping and the solution to ET problem (5) has a closed form:\n$ T(x) = x \\cdot 1_{x\\in B((0,0), 0.5)} + x \\cdot \\frac{R}{\\|x\\|\\_2} \\cdot 1_{x\\notin B((0,0), 0.5)} $, see Fig. (1a). We provide the learned IT maps for $w\\in \\\\{1, \\frac{3}{2}, 2, 32\\\\}$, see Fig. (1b-1e). The quantitative results show that with the increase of $w$ our IT maps become closer and closer to the  grund-truth ET one (Table 1).\n\n**(2) Isn't \"Supp$(T\\sharp\\mathbb{P}) \\subset$ Supp$(\\mathbb{Q})$\" relatively straightforward for image tasks?**\n\nWe use the standard mathematical definition of the support (lines 39-40), i.e., the support of a non-negative mesure $\\mu$ is a closed set consisting of all points $x \\in X$ for which every open neighbourhood $A\\ni x$ satisfies $\\mu(A)>0$. Following the standard manifold hypothesis [1], for a real data distribution $\\mathbb{Q}$ (e.g., distribution of images of faces) and $\\mathcal{Y}=[-1,1]^{D}$, one may think of Supp$(\\mathbb{Q})\\subset [-1,1]^{D}$ as of a small-dimensional manifold occupying a tiny part of the ambient space $[-1,1]^{D}$. In general, this manifold is unknown and we observe only some random data samples lying on it. This is the reason why enforcing the constraint Supp($T\\sharp \\mathbb{P}$) $\\subset$ Supp($\\mathbb{Q}$) is tricky in practice.\n\n**(3) The application of IT or ET could be limited in image tasks due to limited diversity issue.**\n\nWe discussed this issue as a limitation of our method in Appendix A (lines 503-509). However, we emphasize that it is a dataset-dependent problem which may appear only in specific dataset cases like in our *texture* to *chair* translation example, see Fig. 9A. For clarity, we additionally demonstrated it on a specially designed toy example, see Fig. 10A.\n\n**(4.1) The constraint in (11) is not a softened version of (5).**\n\nIndeed, 'softened version' may be not the best formulation in this case since the constraint $T\\sharp\\mathbb{P}\\leq \\mathbb{Q}$ is indeed stronger. However, the constraint $T_{\\sharp}\\mathbb{P} \\leq \\mathbb{Q}$ is more computationally feasible in practice and our answer to your question below explains why. *We will change the word 'soften' in section 3.2.*\n\n**(4.2) Why is it not feasible to design a dual formula for ET directly?**\n\nMost of the duality formulas in OT field are derived using the ideas of the Largrange multiplier method. It is applicable to equality contraints such as $T_{\\sharp}\\mathbb{P}=\\mathbb{Q}$ or inequality constraints like $T_{\\sharp}\\mathbb{P}\\leq w \\mathbb{Q}$. It is not clear how to incorporate the set inclusion constraints such as $Supp(T\\sharp\\mathbb{P})\\subset Supp(\\mathbb{Q})$. This is why we need the transition from ET to IT.\n\n**(5) You mention fake solutions issue. Consider using ideas from the Kernel NOT paper.**\n\nWe perform additional *Ball2Circle* experiment, see **the attached PDF file**, demonstrating the effect of using kernel cost function for alleviating fake solutions issue. We learn IT maps for $c(x, y)=\\|x-y\\|_2$ with or w/o regularization for weights $w\\in\\\\{1,2,32\\\\}$.\n\nWithout regularization, we observe that the method is unstable (for $w\\in\\{1,2\\}$), see Fig. 2b-e. In contrast, with  kernel regularization (+stochastic map $T(x,z)$) [2] the method always converges, see Fig. 3.\n\nOur example shows (a) fake solutions may be a problem and (b) regularization may help to deal with them. Further studying this aspect is out of the scope of the paper.\n\n**(6) Under which conditions the method can recover the ET solution? How large does the value of w need to be?**\n\nIf we correctly understand, you ask for a concrete convergence rate of IT plans $\\pi^{w}$ to ET plans $\\pi^{*}$ as a function of $w$. We do not specify the rate of convergence and leave this aspect for future studies (see lines 168-170).\n\n**(7) FID and metrics based on images itself.**\n\nWe use the FID metric simply because there are no principally different alternatives. In fact, all the metrics for generative models which we have seen evaluate set-to-set similarity rather than the quality of individual samples. Moreover, in the *unpaired* translation task the evaluation based on individual images (e.g., paired metrics) seems to be not applicable. \n\n**(8) In Figure 24, some images fail to preserve hair colors. In Figure 22, some images exhibit unrealistic artifacts. Could this be a limitation?**\n\nWe agree with the reviewer that in Figure 24, the hair colors are not preserved. However, we need to explain that it is the **expected behaviour** since we aim to solve the problem of *'mapping to the nearest neighbor in a target dataset'*. Thus, if this target dataset does not contain samples with the same hair color as in input image, our model is not intented and should not keep the color. Regarding artifacts in Figure 22, we note that they occur since the dataset is rather challenging.\n\n**(9) Figure 5b may not be as illustrative as intended. <...> Provide an example where (8) admits multiple minimizers, e.g. when support is not convex?**\n\n*We will replace the picture in the final version of our paper with the new one where $\\mathbb{Q}$'s support is non-convex.*\n\n**Concluding remarks**. Please respond to our post to let us know if the clarifications above suitably address your concerns about our work. We are happy to address any remaining points during the discussion phase; if the responses above are sufficient, we kindly ask that you consider raising your score.\n\n**References.**\n\n[1] Fefferman, et al. (2016). Testing the manifold hypothesis.\n\n[2] Korotin, A. et al. (2022). Kernel neural optimal transport."}, {"review_id": "iCO9hFYfSD", "reviewer": "Reviewer_URfJ", "summary": "This paper introduces a mathematical formalization called \"extremal transport\" that aims to achieve optimal translation between unpaired domains based on a given similarity function. Additionally, the paper proposes a scalable algorithm that utilizes neural optimal transport to approximate extremal transport mappings. The algorithm is tested on toy examples and the image-to-image translation task, yielding promising results.", "questions": "In lines 121-124, how the lower bound is defined during the process of analyzing and constructing upper and lower bounds to simplify the objective is not mentioned. The reason why value(8) admits more minimizers is also not explained.\n\nIn lines 133-136, an explanation is needed for the replacement mentioned here and why using a finite parameter w can achieve the desired replacement of Supp(T#P) belonging to Supp(Q).\n\nIn lines 218-220, it is asked whether the method presented in the paper scales to high dimensions. If images are defined as high-dimensional, this should be clarified from the beginning of the paper.", "limitations": "The paper has conducted extensive discussions.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper introduces a novel mathematical formalization called extremal transport for achieving optimal translation between unpaired domains. Additionally, the concept of neural optimal transport is introduced and applied in the algorithm. These theoretical foundations provide a solid basis for the algorithm design.\n\nThe algorithm is tested on toy examples and the image-to-image translation task, demonstrating good results. These experiments validate the effectiveness and scalability of the algorithm.\n\nImage-to-image translation is an important problem in computer vision, and the proposed algorithm can be applied to address this problem. Furthermore, the paper mentions other potential application areas, such as single-cell data analysis in biology.\n\nThe algorithm proposed in this paper can be widely applied to solve translation problems between unpaired domains, making it highly generalizable. Additionally, a new method called partial optimal transport is introduced, which can be used to address alignment problems between imbalanced measures, further expanding its potential for generalization.", "weaknesses": "Based on the information provided, the paper primarily focuses on the common main features of existing approaches rather than encompassing all of them. It's possible that due to space constraints, some concepts or details may not be extensively elaborated in the main paper. However, substantial explanations are provided in the Appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your comments. Here are the answers to your questions.\n\n**(1a) In lines 121-124, how the lower bound is defined during the process of analyzing and constructing upper and lower bounds to simplify the objective is not mentioned.**\n\nEquation (10) states that for any $\\pi\\in\\Pi^{\\infty}(\\mathbb{P},\\mathbb{Q})$  it holds (for $\\mathbb{P}$-almost all $x\\in\\mathcal{X}$) that: $c^{\\*}(x)=\\min_{y\\in Supp(\\mathbb{Q})}c(x,y)\\leq \\int_{\\mathcal{Y}}c(x,y)d\\pi(y|x)$. \nIf we now integrate the equation (10) with respect to $x\\sim\\mathbb{P}=\\pi_{x}$ and take $\\inf$ over all admissible plans, we get the following inequality: \n$\\int_{\\mathcal{X}}c^{\\*}(x)d\\mathbb{P}(x)\\leq \\inf_{\\pi\\in\\Pi^{\\infty}(\\mathbb{P},\\mathbb{Q})}\\int_{\\mathcal{X}\\times\\mathcal{Y}}c(x,y)d\\pi(x,y)$. It shows that indeed $\\int_{\\mathcal{X}}c^{\\*}(x)d\\mathbb{P}(x)$ is a lower bound for equation (8).\nAt the same time, as we write in lines 102-103, $\\int_{\\mathcal{X}}c^{\\*}(x)d\\mathbb{P}(x)$ is also a lower bound for equation (5). From our Theorem 1 we see that there exists measurable map $T^\\*$ minimizing (5) such that the bound is tight. It automatically yields existence of a deterministic plan $\\pi^\\*(y|x)=\\delta_{T^\\*(x)}$ such that (8)=$\\int_{\\mathcal{X}}c^{\\*}(x)d\\mathbb{P}(x)$=(5). *We will add these details to the final version of our paper.*\n\n**(1b) The reason why value (8) admits more minimizers is also not explained.**\n\nThis fact follows from the definitions of Monge's and Kantorovich's Extremal Transport (ET) formulations. Indeed, like in the general OT theory, Kantorovich's ET formulation (8) is an extension of Monge's one (5). If there exists a minimizer $T^\\*$ of equation (5), then it yields the corresponding deterministic minimizer $\\pi^\\*(y|x)=\\delta_{T^\\*(x)}$ of (8). However, Kantorovich's formulation allows to split the mass between nearest neighbors and, therefore, may potentially admit more minimizers. \n\n*Example.* Consider $\\mathcal{X}=\\mathcal{Y}=[-1,1]$. Let $\\mathbb{P}=\\delta_0$ and $\\mathbb{Q}=\\frac{1}{2}\\delta_{-1}+\\frac{1}{2}\\delta_1$ be distributions concentrated at $\\{0\\}$ and $\\{-1, 1\\}$ respectively. Let $c(x, y)=\\frac{1}{2}\\|x-y\\|^{2}$ be the quadratic cost. Then there are obviously two extremal OT maps $T^\\*$ delivering minimum to Monge's ET  problem: $T^\\*(0)=-1$ and $T^\\*(0)=1$. At the same time, there are infinitely many minimizers $\\pi^{\\*}$ of the Kantrorovich's problem (8). Indeed, all the plans distributing the mass of $\\mathbb{P}$ between points $\\{-1\\}$, $\\{1\\}$, i.e., satisfying $\\pi(0, -1)=m$, $\\pi(0, 1)=1-m$ are minimizers for $m\\in [0,1]$. \n\n**(2) In lines 133-136, an explanation is needed for the replacement mentioned here and why using a finite parameter $w$ can achieve the desired replacement of $Supp(T\\sharp\\mathbb{P})$ belonging to $Supp(\\mathbb{Q})$.**\n\nFor an arbitrary finite parameter $w$, the condition $Supp(T_{\\sharp}\\mathbb{P}) \\subset Supp(\\mathbb{Q})$ implies $T_{\\sharp}\\mathbb{P}\\leq w \\mathbb{Q}$. As we show in our paper, in the limit $w\\rightarrow\\infty$, the solutions to IT problem converge to the ET in a certain sense. At the same time, the replacement of ET with IT is desired as the latter one admits the dual formulation (which we derive) that can be efficiently solved with neural networks. How to directly enforce the ET condition $Supp(T_{\\sharp}\\mathbb{P}) \\subset Supp(\\mathbb{Q})$ in practice is an open problem.\n\n**(3) In lines 218-220, it is asked whether the method presented in the paper scales to high dimensions. If images are defined as high-dimensional, this should be clarified from the beginning of the paper.**\n\nThank you for noting this aspect. *We will add the clarifications to the final version of our paper.*\n\n**Concluding remarks**. Please respond to our post to let us know if the clarifications above suitably address your concerns about our work. We are happy to address any remaining points during the discussion phase."}, {"review_id": "dVQ1eTkazm", "reviewer": "Reviewer_Cqh5", "summary": "The paper proposes extremal transport (ET), a mathematical framework for achieving the best possible unpaired translation between two domains based on a given similarity function, and proving that ET maps can be learned as a limit of specific partial optimal transport (OT) problem. The contributions of the paper include a formalization of ET as a rigorous mathematical task, the characterization of ET maps and plans through a connection to nearest neighbors, and the derivation of an efficient computational algorithm based on partial optimal transport. The proposed algorithm is evaluated using 2D examples and the unpaired image-to-image translation task.", "questions": "Why the ET problem is defined in the compact polish spaces？Could it transfer to other spaces?", "limitations": "The ℓ2 and FID metrics have some limitations in characterizing the effectiveness of the method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The logic of this paper is well organized, and also the mathematical formulas are well defined.\n2.The work demonstrates that it is possible to relax equality constraints to inequality constraints especially for some situations where enforcing rigorous equal constraints are difficult, and proposes incomplete transport (IT) to approximate ET maps using partial optimal transport (OT) problems, which is very novel.\n3.The experimental part is quite sufficient complete and proves the effectiveness of the proposed method.", "weaknesses": "It is not clarified the motivations of defining ET problem and the relationship between specific task such as unpaired image translation and the mathematical ET problem.The process from abstraction of practical problems to theoretical derivation is too steep.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your comments. Here are the answers to your questions.\n\n**(1) It is not clarified the motivations of defining ET problem and the relationship between specific task such as unpaired image translation and the mathematical ET problem.The process from abstraction of practical problems to theoretical derivation is too steep.**\n\nWe thank reviewer for pointing this. Our choice to consider unpaired image translation problem in the context of ET was motivated by the fact that recovering good similarity of translated samples to input samples may be of high importance in certain image-to-image translation tasks (lines 222-233).\n\n**(2) Why the ET problem is defined in the compact Polish spaces. Could it transfer to other spaces?**\n\n\n**Compactness.** We set the spaces $\\mathcal{X}$ and $\\mathcal{Y}$ to be compact as it is a natural property which holds for various real-world distributions, e.g., images. At the same time, the compactness assumption notably shortens the derivation of the theoretical results, e.g., $\\inf$/$\\sup$ can be automatically replaced by $\\min$/$\\max$ everywhere simplifying derivations, etc. We think that most of our results can be generalized to non-compact spaces but we leave this for future theoretical studies.\n\n**Polish spaces.** Recall that a Polish space is a *separable completely metrizable topological space* (and $\\mathbb{R}^{D}$ is an example). Its metrizable property yields the equivalence between compactness and sequential compactness which is simpler to work with (we use it, e.g., in our Theorem 3). Its separability is required in Banach-Alaouglu theorem which we use in our Proposition 2. Completeness holds automatically due to the compactness assumption. \n\n**(3) The $\\ell^2$ and FID metrics have some limitations in characterizing the effectiveness of the method.**\n\nWe use the FID metric simply because there are no principally different alternatives. In fact, all the metrics for generative models which we have seen in the related papers evaluate set-to-set similarity rather than the quality of individual samples. If you can suggest popular metrics based on individual images, we are happy to include them to our evaluation.\n\nRegarding the $\\ell^2$ metric, we used as a cost fuction during trining of our models and, as a consequence, employ it to evaluate the similarity between input and generated images. \n\n**Concluding remarks**. Please respond to our post to let us know if the clarifications above suitably address your concerns about our work. We are happy to address any remaining points during the discussion phase; if the responses above are sufficient, we kindly ask that you consider raising your score."}, {"review_id": "CQXs0BsV4b", "reviewer": "Reviewer_3fqr", "summary": "This paper presents a novel OT problem, extremal transport (ET), in the context of domain translation. The authors propose an incomplete transport (IT) problem as a surrogate optimization problem to obtain an approximate solution to the ET problem. The theoretical convergence between IT and ET costs (plans) is proven conditionally. The effectiveness of ET and IT is showcased through experiments on toy examples and public datasets, while also demonstrating the relationship between ET and IT.", "questions": "- The authors noted \"the task is ill-posed as there might exist multiple suitable T.\" It is confusing for me due to two reasons: (1) you just mention that there could be multiple maps between source and target; however, the optimization problem has not been formulated here, and it is not proper to say it is ill-posed problem since the word ill-posed seems to be suitable for optimization problems; (2) the optimization problem, such as the Kantorovich problem, could be not ill-posed in some cases given certain metrics, is it right? Please consider to improve the narrative to make it more rigorous and self-contained.\n- The authors noted \"challenge here is that the correspondence between vailable data samples a from the source and y from target domains is not given.\" What if the correspondence is given? Can we get a new optimization problem with intriguing properties?", "limitations": "The limitations have been well discussed.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The optimal transport formulations in this work, i.e., ET and IT, are something that I have not seen. These formulations, for me, are inspiring and interesting.\n\n- The paper provides a thorough discussion on the technical differences and relationship with other existing methods.\n\n- The overall presentation of the main paper is generally clear. Furthermore, the full paper, including the appendices, appears to be comprehensive and well-prepared. The theoretical results are presented in a comprehensive and self-contained manner.", "weaknesses": "- The scope of and motivation for the work are a little unclear from the abstract and introduction. In particular, the motivation to incorporate ET in the context of domain translation is not clear, which could make readers confused. It should be highlighted at least in the abstract and introduction sections. \n\n- Certain statements lack sufficient explanations or supporting intuitions, which should be explained and provided in the main text. To list a few:\n  - In the lines 85-91, a variant of OT problem is established. The authors mentioned \"we say that the target domain is the part of Y where the probability mass of Q lives\". However, the intuition behind this statement is not well-presented and should be elaborated upon.\n  - In the lines 76-78, the intuition to establish the ET framework in the context of domain translation should be demonstrated. It should also be highlighted in the abstract and introduction sections. Specifically, readers may hope to see why it is essential to construct ET for domain translation task, given thorough related works on weak OT, partial OT, etc... Although you have formulated the technical difference with them, I hope to see analysis on \"why ET outperforms them in your application\".\n  - In the lines 91-92, the authors relaxes the mass preservation condition for the target domain. Why not relax the condition for both the target and source domain, likewise UOT? A concise and simple comparison with current weak / partial OT should be clarified here, to **explain the advantages of ET in domain translation compared with peer methods, (rather than purely formulating the technical differences)**, which is critical for identifying and evaluating ET's role in domain translation.**\n\n\n### ************ Minors ***************\n\n- Figure 3-4 are kind of redundant and largely inherit from current literatures. As such, it is not appropriate to take too much blank space for them. A more proper way would be consendate them in one line or move them to the appendix.\n- In the line 104, the NN could lead to unexpected confusion since it usually represents neural networks.\n- In the lines 80-109, the authors establish an optimization problem to seek for the nearest neighbors of $x\\in\\mathcal{X}$ in Supp(Q). The narrative in this section is kind of redundant.\n- It is essential for readers to acknowledge the technical differences with other OT methods. As such, I suggest authors moving the section of \"Related works\" after the section of \"background on optimal transport\", and highlight your technical difference with each genre of OT methods concisely.\n\nMy current score is a reflection of the weaknesses above as they stand. Since these seem like rather correctable issues, I expect to increase my score pending a positive response from the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your comments. Here are the answers to your questions.\n\n**(1) The motivation to incorporate ET in the context of domain translation is not clear <...> in the abstract and introduction.**\n\nThe motivation to incorporate ET in the context of domain translation is implicitly stated in lines 25-31 of the introduction. Indeed, ET allows to perform domain translation while achieving best possible similarity between source and generated images. Such property is needed in various particular downstream image-to-image problems including, e.g., image inpainting or super-resolution (lines 222-225). *We will state the motivation more clearly in the abstract and introduction in the final version of our paper.*\n\n**(2) The intuition behind \"we say that the target domain is the part of $\\mathcal{Y}$ where the probability mass of $\\mathbb{Q}$ lives\" (lines 85-91) is not clear.**\n\nConsider a typical example $\\mathcal{Y}=[-1,1]^{D}$. Following the standard manifold hypothesis [1], real data distribution $\\mathbb{Q}$ (e.g., distribution of images of faces) is usually supported on a small-dimensional manifold $M=$ Supp$(\\mathbb{Q})\\subset [-1,1]^{D}$ occupying a tiny part of the ambient space $[-1,1]^{D}$. Thus, the intuition behind the mentioned statement is that the probability distribution $\\mathbb{Q}$ lives on this manifold $M$ which represents a target domain. *We will add clarifications to the final version.*\n\n**(3) Demonstrate the intuition to establish the ET framework in the context of domain translation. Why it is essential to construct ET for domain translation task, given thorough related works on weak OT, partial OT, etc... <...> \"why ET outperforms them\".**\n\nOur experiments with domain translation do not pretend to show that ET construction is essential to solve domain translation task, but only demonstrates that proposed numerical algorithm are applicable to the problem with real data. In particular, it can recover very good similarity of translated samples to input samples which may be of high importance in certain image-to-image translation tasks (lines 222-233) while existing (GAN-based) methods encounter their limitations (Appendix). To the best of our knowledge, there are also no works that apply weak OT or partial OT to solve the same problem of ET (nearest neighbours computation with the out-of-sample generalization).\n\n**(4) In the lines 91-92, the authors relaxes the mass preservation condition for the target domain. Why not relax the condition for both the target and source domain, likewise UOT?**\n\nIn a task of domain translation, we need to translate the sample from the source domain to the target one. Relaxing the condition for target domain helps us to achieve the 'best possible similarity' between source and generated images which is a primary goal of our IT approach. At the same time, relaxing source distribution is counter-intuitive for domain translation task where all the **test** samples will come from the source distribution $\\mathbb{P}$.\n\n**(5a) The NN abbreviation is confusing.**\n\nWe agree with the reviewer that NN abbreviation is commonly employed to denote neural networks. At the same time, it is also common abbreviation for nearest neighbors, e.g., like in $k$-NN. To avoid misunderstanding, we explain the abbreviation several times in the paper, see line 32 and 104-106. \n\n**(5b) In the lines 80-109, the authors establish an optimization problem to seek for the nearest neighbors of x$\\in$X in Supp(Q). The narrative in this section is kind of redundant.**\n\nWe kindly ask the reviewer to specify which parts of the section seem to be redundant. We will be happy to improve the section narrative.\n\n**(5c) Acknowledge the technical differences with each genre of OT methods. Move the \"Related works\" section after \"background on OT\".**\n\nWe highlight technical differences with conventional neural OT methods in Appendix F (lines 906-910), discrete partial OT methods in Appendix D (lines 650-657), discrete unbalanced OT in Appendix B (lines 554-560). Unfortunately, we could not move related work section to the beginning of the paper, since it uses some ET/IT notions and properties which are introduced in prior sections. *We will move the technical differences with other OT methods from Appendix to the related work section.*\n\n**(6) The statement \"the task is ill-posed as there might exist multiple suitable T\" is confusing. <...> the Kantorovich problem, could be not ill-posed in some cases given certain metrics, is it right?**\n\n(a) We agree with the reviewer's comment that maybe 'ill-posed' is not an appropriate designation for the problem before it is strictly mathematically formulated. *We will change the word 'ill-posed' to 'ambiguous' in line 15 in the final version of our paper.*\n\n(b) You are correct in your understanding that Kantorovich problem is not an ill-posed problem. \n\n**(7) What if the correspondence between available data samples from the source and y from target domains is given?**\n\nIf the correspondence is given, i.e., **paired** samples $(x_n,y_n)$ are available for training, the problem can be straightforwardly solved by common supervised learning techniques such as Pix2Pix [2]. This setup is out of the scope of our paper. We consider the **unpaired** setup where the is no supervision.\n\n**Concluding remarks**. Please respond to our post to let us know if the clarifications above suitably address your concerns about our work. We are happy to address any remaining points during the discussion phase; if the responses above are sufficient, we kindly ask that you consider raising your score.\n\n**References.**\n\n[1] Fefferman, C. et al. Testing the manifold hypothesis.\n\n[2] Isola, P. et al. Image-to-image translation with conditional adversarial networks."}]

Author rebuttal:
Dear reviewers, 

thank you for your thorough and detailed feedback! We are highly inspired by the fact that you agree on the novelty of the proposed Extremal and Incomplete Transport (ET/IT) formulations (Reviewers iXGC, URfJ, Cqh5, 3fqr), find our theoretical results to be valuable (Reviewer iXGC, 3fqr), acknowledge that our algorithm is widely applicable (Reviewer URfJ), and its effectiveness is proved by complete and sufficient experimental evaluation (Reviewers URfJ, Cqh5). We are glad that you positively highlight clear presentation and comprehensiveness (Reviewers iXGC, 3fqr, Cqh5) of our paper. We hope that our IT algorithm would be easy to use in practical applications.

We will incorporate the changes suggested by the reviewers in the final version of our paper. We list the changes below:

(a) Main text (**minors**) $-$ replacement of the Figures (3-5) by those where the support is non-convex (Reviewers Mz3K, 3fqr) plus minor requested clarifications here-and-there;

(b) New **Appendix** section$-$ additional experiments (Reviewer Mz3K): *Swiss2Ball* experiment where ET maps have *closed-form*, *Ball2Circle* experiment testing advanced version of our method with weak kernel cost;

(c) **Addition** to Appendix F $-$ small corollary showing the closeness of IT problem solution to the set of ET plans (Reviewers iXGC).

Please find Figures for experiments requested by reviewer Mz3K in the **attached PDF file**.

Please find the answers to your questions below.

Meta-review: This paper studies generalized versions of the optimal transport problem where the usual mass conservation marginal constraint is replaced by weaker / relaxed constraints. The reviewers in general appreciated the formulation, theoretical rigor, and strong empirical results. 

But the paper has important weaknesses too. For example, I tend to agree with reviewer Mz3K that the way the paper is presented puts too much emphasis on a formulation of the problem (the "Extremal Transport" problem, Eq 5.) that is not properly motivated and is not ultimately what is solved. In particular, it is not clear why one would be interested in a map that has absolutely no mass preservation constraints (only partial support overlap). E.g., any map that puts zero mass on the complement of the support of Q but is otherwise unconstrained is feasible for Eq. 5 -- this is an extremely large (and frankly, not too interesting) class of maps! In contrast, the "Incomplete Transport" problem (Eq. 11), which the authors settle for almost begrudgingly as an "easier alternative" to (5) seems much more natural and easier to motivate, since it optimizes over a much more interesting class of maps. Confusingly, they refer to the transition from (5) to (11) as a "relaxation" (or "softening"), even though it's the exact opposite -- as is clear from the example above, the constraint set of (5) is much larger than that of (11). This to me muddies the message of the paper and makes the ET formulation feel almost forced and superfluous.  

Another aspect where the paper falls short is in contextualizing these formulations in the context of Partial Optimal Transport, a very related and well-studied variant of OT, of which the formulation proposed here is a particular case. While there is a discussion on the related POT work in the Appendix, and sporadic mentions throughout the main text, this connection should be made earlier than Page 5 -- for the sake of the reader's understanding and contextualization of the contributions of this paper.

All things taken into account, I believe this is a solid paper that has not lived up to its full potential due to some important issues of presentation and narrative, but which is nevertheless (and in spite of its weaknesses) likely to be of interest to the ML+OT community in NeurIPS. For that reason, I am ultimately recommending acceptance, but I sincerely hope the authors take the combined feedback from reviews and metareviews to clean up the paper's presentation.
Decision: Accept (poster)