Kernel Neural Optimal Transport
Authors: Alexander Korotin
Daniil Selikhanovych
Evgeny Burnaev
Venue: ICLR 2023 poster (2023)
Keywords: optimal transport
neural networks
kernels

Abstract: We study the Neural Optimal Transport (NOT) algorithm which uses the general optimal transport formulation and learns stochastic transport plans. We show that NOT with the weak quadratic cost may learn fake plans which are not optimal. To resolve this issue, we introduce kernel weak quadratic costs. We show that they provide improved theoretical guarantees and practical performance. We test NOT with kernel costs on the unpaired image-to-image translation task.

Published as a conference paper at ICLR 2023
KERNEL NEURAL OPTIMAL TRANSPORT
Alexander Korotin
Daniil Selikhanovych
Skolkovo Institute of Science and Technology Artificial Intelligence Research Institute
Skolkovo Institute of Science and Technology
Moscow, Russia se 1 ikkhanoyycchaaaii iamaaamiii@@mmaamm 100mmalmlll... com
Moscow, Russia
a. kokootin@kolteech.c.
Evgeny Burnaev
Skolkovo Institute of Science and Technology Artificial Intelligence Research Institute
Moscow, Russia
.burnaev@skoltech..rr
ABSTRACT
We study the Neural Optimal Transport (NOT) algorithm which uses the general optimal transport formulation and learns stochastic transport plans. We show that NOT with the weak quadratic cost may learn fake plans which are not optimal. To resolve this issue, we introduce kernel weak quadratic costs. We show that they provide improved theoretical guarantees and practical performance. We test NOT with kernel costs on the unpaired image-to-image translation task.
RYR P
XX
T(x 21)
Tix,2)
T(x, 22)
7xx,
T(x,
7(x,2))
(a) Celeba (female) anime, 128 x 128.
(b) Outdoor church, 128 128.
Figure 1: Unpaired image-to-image translation (one-to-many) by Kernel Neural Optimal Transport.
INTRODUCTION
Neural methods have become widespread in Optimal Transport (OT) starting from the introduction of the large-scale OT (Genevay et al.) 2016) Seguy et al.) 2018) and the Wasserstein Generative Adversarial Networks (Arjovsky et al.) 2017) (WGANs). Most existing methods employ the OT cost
as the loss function to update the generator in GANs (Gulrajani et al. 2017; Sanjabi et al. 2018
Petzka et al. 2018). In contrast to these approaches, (Korotin et al. |023 Rout et al. 2022] Daniels al. 2222 Fan et al. 2022al Korotin et al. 2023) have recently proposed scalable neural methods to compute the OT plan (or map) and use it directly as the generative model.

---

Published as a conference paper at ICLR 2023
In this paper, focus the Neural Optimal Transport (NOT) algorithm (Korotin et al. 2023 It is
capable of learning optimal deterministic (one-to-one) and stochastic (one-to- same-to-many many) mäps and plans for quite general strong and weak (Gozlan et al. 2017 Gozlan & Juillet, 2020 Backhoff- Backhott-Verrguaa et al. 2019) transport costs. In practice, the authors of NOT test it on the unpaired image-to-image translation task (Korotin et al., [023 95) with the weak quadratic cost (Alibert et al. 2019 85.2).
Contributions. We conduct the theoretical and empirical analysis of the saddle point optimization problem of NOT algorithm for the weak quadratic cost. We show that may have a lot of fake solutions which do not provide an OT plan. We show that NOT indeed might recover them ($3.1).
We propose weak kernel quadratic costs and prove that they solve this issue ($3.2). Practically, we show how NOT with kernel costs performs on the unpaired image-to to-image translation task ($5).
Notations. We use V. to denote Polish spaces and P(x), P()), P(2) to denote the respective sets of probability distributions on them. For distribution I.. denote its mean and covariance matrix by mp and M>, respectively. We denote the set of probability distributions on X' x y with marginals IP and Q by [I,,, Q) For measurable map T X x 2 + y (or Te 2 - }), denote the associated push-forward operator by T: (or Tzt). We use H to denote a Hilbert space (feature space). Its inner product is (t:)),, and || 2/ is the corresponding norm. For function u y + H (feature map), we denote the respective positive definite symmetric (PDS) kernel by k(y. v/ def (u(y), u(y/)))))))))))) )m. PDS kernel y x y + R is called characteristic the kernel mean embedding P(Y) A μ + u(p) def (xv(v)u(ly) E H. is a one-to-one mapping. For a function Φ: D - RU(()) we denote its convex conjugate by p(v) del
suPxERD (1r, y) (z:).
BACKGROUND ON OPTIMAL TRANSPORT
Strong OT formulation. For distributions P(X), Q E P(Y) and a cost function e: Xxy + R.
Kantorovich's (Villani 2008) primal formulation of the optimal transport cost (Figure 2 is
Cost(IP
def
inf TEI((P.Q) xxx
/ c(a, ((d,y)d
where the minimum is taken over all transport plans i.e. distributions on X x y whose marginals are IP and Q. The optimal n" [1( Q) is called the optimal transport plan. A popular example of an OT cost for X' = y R is the Wasserstein-2 (W3), i.e., formulation ① for c(x, y) = || - y/1?.
C(x.N(V))))
c(xay11)
y1 Y2
mlyx),
X1
X1
P
X2
P X2
mlylxn)
Yn
X
c(Xniym)
X
C(xxx)
(a) Strong OT formulation 1
(b) Weak OT formulation
Figure 2: Strong (Kantorovich's 's) and weak (Gozlan et al. 2017) optimal transport formulations.
Weak OT formulation. Let C X' P()) R be weak cost (Gozlan et al. 2017). i.e., function which takes a point E X and a distribution of E y' as inputs. The weak OT cost between IP, Q is
Cost(IP
def
inf TET((.
/ C(z,
where x(-[x) denotes the conditional distribution (Figure 2b Weak OT ( subsumes strong OT formulation (1) for C(., (1) = Sy. c(x, y)du(y). An example of a weak OT cost for X' = y' = TR. D the y-weak () Wasserstein-22 (2 i.c., formulation (2) with the 7-weak quadratic cost
1 x ydd(w))) + (2, def / 1--=ー~il 1alx-v13d4pe vll2)(()) - Varr(n) = | 2
=/,
1 1- Var(u), (3)
where Var(u) denotes the variance of j::
def J Ily
Var(w)
((((l/))l(dpp))) y
1 - v v/(ddp(y)ddp()))
(4)
For 7 0, the transport cost is strong, i.e., Wa -W200-
2

---

Published as a conference paper at ICLR 2023
If the cost C( ju) is lower bounded, lower-semicontinuuus and convex in the second argument, then we say that is appropriate. For appropriate costs, the minimizer π of (2) always exists (Backhoff- (Backhoff-Veraguus et al. 2019: $1.3.1). Since Var(u) is concave and non-negative, cost (3) is
appropriate when E [0, For appropriate costs the (2) admits the following dual formulation:
shs J f (I)) + I, f(v)d((v).
Cost(P, Q)
(5)
where f are upper-bounded, continuous and not rapidly decreasing functions, see Backhoff-Veraguas
al. 2019 91.3.2), and f (1)) def inf (EPO)) (C(s, [4) -Jy f(y)du(y) is the weak C-transform.
Neural Optimal Transport (NOT). In (Korotin et al.
T(xi Z)
2023), the authors propose algorithm implicitly
T(X,,2)
X1
learn an OT plan πt with neural nets (Figure 3 They introduce (latent) atomless distribution S P()),
e.g. 2 = R2 and = N00,, Iz), and search for a OT map) which πt" (ylz) for some OT plan T². That is, given x E X, function T pushes the distribution S to the conditional distribution n²" (vl a) of an OT plan π In particular, 7 satisfies the distribution- preserving condition 7 B) Q. To get 7*, the authors use (5) to derive an equivalent dual form:
P
X2
T(xmi))
function T : X x Z + y (stochastic OT
satisfies T
X
T(xm. 2)
S
Noise
Figure 3: Implicit representation of transport plan via function T Xx
CF, ; Q sup inf / (C(E.I.H))
((II(()) d((x)) - -J----0A fly) (6)
f
where the inf taken over measurable functions T X' Z The functional under sup, infr denoted by [(f, T). For every optimal potential f arg sup, infr L(f,T), it holds that
T E ang C(f", C(f",
see (Korotin et al. 2023 Lemma 4). Consequently, one may extract optimal maps 7 from optimal saddle points (j T') of problem (6). In practice, saddle point problem (6) can be approached with
neural nets f.. To and the stochastic gradient descent-ascent (Korotin et al. 2023 Algorithm 1).
The limitation (Korotin et al. 2023] $6) NOT algorithm is that arg inf, set of f* in 7 may contain not only optimal transport maps but other functions well. As a result, the function T recovered from a saddle point (f*, T*) may not an optimal stochastic map. this paper, we show that for the 7-weak quadratic cost 3 this may be problematic: the arg inf. sets might contain fake solutions 1 (33.1) To resolve the issue, we propose kernel w-eeak quadratic costs ($3.2).
Convex order. For two probability distributions IP, Q on D, we write IP I Q if for all convex functions h R D R it holds /(x)d(((x)
h())d((a)). The relation "=" is partial order, ie., not all PP, Q are comparable. If = Q then mp = my and Σp = Eg (Saariini 1998] Lemma 3). If IP, Q are Gaussians, P holds if and only if mp mg and Σp < Eg (Scarsini 1998 Theorem 4). For IP, Q, we define the projection of P onto the convex set of distributions which are Q as
(P)) aarg infp
The infimumm is attained uniquely (Gozlan & Juillet 2020, Proposition 1.1). There exists a L-Lisschitz continuously diffirentiable and convex function @ RR + R satisfying (Gozlan & Juillei 2020 Theorem 1.2) for details.
V VotP. see
Weak OT with the quadratic cost (> > 0). For the 7-weak quadratic cost (3) on X y R Gozlan & Juillet] 2020] $5), (Alibert al. 2019 55.2) prove that there exists a continuously differentiable convex function o² R - R such that x* [TPP, Q) is op- timal if and only Jy y dor x)) = (x* holds true alamostt surely. In general, x is not unique. We say that ø" is optimal restricted potential. It may be not unique as a function RD - R, but V uniquely defined P-almost everywhere. It holds true
Vi)(x))
X1
P
X2
to Vx)((x))
X
Proj sq (V'#IP)
Figure 4: Every optimal restricted potential @* satisfies T = ( - Q
3

---

Published as a conference paper at ICLR 2023
that VØ" is マ -Lipschiiz; VP Proj=o( (P):; it is the OT map between I and Proj + HP) for the strong quadratic cost (Figure
4..
The function 6i maximizes the dual form alternative to (
[/x
||:|| d((x) dP(T)+ 2
I/ Ilvll
2 dQ(z) (1 o(x)dF(x)+ (wwdd())))
W (P, ?
max (ECOX())
(9)
where ( denotes the set of 1 -moooh convex functions : RD + R. Duality formula 9
appears in (Alibert et al. 2019 85.2). (Gozlan & Juillet [020] Theorem 1.2 & 55) but with different
parametrization. In Appendix F. for completeness of the exposition, we derive (9) from the results of
(Gozlan & Juillet 2020) by the change of variables.
3 SOLVING ISSUES OF NEURAL OPTIMAL TRANSPORT
In what follows, consider X= - C CRD, In $3.1 we theoretically derive that arg infy sets 7 for the 7-weak quadratic cost (3) may indeed contain functions which are not stochastic OT maps. In 83.2 we introduce kernel weak quadratic costs and prove that they do not suffer from this issue, i... all functions in sets arg i for all optimal f are stochastic OT maps. In $3.3 we discuss the practical aspects of learning with kernels. We give the proofs of all the statements Appendix G
3.1 FAKE SOLUTIONS FOR WEAK QUADRATIC COST
In this subsection, we consider X = y' = RR. We show that arg infy C(f" ( T) sets 77) of optimal potentials f in (5) for the 7-weak quadratic cost (3). in general. may contain functions T which are not stochastic OT maps. We call such T fake solutions. To show why one should be concerned about fake solutions, we emphasize their key defect below.
Let J E argsup, inf L(J,T) T) and Tt E arg y C(F", T) be a fake solution. Then it holds that T' 8) &Q.
Lemma 1 (Fake solutions are not ceneributioo-preservinn
Throughout the section, we assume that P, Q have finite second moments. We analyse the potentials
of the form (" 1 ||yl| o= (y)) where ø² RDD + R is an optimal restricted potential. To begin with, show that such potentials indeed optimal potentials for dual forms (5) and (
RR - R be an optimal restricted potential. Assume that 6' takes only finite values. Then (2) def maximizes dual formulations (5) and (6)
Lemma 2 (Optimal restricted potentials provide dual form maximizers). Let 0=
For convex 1/ R.P... - R. we denote the around point y E R in which is linear by
(v) = (v' E RD such that Vr (yy it holds (vy') = (y) + (z, v' y) (v). (10)
Proposition 1 (Convexity of sets of local linearity of a convex function). Set U convex. Our following theorem provides full characterization of the arg inf, L(f" .) sets in view.
Theorem 1 (Characterization of saddle points with optimal restricted f*). Let f (y) = lvll
(v),
2
where d² is an optimal restricted potential. Assume that Φ= takes only finite values. Then it holds true that arg ir L(F*, (T) is a convex set and
Tt earginf C(f" + J2 (=))))((=) (z) holds true P-almost everywhere;
(11)
( (V (x)) holds true PxS-almost everywhere,
where (1y)
def )-) - |l1l12 Note that va is convex since o² is 4-smooth (Kakade et al. 2009).
(v)
We define the optimal barycentric projection (2) def (x*(x) for (æ, 2) E Xx2;; Z; does not depend on E Z. The function depends on the choice of optimal o² we are interested only in its values in the support of P, where VØ* is unique 2p. From definition (10), we see that V (z) E Up (V and T satisfies both conditions on the right side of (TT). Thus, we have T E arg inf., L(f",T)
Lemma (The barycentric projection is not always a stochastic OT map). The following holds true
T is a stochastic OT map Proj k (1) Q (b) T is the unique stochastic OT map.
We use the word stochastic but T is actually deterministic since does not depend on z. From our Lemma 3 we derive that if ( (f + Q holds that (s*, T is a fake saddle point.
4

---

Published as a conference paper at ICLR 2023
2
-2
Input
T(x)
T(x
T(x)
2
Target y
Mapped Tix,
Mapped Tix, z)
Mapped T(x.2)
(a) Input and target
(b) Fitted map T. for 7 2"
(c) Fitted map f.
(d) Fitted map (2)
distributions IP and Q
for 7
for y
Figure 5: Stochastic maps 7 between and Q fitted by NOT algorithm with costs C2.r for various 7
Corollary (Existence of fake saddle points). Assume that ( + Q. Then problem (6)
has optimal saddle points (f*,"*) in which T is not stochastic OT map.
Beside T our Theorem 1 can be used to construct arbitrary many fake solutions which are not OT maps. Let T be any stochastic OT map and 7t arg inf, L( T) satisfy T * T and Var (T H(P x S)) Var(Q). For example, Tl may be another stochastic OT map or the optimal barycentric projection T For any a E (0, 1) consider T aT + a)) E arg ing, L(f",
Proposition (Interpolant is not stochastic OT map). Assume that ( # Q. Then
TO:(P x S) A Q Consequently, T not a stochastic OT map belween IP and Q
It follows that necessary condition for non-existence of fake saddle points is Pr
Q
This requirement is very restrictive and naturally prohibits using large values of y. Also, due to Lemma 3 the OT plan between IP, Q must be deterministic. From the practical point of view, this requirement means that there will be no diversity in samples T (z) for fixed and S.
On the other hand, if (r HP) # Q i.e., P is not 7-times more disperse than Q the optimization may indeed converge to fake solutions. To show this, we consider the following example.
Toy 2D example. We consider F = (o, (2) Q =N(00, I2) (Figure 5ab and run NOT Korotin
ct al. 2023 Algorihm 1) for E ( -. 1]- we-k quadratic costs C2 We show the learned stochastic
maps (²) and their barycentric projections T(x) def Jz T (2))(((2 in Figures 5b
5c
5d
Good case. When > I 2, we have 1P (0, 121) with 1 2 1. Since the distributions
24
HP and Q are Gaussians and Σg 3 Eigr, we conclude that ( ( = Q Gozlan & Juillet 2020 Corollary 2.1). Next,
Lemma] 3 and derive that the OT plan is unique, determmistrc and equals the barycentric projection. The latter is the OT map between IP and Q for the quadratic
cost. given by V (x) = 2x (Álvarez- ('lvarez-Esteban et al. 2016 Theorem 2.3). Figure 5b (when
= }), we have (x) = T(x)= z 2r = VΦ²(x) and (Pxx R Q. Thus, NOT correctly learns the (unique and deterministic) OT plan.
Since 1 and Q are Gaussians and Eg 2 Eggr- we conclude that LP < Q (recall $2). Thus, Proizo + Q by definition of the projection (8) The optimal barycentric projection is the OT map between Gaussians P and 2 -TP for the quadratic cost. It is given by (x)(x) f/x (Alvarez-Fstehan et al. that the learned T(x) R J,, i.e T captures the
Bad case. When 7 1. we have 4PP NO 12)) with 2y
2016 Theorem 2.3). In Figures 5e and 5d
5

---

Published as a conference paper at ICLR 2023
2-
1-
0-
-1
X P
-2
Tix)
T(x)
T(x)
T(x)
2-
1-
Mapped 2)x
Mapped Tix,z)
Mapped Tix, zl
Mapped T(x
(a) Iteration 10k.
(b) Iteration 10k+100.
(c) Iteration 10k+200.
(d) Iteration 10k+300.
Figure 6: The evolution of the learned transport map f during training on toy 2D example (? = 1). conditional expectation of π (ul æ) shared by all OT plans x² ($2) However, TFPPX + Q and NOT fails learn an OT plan.
Importantly, we found that when y 1 (Figures 5c 5db. the transport map f' extremely fluctuates during the optimization rather than converges to solution. In Figure we visualize the evolution of T during training (for 7 = 1). In all the cases, the barycentric projection T(x) R I = V (x) is almost correct. However, the "remaining" part of T is literally random. To explain the behavior, we integrate Vo" (x) = r and get that o² (x) = ]||=|| is an optimal restricted potential. We derive (v) = の- ||ull = 21lvll2
lvll = 0 = (v) = Uo( = R² for every From our Theorem I ii follows that 7 E arg inf, C(S" ,T) +
R
= V (2) x holds P-almost everywhere. Thus, function 7 recovered from (6) may be literally any function which captures the first conditional moment of a plan π (y/rr. This agrees with our practical observations. In Appendix
C
we give an additional toy example illustrating the issue with fake solutions.
Our results show that the w-ek quadratic cost C2,y may be not a good choice for NOT algorithm due to fake solutions. However, prior works on OT (Korotin et al. 22233 Rout et al. [022] Fan al.) [002aa] Gazdieva et al.) [022; Korotin et al. (022) use strong/weal quadratic costs and show promising practical performance. Should we really care about solutions being fake?
Yes. First, fake solutions T* arg infy f( do not satisfy T" 4 Q. i.e. they are not
distribution preserving (Lemma [. Second, our analysis suggests that fake solutions might be one of the causes for the training instabilities reported in related works (Korotin et al., 2023 Appendix D), Korotin et al. 2021b 54): the map T may fluctuate between fake solutions rather than converge.
3.2 KERNEL WEAK QUADRATIC COST REMOVES FAKE SADDLE POINTS
In this section, we introduce kernel weak quadratic costs which generalize weak quadratic cost (3) We prove that for characteristic kernels the costs completely resolve the ambiguity of arg inf, sets. Henceforth, assume that ==yco C RD 2 are compact sets. Let H be a Hilbert space (feature space). Let u. + H be a function (feature map). We define the 7-weak quadratic cost between features:
(x, def 1 2 / [lu(z) - u(t)
2. 27 2 yxy
I |u(y) ((d)))lddd (12)
We denote the PDS kernel k : y x y - R with the feature map u by k(y. v²) def (u(y), u(y ((
Cost (12 can be computed without knowing the map u, i.e., it enough to know the PDS kernel By using [lu(y) - u(v')()))))))) 11 = k(y.v) - 2k(y. v²) + k(y', 2/)), we obtain the equivalent form of (12
Ck, (z) def k(0,, k(z,z)) x)+
1 1-7 / k(y. v)dp(v) - (xx w)dp())+ + / kly, o du(())) (13)
2

---

Published as a conference paper at ICLR 2023
X-p
Tx,z,))
T(x, T(x
T(x,2)
T(x, Zz)
T(x, x2)
Handbag shoes, 128 128.
(b) Shoes handbags, 128 128.
Figure 7: Unpaired one-to-many translation with kernel Neural Optimal Transport (NOT).
We call 12 and (13) the 7-weak kernel cost. The 7-weak quadratic cost (3) its particular case for H R and w(x)= æ. The respective kernel k( y) (u(z), u(y)) = (ar, y) is bilinear.
Lemma 4 (Weak kernel costs are appropriate). Let & be a continuous PDS kernel and y E [0, 1].
Then the cost (2, pi) is convex, lower semi-continuous and lower bounded in μ.
Corollary 2 (Existence and duality for kernel costs). Let be continuous PDS kernel and ry E [0, 1]. Then an OT plan πt" for cost (I, μ)) exists and duality formulas (5) and (6) hold tre.
We focus characteristic kernels k and show that they resolve the ambiguity in arginfy sets.
Lemma 5 (Uniqueness of the optimal plan for characteristic kernel costs). Let k be characteristic PDS kernel and 7 E (0, 1]. Then the OT plan n² for cost Ck,r p)) is unique.
Theorem (Optimality stochastic functions in all optimal saddle points). Let continuous characteristic PDS kernel and (0, 1]. Consider weak OT problem (2) with cost Ok and its dual problem 5
For any optimal potential fr E arg s inf L(f.T) it holds that
T E arginf C(f" .T) - = = πt" (y|x)) holds true P-almost surely for all E X,
(14)
i.e., every optimal saddle point (T') provides stochastic OT map T*
Bilinear kernel k(x, v) (z. y) is characteristic and is not covered by our Theorem 2 its respective 7-weak quadratic cost C2,, suffers from fake solutions ($3.1). In the next subsection, we give examples of practically interesting kernels k(z, y) which are idcologically similar to the bilinear but are characteristic. Consequently, their respective costs C₁ do not have ambiguity in arg inf, sets.
3.3 PRACTICAL ASPECTS OF LEARNING WITH KERNEL COSTS
Optimization. To learn the stochastic OT map T for kernel cost 13 use NOT's training procedure (Korotin et al. 2023 Algorithm 1). It requires stochastic estimation Ck,7 Tg (S) to compute the corresponding term in (6. Similar the 7-weak quadratic cost (Korotin al. 2023 Equation 23), it possible to derive the following unbiased Monte-Carlo estimator Ck,y for X and batch Z ~ S (lZ) 2 2):
(2,
=z
1 k(x +
1-7
Σ (T))
2|
ZEZ
Σ (x,,TT(=)) + ZEZ
7
Σ (TT)(2))
(x, TatS).
(15)
7
2/2(2
The time complexity of estimator 15 is 0( since it requires considering pairs 2, in batch to estimate the variance term. Specifically for the bilinear kernel k(y, v') (y. 1/). the variance be

---

Published as a conference paper at ICLR 2023
X-P
Txx
T(x,
T(x,22)
T(x
T(x,
T(x.zs)
Texture shoes, 128 128.
(b) Texture handbags, 128 128.
Figure 8: Unpaired one-to-many translation with kernel Neural Optimal Transport (NOT).
estimated in 0(1ZI) operations (Krottin et al. 2023 Equation 23), but NOT algorithm may suffer from fake solutions (33.I).
Kernels. Consider the family of distance-induced kernels k(r,, v) -1111=11 +/ll//
vll..
For these kernels, we have ||u(x) - u(2')11 || x i... 12 (13) can be expressed as
(I, p4) = (x, / | v1 vI1
-
1lv v du( (16)
yxy
For 2 the kernel is bilinear, i.e., k(2z (z, y): is PDS but not characteristic and (16) simply hecomes the 7-eeak quadratic cost 3). In the experiments ($5) we focus on the case a = T; yields
PDS and characteristic kernel (Sejdinovic al. 2013 Definition 13 & Proposition 14).
RELATED WORK
In deep learning, OT costs are primarily used as losses to train generative models. Such approaches are called Wasserstein GANs (Arjovsky & Bottou| 2017); they are not related to our paper since they only compute OT costs but not OT plans. Below discuss methods compute OT plans.
Existing OT solvers. NOT Korotin et al. 2023) the only parametric algorithm which capable of computing OT plans for weak costs (2) Although NOT is generic, the authors tested it only with
the 7-weak quadratic cost (3). The core NOT saddle point formulation (6) which subsumes
analogs (Korotin et al.] 202 Eq. 9), (Rout al. 2022 Eq. 14). (Fan et al.
2022al Eq. 11),
HHeny-LLaborded 2019 Eq. Ī1). (Gazdieva et 2022] Eq. 10). (Korotin et al.
2022 Eq. 7) for
strong costs (1p. For the strong quadratic cost, (Makkuva al. (020), (Taghvaei Jalaii 2019
Eq. 2.2), (Korotin et al. 2021a la Eq. 10) consider analogous to (9) formulations restricted to convex potentials; they use Input Convex Neural Networks (ICNNs (Amos al.) (017 approximate the potentials. ICNNs are popular in OT (Korotin et al. | Mokrov et 2021 Huang et al.
2020 Alvarez-Melis et al.) 2022, [unne et al.) al.]] (022) but recent studies (Korotin et al., 2021b 2022
Fan et al. 2022b) show that OT algorithms based on them underperform compared to unrestricted formulations such as NOT.
In (Genevay et al. 2016; Seguy et al.) 2018 Daniels et al. 2021). the authors propose neural
Genevay 2019). The first two methods suffer from bias in high dimensions (Korotin et al., 202 34.2). Algorithm (Daniels et al. (02T) alleviates the bias but is not end-to-end and is computationally expensive due to using the Langevin dynamics.
algorithms for /diveergence regularized costs
There also exist BAN-based (Goodfellow al.] 2014) methods (Lu et al. 2020 Xie et al. 2019 González-Same et al. 2022) to learn OT plans (or maps) for strong costs. However, they are harder to up in practice due to the large amount of tunable hyperparameters.
8

---

Published as a conference paper at ICLR 2023
Kernels in OT. In Zhang al. 2019 Oh et al., 2020). the authors propose strong kernel W2 distance and an algorithm to approximate the transport map under the Gaussianity assumption on P. Q. In (Li et al., 202I), the authors generalize Sinkhorn divergences (Genevay et al.) (2019) to Hilbert spaces. These papers consider discrete OT formulations and data-to-data matching tasks; they do not neural networks to approximate the OT map.
EVALUATION
In Appendix A we learn OT between toy ID distributions and perform comparisons with discrete OT. In Appendix B we conduct tests on loy 2D distributions. In this section, we test our algorithm on an unpaired image-lo-image translation task. We perform comparison with principal translation methods in Appendix K The code is written in PyTorch framework and is available at
https://g http:/gtttuhbboo//oo ama
ama weekorek Kerne NNura Opt mm Transport.
Image datasets. We test the following datasets as P, Q: aligned anime face:" celebrity faces (Luu
et al. 2015), shoes (Yu & Grauman, 2014), Amazon handbags, churches from LSSNN dataset Yu et al. 2015), outdoor images from the MIT places database (Zhou et al., (014), describable textures (Cimpoi et al. 2014). The size of datasets varies from 5K to 500K images.
Train-test split. We pick 90% of each dataset for unpaired training. The rest 10% are considered as the test set. All the results presented here are exclusively for test images, i.e., unseen data.
Transport costs. We focus on the 7-weak cost for the kernel k(æ; y) |||||| 1 |blll For completeness, we test other popular PDS kernels in Appendix
2 vll-
Other training details (optimizers, architectures, pre-processing, etc.) are given in Appendix 1
We learn stochastic OT maps between various pairs of datasets. We rescale images to 128 x 128 and use in the experiments with the kernel cost. Additionally, in Appendix D we analyse how varying parameter y affects the diversity of generated samples. We provide the qualitative results in translation map T (z) tries to minimally change the image content in the pixel space. At the same time, the second term (kernel variance) in (16) enforces the map to produce diverse outputs for different 2 ~ S.
Figures and 8 extra results are in Appendix D Thanks to the first term in (16).
We provide quantitative comparison with NOT with the 7-weak quadratic cost C2.y. We compute FID score (Heusel et al. 2017) be- tween the mapped input test subset and the output test subset (Table I For C2.7, we use the pre-trained models provided by the
Ck.y (weak) Ours
Datasets (128 128)
C2.0 (strong)
C2. (weak)
Handbags - shoes
35.7
33.9 + 0.2
26.7 = 0.06
Shoes handbags
39.8
29.51 = 0.19
authors of NOT (Korotin et al. 2023 {
Outdoor church
25.5
25.97 + 0.14
15.16 0.03
We observe that FID of NOT with kernel cost Ck,y is better than that of NOT with cost C2 We show qualitative examples in Appendix In Appendix H. we perform a detailed com- parison of NOT's training stability with the weak quadratic and kernel costs.
Celeba (f) + anime
38.73
28.21 + 0.12
21.96 = 0.07
Table 1: Test FID of NOT with various costs.
DISCUSSION
Potential impact. Neural OT methods and their usage in generative models constantly advance. We expect our proposed weak kernel quadratic costs to improve applications of OT to unpaired learning. In particular, we hope that our theoretical analysis provides better understanding of the performance.
Limitations (theory). In our Theorem 2 we implicitly assume the existence maximizer f* of dual form (5) for kernel costs Ck,y- Deriving precise conditions for existence such maximizers is a challenging question. We hope that this issue will be addressed in the future theoretical OT research.
Limitations (practice). Applying kernel costs to domains of different nature (RGB images - depth maps, infrared images - RGB images) is not straightforward as it might require selecting meaningful shared features u (or kernel k). Studying this question is a promising avenue for the future research.
kaaglle.ccom/eettaaaaaaaaaaaaaao https::/githhb..... amaa wtw.amaawekkkrktteeeeeee Opt ma1 Transport 1

---

Published as a conference paper at ICLR 2023
Reproducibility. We provide the source code for all experiments and release the checkpoints for all The details are given in README .MD the official repository.
models of S
ACKNONLEDGEMENTS. The work was supported by the Analytical center under the RF Govermment (subsidy agreement 0000000770331115000002 Grant No. 70-2021-00145 02.11.2021).
REFERENCES
J-J Alibert, Guy Bouchitté, and Thierry Champion. A new class costs for optimal transport planning, European Journal of Applied Mathematics, (066):122-1163. 2019.
Amjad Almahairi, Sai Rajeshwar, Alessandro Sordoni, Philip Bachman, and Aaron Courville. Aug- mented cyclegan: Learning many-to-mamy mappings from unpaired data. In International Confer- ence on Machine Learning, pp. 195-204. PMLR, 2018
Pedro C Álvarez-Esteban, Del Barrio, JA Cuesta-Albertos and C Matrán. A fixed-point approach to barycenters in Wasserstein space. Journal of Mathematical Analysis and Applications, 441(2):
744-762, 2016.
David Alvarez-Melis, Yair Schiff, and Youssef Mrouch. Optimizing functionals on the space of probabilities with input convex neural networks. Transactions Machine Learning Research, 2022. ISSN 2835-8856.
Brandon Amos, Lei Xu, and Zico Kolter. Input convex neural networks. In Proceedings of the 34th International Conference Machine Learning-Volle Volume 70, pp. 146-155. JMLR. org, 2017.
Martin Arjovsky and Leon Bottou. Towards principled methods for training generative adversarial networks. In International Conference on Learning Representations, 2017. URL https:// openreview net/ for _____
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Julio Backhoff- BackhooftVeraguas, Mathias Beiglböck, and Gudmun Pammer. Existence, duality, and cyclical monotonicity for weak transport costs. Calculus of Variations and Partial Differential Equations, 58(6):1-2,, 2019.
Charlotte Bunne, Laetitia Papaxanthos, Andreas Krause, and Marco Cuturi. Proximal optimal transport modeling of population dynamics. In International Conference on Artificial Intelligence and Statistics, pp. 3511-6528 PMLR, 2022.
M. Cimpoi, S. Maji, I. 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.
Grady Daniels, Tyler Maunu, and Paul Hand. Score-based generative neural networks for large-scale optimal transport. Advances in Neural Information Processing Systems, 34, 2021.
Jiaojiao Fan, Shu Liu, Shaojun Ma, Yongxin Chen, and Hao-Min Zhou. Scalable computation of monge maps with general costs. ICLR Workshop on Deep Generative Models for Highly Structured Data, 2022a.
Jiaojiao Fan, Qinsheng Zhang, Amirhossein Taghvaei, and Yongxin Chen. Variational wasserstein gradient flow. In International Conference on Machine Learning, pp. 6185-6215. PMLR, 2022b.
Milena Gazdieva, Litu Rout, Alexander Korotin, Andrey Kravchenko, Alexander Filippov, and Evgeny Burnaev. An optimal transport perspective unpaired image super-resolution. arXiv preprint arXiv:2202.0/ 116, 2022.
Aude Genevay. Entropg-reuulaizzed optimal transport for machine learning. PhD thesis, Paris Sciences et Lettres (ComUE), 2019.
Aude Genevay, Marco Cuturi, Gabriel Peyré, and Francis Bach. Stochastic optimization for large- scale optimal transport. In Advances in neural information processing systems, pp. 3440-3443 2016.
10

---

Published as a conference paper at ICLR 2023
Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of sinkhorn divergences. In The 22nd interaational conference on artificial intelligence and statistics, pp. 1574-1583. PMLR, 2019.
Alberto González-Sanz Lucas De Lara, Louis Béthune, and Jean-Michel Loubes. Gan estimation of lipschitz optimal transport maps. arXiv preprint arXiv:2202.07990 2022.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, pp. 2672-2680, 2014.
Nathael Gozlan and Nicolas Juillet. On a mixture of brenier and strassen theorems. Proceedings of the London Mathematical Society, 120(3):434 463, 2020.
Nathael Gozlan, Cyril Roberto, Paul-Marie Samson, and Prasad Tetali. Kantorovich duality for general transport costs and applications. Journal of Functional Analysis, 2017.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of Wasserstein GANs. In Advances in Neural Information Processing Systems, pp. 5767-57777 2017.
Pierre Labor-Labo (martingale) optimal transport and anomaly detection with neural networks: A primal-dual algorithm. Available at SSRN 3370910, 2019.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in neural information processing systems, pp. 6626-6637, 2017.
Chin-War Huang, Ricky TQ Chen, Christos Tsirigotis, and Aaron Courville. Convex potential flows: Universal probability distributions with optimal transport and convex optimization. In International Conference on Learning Representations, 2020.
Xun Huang, Ming- Yu Liu, Serge Belongie, and Jan Kautz. Multimodal unsupervised image-to-image translation. In Proceedings of the European conference computer vision (ECCV), pp. 172-189, 2018.
Sham Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. On the duality of strong convexity and Learning applications and matrix regularization. Unpublished Manuscript, http://ttic. uchicago.
strong smoothness:
pdf. 2(1), 2009.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 6906666,, 2014.
Alexander Korotin, Vage Egiazarian, Arip Asadulaev, Alexander Safin, and Evgeny Burnaev. Wasserstein-2 generative networks. In International Conference on Learning Representations, 2021a. URL_https://opperrvviee http::/eee/fooooooeeeee/o www.ee/ooooiiiddoooo.tce _Xxa
Alexander Korotin, Lingxiao Li, Aude Genevay, Justin M Solomon, Alexander Filippov, and Evgeny Burnaev. Do neural optimal transport solvers work? a continuous wasserstein-2 benchmark. Advances in Neural Information Processing Systems, 34, 2021b.
Alexander Korotin, Lingxiao Li, Justin Solomon, and Evgeny Burnaev. Continuous wasserstein-2 barycenter estimation without minimax optimization. In International Conference on Learning Representations, 2021c. URL https:://ppnrreiee net. wtt:
Alexander Korotin, Vage Egiazarian, Lingxiao Li, and Evgeny Burnaev, Wasserstein iterative networks for barycenter estimation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (cds.), Advances in Neural Information Processing Systems, 2022. URL https //openreview. ntt.:/wwweeeeeeeeeeeeeeeeeee waweee//ooummmmm Bie.da-iinnnnnnannamme
Alexander Korotin, Daniil Selikhanovych, and Evgeny Burnaev. Neural optimal transport. In International Conference on Learning Representations, 2023, URL /ttttss://ppeereiiiieeee (tt.::/mmmmmmccccRRn1mcm

---

Published as a conference paper at ICLR 2023
Qian Li, Zhichao Wang, Gang Li, Jun Pang, and Guandong Xu. Hilbert sinkhorn divergence for optimal transport. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3835-3844, 2021.
Huidong Liu, Xianfeng Gu, and Dimitris Samaras, Wasserstein GAN with quadratic transport cost. In Proceedings of the IEEE International Conference Computer Vision, pp. 4832-4841, 2019,
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Guansong Lu, Zhiming Zhou, Jian Shen, Cheng Chen, Weinan Zhang, and Yong Yu. Large-scale optimal transport via adversarial training with cycle-consistency. arXiv preprint arXiv:2003.06635, 2020.
Ashok Makkuva, Amirhossein Taghvaci, Sewoong Oh, and Jason Lee. Optimal transport mapping via input convex neural networks. In International Conference on Machine Learning, pp. 6672-6681. PMLR, 2020.
Petr Mokrov, Alexander Korotin, Lingxiao Li, Aude Genevay, Justin M Solomon, and Evgeny Burnaev. Large-scale wasserstein gradient flows. Advances in Neural Information Processing Systems, 34, 2021.
Jung Hun Oh, Maryam Pouryahya, Aditi Iyer, Aditya P Apte, Joseph O Deasy, and Allen Tannenbaum. A novel kernel wasserstein distance on gaussian measures: an application of identifying dental artifacts in head and neck computed tomography. Computers in biology and medicine, 120:103731, 2020.
Henning Petzka, Asja Fischer, and Denis Lukovnikov. On the regularization of wasserstein GANs. In International Conference on Learning Representations, 2018. URL /oopsp/etee///eeeeeeeele net/ Bett//ooumniddshhyeBe
Gabriel Peyré, Marco Cuturi, al. Computational optimal transport. Foundations and Trends in Machine Learning, 1 11(5-6)3555-007 2019.
Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer- assisted intervention, pp. 234-241. Springer, 2015.
Litu Rout, Alexander Korotin, and Evgeny Burnaev. Generative modeling with optimal transport maps. maps. In International Conference on Learning Representations, 2022. URL httt:s:://ppprree/////
net www.fooruiiioooo wow.oommnd-dd222333666666-
Maziar Sanjabi, Jimmy Ba, Mcisam Razaviyayn, and Jason Lec. On the convergence and robustness of training gans with regularized optimal transport. Advances in Neural Information Processing Systems, 31, 2018.
Filippo Santambrogio. Optimal transport for applied mathematicians. Birkätsee, NY, 55(58-63):94. 2015.
Marco Scarsini. Multivariate convex orderings, dependence, and stochastic equality. Journal of applied probability, 35(1):93-103, 1998.
Vivien Seguy, Bharath Bhushan Damodaran, Remi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large scale optimal transport and mapping estimation. In International Confer- ence on Learning Representations, 2018. URL https: //te:s:///peeeevieww net htt./oorrmmiii
B1zlplbRW
Dino Sejdinovic, Bharath Sriperumbudur. Arthur Gretton, and Kenji Fukumizu. Equivalence of distance-basee and rahs-based statistics in hypothesis testing. The Annals of Statistics, pp. 2263- 2013.
Amirhossein Taghvaei and Amin Jalali. 2- Wasserstein approximation via restricted convex potentials with application improved training for GANs. arXiv preprint arXiv: 1902.07900 2019.
12

---

Published as a conference paper at ICLR 2023
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Yujia Xie, Minshuo Chen, Haoming Jiang, Tuo Zhao, and Hongyuan Zha. On scalable and efficient computation of large scale optimal transport. volume 97 of Proceedings of Machine Learning Research, pp. 6882-6892, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http: //proceedings mlr press https////v/xieeea..hamm html
Aron Yu and Kristen Grauman. Fine- fineigg visual comparisons with local learning. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 192-199, 2014.
Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao. Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop. arXiv preprint ar xrvi: 000..00000000 033600366, 2015.
Zhen Zhang, Mianzhi Wang, and Arye Nehorai. Optimal transport reproducing kernel hilbert spaces: Theory and applications. IEEE transactions on pattern analysis and machine intelligence, 1277):7411 2019.
Bolei Zhou, Agata Lapedriza, Jianxiong Xiao, Antonio Torralba, and Aude Oliva. Learning deep features for scene recognition using places database. 2014.
Jun Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference computer vision, pp. 2223-2232, 2017.
13

---

Published as a conference paper at ICLR 2023
A TOY EXPERIMENTS IN ID AND COMPARISON WITH DISCRETE OT
In this section, we learn transport plans between various pairs of toy 1D distributions and compare them with the discrete optimal transport (DOT) considered as the ground truth. We use the distance- induced kernel and consider 7 E 10). optimizers, etc.) match those of (Korotin et al. 2023 Appendix C). We consider Gaussian N(00 1) - Mixture of 2 Gaussians and Mixture of 3 Gaussians - Mixture of 2 Gaussians.
the rest training details (fully-connected architectures,
In Figure 9 visualize the pairs P, Q (1st and 2nd columns), the plan ât learned by Kernel NOT (3rd column) and the plan π learned by DOT (4th column). To compute DOT, we sample 10 random points x y y Q and compute discrete plan by ot opt imm cg solver from Python OT (POT) library https: : /ttps://pyythaae http//yttooo....t g gigggithhtg hhb. 1o/] Our learned plan म and DOT's plan " nearly match. Note also that, one may expect, with the increase of yy from variance of the plan increases and for very high 10 it becomes similar to the trivial plan IP x Q
10, the conditional
This is analogous to the entropic optimal transport, see, e.g., (Peyré et al. 2019 Figure 4.2).
Input P (1D)
Target C (1D)
Learned (2D), ours
DOT plan n (2D)
0.7
0.6
y-a
b.. f.2)) i
(x,)) 1
0.4
0.3
-1
011
-2
-1
2
0.0
0.2
0.4
0.6
Dansity
(a) Gaussian (00, - Mixture of 2 Gaussians,
Input e (1D)
Target & (1D)
Learned (2D), ours
DOT plan nī (2D)
0.6
x-p
y-2
fdd)
(xy)
0.4
0.3
-1
0.1
-2
0.6
(h) Gaussian (o0, 1) Mixture of Gaussians, 7 10.
Input P (1D)
Target c (1D)
Learned (2D), ours
DOT plan n (2D)
0.6
X
y-o
tx, f.zz)
(X.)) R²
0.5
1
0.4
0-
0.3
-1
0.1
-2
Mixture of Gaussians + Mixture of Gaussians, 7
Input P (1D)
Target c (1D)
Learned ñ (2D), ours
DOT plan n' (2D)
X-P
y-o
xx f.22)
(x-))
0.6
0.5
0.9
-1
0.1
0.0
Dersity
(d) Mixture Gaussians Mixture of 2 Gaussians, 7 = 10.
Figure Stochastic plans (3rd and 4th columns) between toy ID distributions (Ist and 2nd columns) leamned by our Kernel NOT (3rd column) and discrete OT with the weak kernel cost (4th column).
14

---

Published as a conference paper at ICLR 2023
B TOY EXPERIMENTS IN 2D
In this section, we learn transport maps between various common pairs of toy 2D distributions.
We use the distance-induced kernel and 7 1. All the training details (fully-connected architectures, optimizers, etc.) exactly match those of (Korotin et al. 2023, Appendix B). We consider Gaussian (0, [2) - Gaussian N I2) (the same experiment in Figures and 6p. Gaussian
(O, [ I2) + Mixture of Gaussians and Gaussian (0, [ 1 (2) - Swiss roll P, Q pairs. In
Figure 10 provide the learned stochastic (one-to-many) maps. Since the ground truth OT maps for kernel costs are not known, we provide only qualitative results.
X
-2
Input
Targety y
Mapped Tix,
T(x, 2)
Gaussian (0
Gaussian NO0, 12).
1-
-1
-2
Input x P
Target - 0
Mapped f(x.>)
(b) Gaussian (O,, (2)
Mixture of Gaussians.
0-
largety
Mapped 7lx
T(x.2)
(c) Gaussian (00 12) Swiss roll.
2-
1-
-1
-2
Input x PP
Targety
Mapped Tux 2)
Por.
(d) Mixture of 4 Gaussians + Uniform.
Figure 10: Stochastic (one-to-many) maps learned between toy 2D distributions by Kernel NOT.
15

---

Published as a conference paper at ICLR 2023
C ADDITIONAL TOY 2D EXAMPLE
In this section, provide additional toy 2D example demonstrating the issue with fake solutions for the weak quadratic cost. We consider a mixture of 4 Gaussians as and the uniform distribution on square Q- We train NOT with the y-weak quadratic cost for 7 0, 2 and report the results in Figure 11 For 0 (Figure 11b). we that NOT with the weak quadratic cost learns the target distribution. However, when converge and yields fake solutions. In addition, in Figure 12 we show that for y 1 the method notably fluctuates between the fake solutions. This is analogous to the toy example with Gaussians in For completeness, we run NOT with our proposed kernel cost (16) on this pair (IP, and and show that it learns the distribution Q, see Figure 10d
(Figure I1c) and
(Figure 1id), the method does not
$3.1 see Figure 6
2-
1-
-1
x
-2
Input
T(x)
70c
T(x)
2
-1-
Targel y -Q
Mapped Tix, 4)
Mapped Tix. 4
Mapped T(x.2
(a) Input and target
Fitted map 12 (z) for y = O.
(c) Fitted map (z)
Fitted map 1, (z) for y 1.
distributions IP and Q
for
Figure 11: Stochastic maps T between IP and Q fitted by NOT with costs C2, for various
1
W
0
-1-
% X ~
X
X
2
Tix)
T(x)
T(x)
T(x)
2-
1
-2
Mapped Tix.2)
Mapped Tix
Mapped Tix,
Mapped Tix.
(a) Iteration 10k.
(b) Iteration 10k+100.
(c) Iteration 10k+200.
(d) Iteration 10k+300.
Figure 12: The evolution of the learned transport map / during training toy 2D example (y 1).
In this case, the cost is the strong quadratic
16

---

Published as a conference paper at ICLR 2023
D
TRADE-OFF
In this section, we study how parameter affects the resulting learned transport map. In (Korotin) et al. 2023] Appendix A), the authors empirically show that for the 7-weak quadratic cost C2 the variety of samples T2 (z) produced for fixed x and ~ S increases with the increase of 7, but their similarity decreases. We formalize this statement and generalize it for kernel costs Ck.y
For a plan n, we define its (feature) conditional variance and (the square of) input-output distance by
(T) del J Var (utr()l=))dd(a)) dT())) and (ist del
/ [l(()) u(y)l v), (17)
xxxy
respectively. Recall that Var (uET(y) = Syxx [1a(y) -1) (Tdd We note that the 7-weak kernel cost of a plan [P, Q) is given by
Costg, (T) Dist (T) CVar,
(18)
Our following proposition explains the behaviour of the above mentioned values for OT plans.
x-P
Tix,z
Tix, T(x,z2)
Tix,
T(x, 2s)
Tix, Za) Za)
Tix, Ti,, 21)
T(x, Za)
(a)
7 (c)
(d)
(e)
Figure 13: Texture + shoes (64 64) translation with the week kernel cost for various values 7
Proposition 3 (Behavior of the conditional variance and input-output distance). Let n. E II(P,, Q) be an OT plan for w-wea kernel cost. Thenfor 72 > 71 2 holds true
(,)) CVara(m" and (m,, S Dist, (
(19)
17

---

Published as a conference paper at ICLR 2023
7
7 =
-=
y=1
7=
3
(T))
0.72
15.2
16.28
17.86
18.26
(ist
46.6
48.13
48.75
49.87
51.24
Costi. (7.)
23.3
21.56
19.0
16.01
13.48
Table 2: The values of CV)rr(f,), (i,)( and Costa, (Tx) of learned plans R. R R,, with different values of 7 on texture - shoes (64 64) translation with the kernel quadratic cost. i.e. for larger "i the OT plan F... on average for each x yields more conditionally diverse samples x (y)) but they are less close to x in features w.E.t
-1 The OT cost is non-increassin, i.e.
Costain (TTH,) 2 CostR,n (==2g)
(20)
The proof is given in Appendix G We empirically check the proposition by training OT maps for Ck. for texture - shoes translation (64 x 64), distance-induce & (55) and E {0, 3- 3.31, 1, 41, see Figure 13 and [2 We observe the increase of the variety of samples with the increase of 7. At the same time, with the increase of y, output samples become less similar to the inputs.
E EXPERIMENTS WITH DIFFERENT KERNELS
We empirically test several popular kernels texture handbag translation (64 x 64), 7 3- We consider bilinear, distance-based Gaussian and Laplacian kernels. The three latter kernels are characteristic. The quantitative and qualitative results are given in Figure [4
For the kernels in view, the squared feature distance can be expressed as llu(z)- xllx== for some increasing function h RR, RT. Due to this, all the stochastic transport maps try to preserve the input content in the pixel space. According to FID, the distance-based kernel performs better than the bilinear one, which agrees with the results in $5 Interestingly, both Gaussian and Laplacian kernels are slightly outperformed by the bilincar kernel. We do not know why this happens, but we presume that this might be related their boundness (0 < k(x, v) S 1) and exp operation.
F RESTRICTED DUALITY FOR THE WEAK QUADRATIC COST
In this section, we derive duality formula 9 for the w-eea quadratic cost. First, we derive formula (9) for y 1 by using (Gozlan & Juillet 2020 Theorems 1.1, 1.2). Next, following the discussion in (Gozlan Juillet, 2020 55.2). we generalize duality formula (9) to arbitrary ? >> We note that the
constants in our derivations differ from those in (Gozlan & Juillet 2020) since our quadratic cost
C2,7 differs by a constant multiplicative factor.
Part (7 1). From (Gozlan & Juillet 2020 Theorems 1.1, 1.2) it follows that there exists
lover-sseii-oontinuuss and convex function 2² RD IR U {oo} which maximizes the following expression:
U/
| 211))p((a) - S, o(s))
W 2,1 (P, ()
max
inf VER
(e())
(21)
2 + u* (x) is the optimal restricted potential, i.e., VΦ implements the projection of TP to Q and is 1-smooth convex function.
Importantly, d²(x" (x) def 11112
We consider the change of variables d(x) (ياا + (z) in
Since 1 v(y) is 1-strongly convex, its conjugate ((x) is 1-smooth. From the lower-semi-continuig of it follows that
(lv) = ( [1 +z)()) = ( (1-11- + +v) 2
デ |lvl + x(v) = -v(y) = 111l1 - (22)
1
2
We derive
inf [v(y) + -|1 - - = = vERo
|
inf (Ø(v) - (I, vil
DER
18

---

Published as a conference paper at ICLR 2023
X-p
x-x
Tix x1)
Tkx
T f()
T(x, 2s)
Tix, 2:)
T(x, 7xx,44 24)
Tx,
Bilinear k(y, y')
(y. y²)
Korotin et al. 0.08.
2023
Distance k(y.
1 |lll + 1 11 m11
FID 18.79
FID 16.13
X- R
7xx
T(x2,))
T(x, 24)
T(x, 22)
7(x 2s)
7(x
Tix, 24)
Tix, T(x
(c) Gaussian k(y, v¹) exp
18-211 2D
(d) Laplacian k(y, v/) = exp
1y-8'l)
27
FID = 20.89 0.09.
FID = 20 + 0.09.
Figure 14: Texture handbags (64 x 64) translation with the different 7-weak kernel costs.
1 - ||=1|| -(x)).
| sup [(x, v) - a(v)]
(23)
VERD
substitute 22 and
(23
and obtain
| d()
/ ||ll dQ(z) (1 ((x)dP(x)+ / o(v)d(()))
W (PP,
-max
(24)
x We only need to note that (24 exactly matches the desired (9) for 7 1.
(ECxx(1)
2
2
Part 2 (arbitrary 7 > 0). In (Gozlan & Juillet 2020 $5.2), the authors show that the OT problem between P and Q for the w-weak cost becomes the OT problem between LP and Q for the 1-weak cost. It holds
W2 (IP, Q by inf HP. + /
1-2
|a|| [dl)2P((x)
1 1-2 / dQ()) (25) + 2
27
=W3,,(,17.00
Backball Veraguas
2019 Thm. 1.4)
Moreover, xx(x) is the optimal restricted potential for y-weak cost between IP, Q and only (x) 7 700017 -1x) is the optimal restricted potential between 3 HP and Q for the 1-weak quadratic
19

---

Published as a conference paper at ICLR 2023
cost. Note that (x) Voi()2), i.e., (z) first scales P. by and then implements projection Voj ; 1P to Q. In particular, the function 6" is -Liiscchizz.
We reparameterize the duality formula 24 for distributions 1 and Q as follows:
[/
||>||
2 a( - ()))+) / 11a112 dQ((x)
W
Q de ECvx(1)
max
2
(Lx (o( (P) / ( )
1
||0|| dP(x)+ /
11ul2 dQ(z) (1x 0n (1(t2))P())+ / ( )
max (0vx()
7 x 2
(26)
||=1|
dT(x)) / llvll dQ(x)
(J o(z)dP(2)+ ///,// ((0)d((6))) (27)
max (ECOX(
7 x
2
In transition from (26 to 27 we use the change of variables for <(x) = 7 () known as the
right scalar multiplication. yields p(y) 7 (y).
To finish the derivation of dual form we simply substitute 27 to 25
G PROOFS
Assume the opposite, i.e., 7T x 8) Q. Then Tt implicitly represents some transport plan
Proof of Lemma /
ITP, Q) between P and Q. By the definition of f*, Tt and (6) it holds
Cost(PP Q) = LCS"T"")))
J Cle, r
+ / (g))((())
(28)
J Clx, ((e,
J, (()dd(())))))))))) J (())d((())=
(29)
f C(x, (iss)d(())))=
/ C(x, Cl
(30)
where in transition between lines (28) and we use the change of variables formula fory T T (=) and the equality [Tp(P x = Q. From (30) we that the cost of the plan n' [IP, Q) equals the optimal cost Cost(P, Q). As result, it is an optimal plan by definition. In turn, Tf is an stochastic OT map but not fake solution. This is contradiction. Thus, holds that T (P 5) # Q.
Proof of Lemma
We compute the C-transform of f*()) = Ivll - Φ5t (x)) 2
We have
(F*) = inf
(C,,, / 8 (
HEP())
1
/ || ull)d)(y) 2 Var(w) - / =111112
inf (EP())
25 (v))
2
2
2 ||=|| (x. S ddu(v)))
2 / [1v112
1
Var((1) - / |luule
inf (EP())
+
2
2
||00|1 - (ar, / ydu(v)) - 1 Var(n) +
inf mEP()))
[
Φ (2)dn(v))
1
||0:| + inf
/ (Φ:(v) - (r. u) dp(v)
? Var(n)
2
HEP()))
2
0 (v) - 2 ||vlll - (a,, v) du() + 2/ $1// y pdp(v))
|1 (31)
2 | + inf HEP()))
2
20

---

Published as a conference paper at ICLR 2023
Pick any y P())) and denote its expectation by m fy y du(l)). Since o' is 1 -moothh it holds that Ø² is n-strongly convex, i.e., o (v) |11 (x, v) is convex. We use the Jensen's inequality:
| o (v) 2 Ilul - (a, 3) du((y) 2 (m) 2 |mll - (x, m).
(32)
Therefore, may restrict the feasible set of inf in 31 to Dirac distributions d. m V. That is,
(f*) (x)
1 || + inf
6 (m)
|m|] (a, m) -
7 ||
2
mEy
2
2
1 -0-000000 xx(x,, (33)
2 || + inf
~ (m) - (x,, m))
= |=
sup mey
(I, m) - कt (m)
||=11²
mEy
2
2
(x)
where (xx) = d² (2) holds since of is continuous. We substitute
33 to
5
and obtain
f ( + S,r
( (())((()))=
|=|
2 - (x)) + / |1u1 - 55) -w) (F,
(34)
where in line (34). we use the optimality of 0* and
We conclude that f maximizes 5 66)
Proof of Proposition 7 For all v'.v" E (v) a E [0, 1). from the convexity of &b it follows that
Vayy + (1 a)v") I an/(y') + (1 - a))((")
(35)
By the definition of the subgradient of a convex function it also holds
va(ay' + (1 - a)²") 2 vvv) + (z, ay/ + (1 - a)y" - y) =
(v)(v) + 1 v)) + (1 a)) (v+v) + (r. - 9)) av/(1))))++))))) + (1 a))(("")
(36)
for all x E Ov) Therefore, 35 and (36) are equalities, and ary' + (1 - (1= E Uv()).
Proof of Theorem It holds that
Tt E arg inf C("" T) +> Tt E arginn inf / (C(I,T..8))
T2BS) - (TTo(t)) dP(x).
T The latter condition holds if and only if P-almost surely for all x E X we have
T
T E ing [C(x, T[)s) - f (T((())) T:2-y
(37)
We substitute f 11 xx and C C2 As result, we derive
(2,
f (T((e)))
1 f || - (T) 7 Var(Tiis)
/ | (1) (d3(z)
(T)
2 Z
2 |0||² - (I, / (s)))(((2)
1
Var Var( +
(T)()))))(()- =
2
||0||/ (x,,
Td (=))S(())) + ?
/ (=)3(()())
+ / 3 (T!
? [T) dS(=)) =
2
2
||]|| (x, 2
(=(:)d((2))
+ 7
/ (=()))((2))
+ 1 ((T(())))B()) 2 (38)
2
/
|0/| (5. / (+)))
+ 2
/ (=)
+ 2b (T((()))ss)) (39)
2
21

---

Published as a conference paper at ICLR 2023
where we substitute & = 0- 11..11 Recall that và is convex since o² is 2 -moohhhhh (Kakade et al. the convexity of da and the Jensen's 's inequality.
2009). In transition from (38) to (39).
Part To begin with, we prove implication "=" in
If (37 holds true, then (39 is the equality. If it not, one may pick (2) def 12 T (=))
which provides smaller value (39) for (37) than 7I. Let 7 be any stochastic OT map and xt be its
respective OT plan. We know that 7 E arg inf L( T), i.e., the optimal value 33 of (37 equals
1 | - (r, (=)=)d((=)) +
2
T (2) 2
+ v (1 (T())(()))
(40)
2
2
2 |==10² (x. VΦ (z)) 2 Vo (z)]l (z)(()))
(41)
where we use the equalities Vx) = Jy ydv (u/z) = 12 (2) see $ The function
m + |||| (z) + 3/1m|| + (m)) is 7-strongly convex in m, therefore, the minimizer
m V (a)) is unique. This yields that fg (=))B((= m (x).
We know that (38) equals (39). i.e.
) (T))) - e (J² (T(e)dB())) - J (TT - (vo' = (42)
and the Jensen's 's gap vanishes. Now we are going to prove that Supp(T, C (v(o We need to show that for every x' E 02 (Vo' (x)) the following inequality
<vv) 2 oe (Vo" (x)( + (x', (x)(
(43)
the equality Ti-S-almost surely for all y E Supp(TI Assume the opposite, i.e., for some x', holds true not T TI#SS-allen (S-almost surely. We integrate (43) w.r.t. y~T and get the strict incquality
J (O)d > (Vo + (x', yd((T)=))w) - v
We use the change of variables for y Ti and obtain
/ v (TI(3)) > (x) + (v/ z
(vo'())),
which contradicts
This finishes the proof of implication
Part 2. Now prove implication "-" in
For every 2 satisfying the conditions on the right-hand side of (1],, the Jensen's gap
42 is zero
since db is linear in Up (z)) Therefore, (38) equals (39). Due to [ (z)
V VØ" (z).
we have that (39) attains the optimal (minimal) values. Consequently, (37) holds.
Finally, we note that convexity of arg inf, C(J", T) follows from the convexity of sets (+)... n
Proof of Lemma 3 The plan π E [[(,, Q) is optimal if and only if Sy ydd(y)z) = V (x). That is, a stochastic map T X' 2 + y y is optimal if and only if it pushes P to Q (represents some plan [T(P, Q)), i.e., T=(P X Q and fg (=)= V (x)) The optimal barycentric projection 7 satisfies the second condition by the definition.
Consider implication " (a) Since T is a stochastic OT map, the first condition T x = Q holds true. Recall that by the definition of o² and T we have T x) = Vo' = (1:
(P). (P Consider implication (a) Since Proj ( = Q the first condition T x S) = Q holds true. Therefore, T is stochastic OT map.
Thus, Q = Proj
Now we prove implication (b) Let T be any stochastic OT map. We compute the second moment of H(P x 8) @ below:
1 [1ll)(Q())) /
(44)
22

---

Published as a conference paper at ICLR 2023
/x Var(TT / Var(T Var(TT+S)dP(())) / (d + [101)
1/ (= T(e))B(Ee) dP(())=
(45)
x
(46)
where in transition to (45). we use the equality Sz (2))((() (x): in transition (46).
the change of variables formula for y Vo and (x)(F) Q. Finally, by comparing 44
and (46), we obtain that Var(Ta#3) = 0 holds P-almost surely. That is, 7 is deterministic (does not depend on z) and (PXX))-lmoos surely matches the optimal barycentric projection T*.
Proof of Proposition We are going to show that the second moment of (PS)) is less than that of Q. Consequently, T :(P xS) + Q and T can not be stochastic OT map. First, for T we have
fx [T (2) (3)) = Var (T x 8))
-11 (1
Var((Q)
Var(Q) ||mal = / (TTT3)
Var(Q)
x V
(47)
where in the last equality we use TP x 8) = Q Finally, we derive
1 ((())))))))))) = (1-
<
/ ( +1=))
(48)
1 J2
[ (=)) (1-a) a) / [T)
= |second moment of Q]
(49)
In transition
48
we use the Jensen's incquality for 112. The inequality is strict since
|| 1|2
is strictly convex and Tt * T (P x S-almost surely). In transition to (49). we use (47) That is. TT:(P x S) * as its second moment is smaller.
Remark. The assumption ( * in Proposition is needed to guarantec the existence
of a function 7 E arg inf, L( T) which differs from the given stochastic OT map T" Due to our Lemma 3 the optimal barycenteric projection T E arg inf, L("*, 7)) is not an OT map. Thus, Tt 7 is a suitable example. Since T' = Q, we also have Var (TT S)) < Var(Q).
Proof of Lemma 4 The lower-semiiccotiiuityy (x. Cr, (r. ()) in (xr, (4) follows from the continuity of k compactness X' y C RD and (Santambrogio 2015 Lemma 7.3). F
The term 1/ fy [[x(=)) u(v) in 12 is linear in μ and, consequently, convex. The second 7 Var(utpi (utt)) The pushforward operator ut is linear and Var(-) is concave.
term in [12) equals Therefore, the second term is convex in y (7 2 0). As a result, Ck,, (x., (4) is convex μ.
To prove that CR,y is lower-bounded, we rewrite
122 analogously to (3), i...
1 (2, 2 [lu((x) / u(v)dd(())l 1 1-7 1 / [1((v) ul'' (ed
2 2
yxy
*We use lower semi coniiccnn (in μo) C(x, n)) w.n.t. the weak convergence of distributions P()"). In contrast, BBckhoff- Veraguas et al. (2019) work with μ E P,,))) C P())). i.e. with the distributions which have a finite p-th moment. They prove the existence and duality results for weak OT ( assuming that C(z,, j4) is lower semi-continuous w.r.t. the convergence in the Wasserstein-p sence in ())))) Since Since we consider compact Y, it holds that P)))) P())) and these notions of convergence coincide VVillani 2008 Def. 6.8).
23

---

Published as a conference paper at ICLR 2023
[|((x) / u(y)du(y)ll 1-2 Var(utu), (50)
Both terms are non-negative (y [0, 1D, i... C,,y (i) is lower bounded by 0.
Proof of Lemma S To begin with, we prove that & is characteristic, then Ck,, p1) = Cu,y p1)
strictly convex in μ.. The term fxx [|w(()) =(y))l [12 is linear in μ., so we focus on the second (variance) term - Var(ufj). We prove that Var(uūp) strictly concave. We derive
Var(utu) - y Iu(y) u(dd)laddww)dd
2 J/. [|u(v) (udp))))))))) Sox ( /// |u(v') =
1
/ ( ulw)du(s) /
J [ulw)lladu( (1 u(v)du(v)ll
(51)
The first in (5T) linear in μr, so it sufficies to prove that ( = ( || is
strictly convex. do this, we pick any μr * #2 E P(X). a E (0, 1). Since the kernel lt is characteristic, it holds that u(w) j u(w2). The squared norm function || 11 is strictly convex. As result, the following strict inequality holds
al (p)) )1 + (1 - ())a)llu()22111 > [lu(app + +1 a))2))
which yields strict convexity of ||u(μ))] Consequently, (x,( is strictly convex in In this
case, the weak OT functional π Ixx Ck,, (x)) also strictly convex and yields the
unique minimizer x" [[(P, Q) which the OT plan (Backhoff- Veraguus et 2019 $1.3.1). O
Proof of Theorem ?
To begin with, we expand the functional L:
arg arginf inf / (C(I,IHH)) J - (Io(t)))dd(s)) dP(x). (52)
T E arg C(F" T) +
Define 3 def T. We going to prove that μ. (y(xx) where x* [1 @) is the (unique) optimal plan; this yields that 7 is a stochastic OT map. Since the optimization over functions in NOT equals to the optimization over distributions that they generate (Korotin al. 2023 54.1), have
{ E arginf inf / (C(z, f (()d (u.)
(53)
where the inf taken over collections of distributions far E P()) indexed by X. Importantly, be split into X' independent problems, i.e., have that
(53
"e E arg inf [C(x, - J ("))dda
(54)
holds true P-almost surely for all x E X. Note that the functional μ + C(r, - Sy f dy))
consists of a strictly convex term C(r, p)), which follows from the proof of Lemma and linear term (integral over μ)). Therefore, the functional itself strictly convex. Since x (y][z) minimizes this functional, it is the unique solution due to the strict convexity. Therefore, (x) T" <>v((> holds
true Plllmost surely for E X' and Tays pt n (y)z), I), i.e., T" is stochastic OT map.
Proof of Proposition 3 Since = is optimal for the 71 -wek cost, for all E [I Q) it holds Costg,y (m²,)) S Cost (T). In particular, for = #,. holds true that
Dist (x) 71 CVar.(m)))) < (m= mn CVar
(55)
24

---

Published as a conference paper at ICLR 2023
Analogously, Th is optimal for the 92 -2-weak cost; the following holds:
Dist (mi2)~72 CVar. S DDitt )- -72 (V
(56)
We sum 55 and (56) and obtain
71 CVar (T",) - Y2 CVar ( - -11 CVaru (mT2)) 72 CVar (T
or, equivalently,
- (1) ( 2 (72 - 71) CVaru (TT2):
( which is equivalent to (TT,, CVar (m²,) since 72 7/2 >> O. Now we multiply 55) and
(56) by Y2 and y/, respectively, and sum the resulting inequalities. We obtain
72 Dist (m)))) + 71 Dist (TTTE) S 72 Dist + 711 (ist,
or, equivalently,
(12 - 71 Dist (T),)) S (72 7) ( (mit)
which provides Dist (T < Dist (Tzz2 Finally, we note that
Costi, (TiZ2) = inf Cost (T)) I Costi (T xEI((.0))
Costi (TTT,) (72
n) CVaru(T 2 Costi,n (TT
(57)
20
20
which concludes the proof.
H WEAK QUADRATIC VS. KERNEL COSTS ON REAL DATA
The goal of this section is to demonstrate that our proposed kernel cost (2) consistently outperforms the weak quadratic cost (3) in the downstream task of unpaired image translation. We consider the distance-induced kernel (xx,, 3) = 1 |||=|| | + llyll 2/2 | y||- In short, we run NOT (Korotin et al., 2023 Algorithm 1) multiple times (with various random seeds) with the same hyperparameters (Appendix for weak and kernel costs, and then we compare the obtained FID (μI + r)). o).
Datasets. We consider shoes -> handbags and celeba (female) - anime translation. We work only with small 32 x 32 images to speed up the training and be able to run many experiments.
EXPERIMENT 1. We consider the w-eea quadratic cost for each 7 { 1, 3. 2} we run NOT with 5 diffcrent random seeds and train it for 60k iterations of fw. In this experiment, during training, we evaluate test FID every 1k iteration and for each experiment we report 3 FID values: the best FID value of iterations 25-60k indicating what the model can achieve best, the max FID value of iterations 25-60k indicating what the model achieves worst (because of potential training instabilities) and the last FID value at the end of training (60k) showing what the model actually achieved.
The experimental results of Tables the increase of parameter 7, the best FID stably increases. Second, the overall training becomes less stable: max FID becomes extremely large, which indicates severe fluctuations of the model. In particular, both the mean and standard deviation of last FID (as well as max FID) drastically increase.
provide several important insights. First, we see that with
Why does this happen? We think that with the increase of y sets (.) II become large. These sets determine how much a fake solution may vary (Theorem) I.. Thus, this naturally leads to high ambiguity of the solutions and results in unstable and unpredictable behaviour.
EXPERIMENT 2. We pick the highest considered value 7 2 and show that our w-eak kernel cost performs better than the weak quadratic cost from the previous experiments.
We run NOT with the kernel cost 5 times and report the results in the same Tables 3 The results show that even for high the issues with the fluctuation are notably softened. This is seen from the fact that for 7 2 the gap between the last FID (or max FID) and best much smaller for the kernel cost than for the quadratic cost. In particular, this gap is comparable to the gap for = wwek quadratic cost for which sets U.)()) are presumably small and provide less ambiguity to the solutions.
Conclusion. Our empirical evaluation shows that NOT with our proposed kernel costs yields more stable behaviour than NOT with the weak quadratic cost. This agrees with our theory which suggests that one of the reasons for unstable behaviour and severe fluctuations might be the existence of the fake solutions 3...I. Our weak kernel cost removes all the fake solutions ($3.2).
'ee choose 25k iterations as the starting point because at this time point FID roughly stabilizes at small level. This indicates the model has nearly converged and starts fluctuating around the optimum.
25

---

Published as a conference paper at ICLR 2023
Weak kemel
Method
Weak quadratic, C2.y
Ckty [Ours]
Setting
7= 0.5
7=1
7 1.5
FID
16.08
0.37 37]
19.87
23.01 + 5.16
1.26
16.50
Last FTD
21.98
3.04
33.56 4 10.49
30.35 4: 8.85
37.18 4: 8.58
20.19
2.36
Max FID
28.40 1 3.18
52.03 + 16.00
46.59 1: 9.53
67.50 de 30.76
29.85 3.75
Table 3: Test FID (μ + a) shoes handbags, 32 32 of C2,7 and Ck.y for different 7 Red color highlights μ 2 30, orange color highlights a 2 5.
Weak kernel
Method
Weak quadratic, C2.5
Cs.s [Ours]
Setting
7= 0.5
7=1
7= 1.5
7=2
7 =
Best FID
18.88 1 0.57
34.71
6.48
24.49
0.64
40.49 1: 5.57
19.39 1. 1.06
:: 1.98
36.89
8.19
28.49
49.66
5.45
20.62
1.66
Max FID
29.51 # 1.45
81.78
+ 25.93
48.44 + 6.14
76.25 + 4.20
36.86 + 0.45
Table 4: Test FIDI (u + σ) on celeba (female) + anime, 32 x 32 of C2., and Ck.7 for different y Red color highlights μ 2 40, orange color highlights 4.
I ADDITIONAL TRAINING DETAILS
Pre-processing. In all the cases, we rescale RGB channels of images from [0. to [-1. As in (Korotin al. 2023), we beforehand rescale anime face images to 512 512, and do 256 256 crop with the center located 14 pixels above the image center to get the face. Next, for all the datasets except for the describable textures, we resize images to required size (64 64 or 128 128).
Specifically for the describable textures dataset (R:5K textures), we augment the samples. We rescale input textures to minimal border size of 300, do the random resized crop (from 128 to 300 pixels) and random horizontal & vertical flips. Then we resize images the required size (64 x 64 or 128 128).
Neural networks. We use WGAN-QC discriminator's ResNet architecture (Liu et al. 2019) for potential We use UNe(" [Ronneberger et al. 2015) as the stochastic transport map T(x, 2) (2). To condition it on 2, we insert conditional instance normalization (CondIN) layers after each UNet's upscaling block? We use CondIN from AugCycleGAN (Almahairi et al. 2018). In experiments, the 128-dimensional standard Gaussian noise.
NOT algorithm (Korotin al. 2026 Algorithm 1). We use the Adam optimizer (Kingma & Ba 2014) with the default betas for both Te and fa The learning rate is ly 1 10 We use the MultiStepLR scheduler which decreases (r by 2 after [15k, 25k, 40k, 55k, 70k] (iterations of fw. The batch size is XX 64, 2z = 4. The number of inner iterations is ky 10. In toy experiments, we do 10K total iterations of fw update. In the image-to-imet -mage translation experiments, we observe convergence in == 70k iterations for 128 x 128 datasets, in 40k iterations for 64 x 64 datasets. mmage-to-image translation, we gradually change y. Starting from = 0, we linearly increase it to the desired value (mostly !) during 25K first iterations of fa-
Optimization. To learn stochastic OT maps,
Computational complexity. NOT with kernel costs for 128 x 128 images converges in 3-4 days on a 4x Tesla V100 GPUs (16 GB). This is slightly bigger than the respective time for NOT (Korotin (6) with the quadratic cost due to the reasons discussed in $.3
al.
2023
gi gttnbb/cww/rrrrrmm///reereeeeeee
26

---

Published as a conference paper at ICLR 2023
J COMPARISON WITH NOT WITH THE QUADRATIC COST
C2.0
C (ours)
0,,
Cey (ours)
C2.9
Cz.y
Czy (ours)
TOx.2 21
T(x.4)
Tixzi
TIx, 21)
T(x,)])
Tix.2s) T(xzz)
TOx, 23)
X-9 T(x,7))
(a) Outdoor church, 128 x 128, (b) Celeba (f) + anime, 128 x 128,
(c) Handbags + shoes, 128 128.
Figure 15: Unpaired translation with Neural Optimal Transport with various costs (C2,0- C2 Ck.T)
X-P
Tlx.z.)
fixzz)
Tixzz
f Z3)
Fix. f(x
T(x
Pix, Z3)
Tix, 25)
C2.0
(b) C2.5
CK.Y [Ours].
Korotin et al. 2023 85.2).
Korottn et al. 2023 85.3).
Figure 16: Celeba (f) anime (128 128) translation with NOT with costs C2 C2,7 Ck
X- 0
X-P
X-2
Tlx, Z1)
Txxz
f(x
Ptx, Z2)
Fix,zy) 7x)
T(x
tris
fix, 73)
7xx,z:)
(a) C2.0
Korotin et al.
2023 85.2). (b) C2.5
Korotin et al.
2023 85.3).
(c) C..y [Ours].
Figure 17: Outdoor - church (128 x 128) translation with NOT with costs C2.0. C2,y Ck
27

---

Published as a conference paper at ICLR 2023
x g
X-s
X-
7 21)
T(x.2.)
T T2x
T 22)
T zz)
1 75)
f zj)
f(x,2s)
(a) C2
Korotin el al.
2023 85.2). (b) C2.7
Korotin el al.
2023 $5.3).
(c) Ckey [Ours].
Figure 18: Handbags shoes (128 128) translation with NOT with costs C2 C2,7 CK
K COMPARISON WITH IMAGE-TO-IMACE TRANSLATION METHODS
We compare NOT with our kernel costs with principal models lone-to-one and one-to-many) for unpaired image-to-image translation. We consider CycleGAN Zhu al. 2017), AugCycleGANT AAlmahairi et al. 2018) and MUNIT (Huang et al. 2018) for comparison. We use the official or community implementations with the hyperparameters from the respective papers. We consider outdoor + church and texture + shoes dataset pairs (128 x 128). The FID scores are given in Table
Qualitative examples are shown in Figures 20
19
Method
One-to-one
One-to-many
Datasets (128 128)
Cycle GAN (with L1 loss)
Cycle GAN (no L1 loss)
NOT with Ck.y (Ours)
AngCycleGAN
MUNIT
Outdoor church
43.74
36.16
51.15 1
32.14 0.18
15.16 0.03
Texture shoes
34.65 0.12
50.95 0.12
N/A
43.74 0.16
24.84 0.09
Table 5: Test FID] of the considered image-to to-iaae translation methods.
We do not include the results of AugCycleGAN texture -shoe as it did not converge these datasets (FID > 100). We tried tuning its hyperparameters, but this did not yield improvement.
cycl eqgan
qi htchh./ccm//aaaaaa///uumeteeeeee
g ttthbb.ccm///llaass//iiii
28

---

Published as a conference paper at ICLR 2023
T(x)
Tixi
(a) CycleGAN
(b) CycleGAN (no identity loss)
X-P
X-P
7(x, 21)
T(x.
Tlx, (xx
T(x, 25)
7(x. 2,)
M
Pix, 2z)
(c) MUNIT
(d) NOT with Ck,v. [Ours]
Figure 19: Texture shoes (128 x 128) translation with various methods.
29

---

Published as a conference paper at ICLR 2023
T(x)
Tix
(a) CycleGAN (no identity loss)
(b) CycleGAN
X-
Tix, 2;)
Tix, 2i)
TVx 2g)
Tix
f(x,2,)
7(x,2s)
(c) MUNIT
(d) AugCycleGAN
P
fix,
T(x.22)
T(x. 23)
0
(e) NOT with Ck.y [Ours]
Figure 20: Outdoor + church (128 x 128) translation with various methods.
30

---

Published as a conference paper at ICLR 2023
L
ADDITIONAL EXPERIMENTAL RESULTS
x-p
T(x 21
T 24)
T(x. 23)
(a) Input images and random translated examples T2(2).
x P
Tix 2
2 e-10
a 207
3/7
a= 4/7
--
5/7
6/7
T(x.2))
(b) Interpolation in the conditional latent space, x = (1 0.)21 - 022-
Figure 21: Celeba (female) anime translation, 128 128. Additional examples.
31

---

Published as a conference paper at ICLR 2023
X
T(x.
7(x, 2z)
T(x,
T(x, z4)
(a) Input images and random translated examples T₃ (z).
T(x
a --10
a 2/7
G 3/7
g= 4/7
5/7
6/7
Tu.
(b) Interpolation in the conditional latent space, z (1 0:)= + Q22.
Figure 22: Outdoor - church, 128 128, Additional examples.
32

---

Published as a conference paper at ICLR 2023
X-p
T(x. (x)
7(x, 2z)
T(x,
T(x, Z4)
(a) Input images and random translated examples T₃ (z).
X P
T(x
a 1/
a 2/7
3/7
= 4/7
=
5/7
6/7
T(x.2)
TWII
FRIS
DRSS
(b) Interpolation in the conditional latent space, z (1 a:)= + 022-
Figure 23: Texture shoes translation, 128 128. Additional examples.
33

---

Published as a conference paper at ICLR 2023
X~P
T(x. 24)
T(x, 23)
T(x. Zs)
T(x. Z4)
(a) Input images x and random translated examples (2))).
Tix
Tx,
(b) Interpolation in the conditional latent space, (1 0.)2 0.22.
Figure 24: Texture + handbags translation, 128 x 128. Additional examples.
34

---

Published as a conference paper at ICLR 2023
X~P
T(x. 21
T(x 2z)
T(x. Zs
T(x.
(a) Input images x and random translated examples Ta (2).
Tix, m)
3/7
Tx.4)
(h) Interpolation in the conditional latent space, 2 0)21 022.
Figure 25: Shoes + handbags translation, 128 x 128. Additional examples.
35

---

Published as a conference paper at ICLR 2023
X- p
T(x. Z1
T(x, 2z)
T(x. 2z)
T(x.
(a) Input images a and random translated examples T₃ (2))).
Tix.
Tx.4)
(b) Interpolation in the conditional latent space, (1 0.)2 0.22.
Figure 26: Handbags + shoes translation. 128 x 128, Additional examples.
36


Reviews:
[{"review_id": "nCm-M9I4nT", "reviewer": "Reviewer_QYaw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors propose a novel technique to compute weak optimal transport plan between two distributions, given in possibly two different spaces. Based on an earlier work of Gozlan et al, the computation of OT plan is formulated as a certain minimax task. The major issue that the paper addresses is that some saddle points of the latter task can correspond to fake plans. Existence of fake plans is proven theoretically and demonstrated on toy experiments.", "summary_of_the_review": "Overall, a quantity and a quality of experiments convinces me in correctness of major points of the paper. Though, for me it is hard to judge experiments with unpaired image-to-image translation task. Some discussions of  unpaired image-to-image translation task, or a citation where one can learn details of that problem is needed.\n", "strength_and_weaknesses": "First, it looks like existence of fake plans is a result of some kind of degeneracy in the problem formulation (like the multicollinearity problem in linear regression). Can it be tackled by some form of regularization? Interesting question was asked on page 6: \"Should we really care about solutions being fake?\" and noted that \"the map T may fluctuate between fake solutions rather than converge.\" The question is: does it fluctuate between fake solutions, or, in fact, it fluctuates as some convex combination of stochastic OT plans? The Proposition 2 hints that it could be the second case. \nAnother issue is that existence of fake plans are demonstrated on toy experiments. A natural question is: are fake plans common when the technique is applied to real-world data, e.g. to unpaired image-to-image translation task?\n\nMinor comments:\nPage 1: (a) Celeba (female) → shoes  ->   (a) Celeba (female) → anime  \nPage 2:  fomulations ->  formulations  \nPage 8: under perform -> underperform", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kwp6RwGhd8", "reviewer": "Reviewer_9WD8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes an extended method for neural optimal transport.\nThe authors first point out that the theoretical flaws of neural optimal transport with using the weak quadratic cost in terms of potentially learning face plans.\nThen, they proposed a method of using kernel costs of neural optimal transport to overcome learning fake plans.\nThis paper also show the theoretical justification that the proposed method can solve the lack of the previous method.\nThe experiments are conducted on the image-to-image translation task, and demonstrate that the proposed method produces better results.\n", "summary_of_the_review": "I think this paper (potentially) has sufficient contributions to be accepted to the conference.\nHowever, as I wrote above, I am not a specialist in neural optimal transport, so that it is hard for me to check the correctness of the theoretical justification of this paper.\nMy recommendation is based on the fact that this paper shows the correct justification.", "strength_and_weaknesses": "Strength:\n* The proposed method seems reasonable, and motivation is clear.\n* This paper provides the theoretical justification of superiority of the proposed method.\n* The figures help to intuitively understand the methods.\n\n\nWeaknesses:\n* The most of the experimental results shown in this paper are qualitative comparisons with small number of evaluation data. Therefore, it may exist the doubt of cherry picking.\n* Similarly, it is hard to say that the proposed method really provides the better performance by solving the fake plan issue from the results shown in this paper. Therefore, I feel that the experimental results do not much support the main claim of this paper.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b9rr4Aaw5y", "reviewer": "Reviewer_84ix", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduced kernel weak quadratic costs to solve the problem that NOT with the weak quadratic cost might learn fake plans which are not optimal. \nAnd it conducts the theoretical and empirical analysis of the saddle point optimization problem of NOT algorithm for the weak quadratic cost. \nFinally, they analyze from theory and examples to show that NOT generates fake solutions which do not provide an OT plan.", "summary_of_the_review": "In this paper, a new neural optimal transport algorithm based on kernel cost function is proposed, and the deficiency of NOT is analyzed theoretically. \nHowever, the lack of experimental support, the key is the lack of experimental comparison of NOT, does not reflect the advantages of improving the cost function. \nMoreover, there is a lack of comparison of classical neural OT algorithms, such as ICNN.", "strength_and_weaknesses": "Strengths: This paper conducts the theoretical and empirical analysis of the saddle point optimization problem of NOT algorithm for the weak quadratic cost, this show it may appear fake solutions. \nThis paper introduces kernel quadratic costs to solve above problem, and it proves the feasibility of the proposed algorithm via theoretical analysis and examples.\n\nWeaknesses: The cost function with kernel is too complex in practice. Comparison with other neural network-based algorithms for solving OT mappings is lacking. \nThis paper does not explain the advantages of the proposed algorithm compared with the classical algorithm, and there is no experimental support.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "04CqlmS2Kg", "reviewer": "Reviewer_goNj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces kernel neural optimal transport. Prior work on neural optimal transport makes use of a weak cost. The paper proves that weak costs admit non-solutions in the sense that the resulting plans do not satisfy the marginal constraints. The authors also propose that the weak costs are related to optimization instability. As a solution, weak kernel costs are introduced. Extensive testing demonstrates the effectiveness of weak kernel costs including via unpaired image to image translation tasks. ", "summary_of_the_review": "The paper introduces kernel NOT, which uses weak kernel costs, to address issues in earlier neural OT work. There are both theoretical and extensive simulation results. The simulations do not document the limitations of and solution to the prior work as clearly as I would have liked. Overall, this is a nice contribution. ", "strength_and_weaknesses": "Strengths: \n- Neural OT and related methods are of increasing interest across the community. \n- The paper is generally well written. The math is clear and appropriate. Proofs are thorough, complete, and in my checking correct.\n- The theoretical results are accompanied by detailed simulations. \n\nWeaknesses:\n- The claimed limitations of weak costs were not detailed as comprehensively as I would have liked. Specifically, how far off are the \"fake\" plans? Also, how bad is the instability? These seem like important points, given that they motivate the paper in the first place. \n- I found the exposition difficult. The introduction is quite short, has jargon that is not explained, and hence doesn't completely set up the problem. After reading the paper through, I appreciate the contribution but it think it would help to try to get more of the details earlier in the paper. \n- There are a large number of figures with image to image translation. I don't see what the unique contribution is for each. It seems like one would suffice in the main text. \n\nOther detailed comments\n- I didn't really understand what figure 1 was supposed to show. How would I know if the result is \"good\"? \n- Please define strong and weak transport costs in the introduction. What is the significance of the difference aside from the fact that people use them? \n- Please define fake solutions. It would be helpful to be specific here so readers understand the gravity of the situation. \n- Please define a weak kernel cost when one uses it the first time. \n- It is not clear why imagine to image translation is a good way of testing performance. \n- \"may be not an optimal stochastic map. In this paper, we show that for the γ-weak quadratic cost (3) this may be problematic: the arg infT sets might contain fake\nsolutions T\" I don't quite understand whether this is the same point, i.e. it is problematic because it is not an optimal stochastic map, or whether there are other aspects that are problematic. If it is problematic because it is not an optimal stochastic map, and the fake solutions are of this type, it would help to use simpler language (fewer different names) and adopt a label more descriptive than \"fake solutions\". \n- I appreciated the inclusion of a derivation of (9) in the appendix. \n- \"Should we really care about solutions being fake?\" It would be great for the answer to this question to appear early in the paper. \n- It would be nice to have some sense of how bad fake solutions are. Are these truly pathological? (In the sense of being far from Q?) Also, can we demonstrate the stability issues more concretely? \n- I don't see the added value of having the example figures in the paper (beyond the first one). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster