On the Gradient Formula for learning Generative Models with Regularized Optimal Transport Costs
Authors: Antoine Houdard
Arthur Leclaire
Nicolas Papadakis
Julien Rabin
Venue: Accepted by TMLR ()

Abstract: Learning a Wasserstein Generative Adversarial Networks (WGAN) requires the differentiation of the optimal transport cost with respect to the parameters of the generative model. In this work, we provide sufficient conditions for the  existence of a gradient formula in two different frameworks: the case of semi-discrete optimal transport (i.e. with a discrete target distribution) and the case of regularized optimal transport (i.e. with an entropic penalty). In both cases the gradient formula involves a solution of the semi-dual formulation of the optimal transport cost. Our study makes a connection between the gradient of the WGAN loss function and the Laguerre diagrams associated to semi-discrete transport maps. The learning problem is addressed with an alternating algorithm, which is in general not convergent. However, in most cases, it stabilizes close to a relevant  solution for the generative learning problem. We also show that entropic regularization can improve the convergence speed but noticeably changes the shape of the learned generative model.

Published in Transactions on Machine Learning Research (MM/YYYY)
On the Gradient Formula for learning Generative Models with Regularized Optimal Transport Costs
Antoine Houdard
Antoine. Hestone.Houdard@maane hettimathhhu-bbddeeee boroodeauu.jjp fr Arthur. OrtharrLeclloirer Lecloire @math. Mt- bordeaua. fr Nicolas. Papadakks @malh. -obboouu....f..
Arthur Leclaire
Nicolas Papadakis
Univ. Bordeaur, Bordeaur INP, CNRS, IMB, UMR 5251,N-33400 Talence, France
Julien Rabin
Julien.Rabén
Normandie Univ., UNICAEN, ENSICAEN, CNRS, GREYC, 14000 Caen, France
Reviewed on OpenReview: https: // openreview. net/ net//formm id= FostuhddCC
Abstract
Learning a Wasscrstein Generative Adversarial Networks (WGAN) requires the differentia- tion of the optimal transport cost with respect to the parameters of the generative model. In this work, we provide sufficient conditions for the existence of gradient formula in two different frameworks: the case of semi-discrete optimal transport (í.e. with discrete target distribution) and the case of regularized optimal transport (f.e. with an entropic penalty). In both cases the gradient formula involves a solution of the semi-dual formulation of the optimal transport cost. Our study makes a connection between the gradient of the WGAN loss function and the Laguerre diagrams associated to semi-discrete transport maps. The learning problem is addressed with an alternating algorithm, which is in general not con- vergent. However, in most cases, it stabilizes close to relevant solution for the generative learning problem. We also show that entropic regularization can improve the convergence speed but noticeably changes the shape of the learned generative model.
1 Introduction
In data science, generative models are ubiquitous to approximate a data distribution in order to draw new samples, to interpolate data points, to design a geometric structure revealing some interpretable dimensions of data (Radford et al. 2016 Shen et al. 2020) or to restore corrupted data by regularizing inverse prob-
lems (Bora et al.J [2017] Hand & Joshi 2009 Hyder & Asil, 2020 Heckel & Soltanolkotabi 2020 Menon el al., 2020 Shamshad & Ahmed] 22200] Damara al. 2021 Leong 2021). Given the empirical distribution of the data supported on a compact set y Rda estimating a generative network consists in solving
arg arg min L(ue, 8EB
(1)
where Mg is the distribution of generated samples (parameterized by in an open subset θ c RR) with support included a compact set X' C R2d and where The distribution pe is often considered to be the law of random variable go(Z) where go is a neural network and Z random variable, and samples of the model can be obtained by passing new realizations of Z through the network 9o- These distributions are generally built upon features computed from samples and data points, such as the latent space of a variational auto-encoder (Kingma & WWeling 2014).
loss function between probability distributions.
The choice of the loss function is crucial to quantify the discrepancy between probability distributions. In the seminal work Goodfellww et al. (2014) on generative adversarial networks (GAN), the loss function (1) is related, in a dual sense, the Jensen-Shane Shannon divergence between feature distributions. The Jensen- Shannon divergence is nevertheless not robust enough to data outliers and leads to convergence issues when

---

Published in Transactions on Machine Learning Research (MM/YYYY)
learning the GAN model. For this reason, Arjovsky et al. (2017) later proposed to use optimal transport (OT)
costs in the loss function, leading to new generative models called Wasserstein GANs (WGANs).
Wasscrstein distance The optimal transport cost between probability distributions pi and v is
inf Jrxs c(z, V)dT(,
W(u,
(2)
xell(pp.r)
where IT v) is the set of probability distributions X' x y having marginals pe and v, while the ground
cost X' x V + I is continuous function in which c(z,y) y) represents the elementary cost between
locations z E X' and y E E... A popular choice for the cost is the Euclidean distance to the power 2 1, d.e.
((x,y) = | - y|| EE=n(x: v;)²) The cost function may also be defined as metric in feature space. As we will recall later, the OT cost (2) admits dual formulation (Santambrogio 2015)
(1 p/2
for which ((..)) defines the well-known y- passsessteenn distance.
/ odfpo + vide, (P.D)E,
sup
(3)
where (pp, 15) a couple of dual variables that belongs to the set
K. = ((p,))))))))))) ((x) x (()), subject to xxx) + ((y) S c(z,y) N@vae.
(4)
where (x) indicates the set of real continuous functions on X' and @ the product of two measures. mizing one of the dual variables in 3 amounts to taking the c-transform
Opti-
(x)
min c(x, y) (v)) yEy
(5)
thus lcading to another expression of the OT cost, called "semi-dual formulation":
/ wddpa + vdd..
(No, v) sup
(6)
vesiy)
Solving the constrained dual problem (3) is difficult and possibly infinite-dimensional optimization prob-
lem. To circumvent this issue, one can turn to the entropic formulation of OT (Chizat 2017 Peyró & Cuturi 2019) which is an unconstrained optimization problem on (p, where the regularization of the OT problem is controlled by a parameter > O. The eutropy-regulltized OT admits a similar semi-dual formulation (6) except that a softmin (a smoothed version of the minimum) is involved in the computation of the c-transform (5). In the discrete setting, the regularized OT cost can be computed efficiently with the Sinkhorn algorithm (Peyré & Cuturi 2019), which exhibits geometric convergence. When one of the distribution is continuous (as in (L), one has to rely stochastic algorithms (Genevay et al. 2016), which are provably convergent, but considerably slower.
Learning Wasserstein Generative models In this paper we study the case where the loss function C for learning the generative model the OT cost with entropic regularization (including the unregularized case 0, see Definition 2 below):
arg min Wx v).
(7)
0eB
In practice, the optimization problem 7 can be solved with a gradient- basod algorithm, such as the ADAM algorithm (Kingma & Ba 2015). that requires the computation of the gradients of the Wasserstein cost with respect to 0. To compute this gradient, we rely on the semi-dual formulation of regularized OT. In particular, are interested in the conditions ensuring that the gradient at a point On satisfies
= (foadlte)
ve(Wa(Ho,)) 0=00- = Vo
(8)
18=80
where (y,, v).) an optimal dual variable for WX(Ha, v). The objective of this paper is to provide set of hypotheses that validate {8) and to show how it applies to generative models go parameterized by neural networks.
2

---

Published in Transactions on Machine Learning Research (MM/YYY)
1.1 Related works
Learning generative model with a Wasserstein cost requires the computation of the gradient which involves the optimal dual variable fr.. We now detail related works on differentiation of OT costs, learning of generative modols with OT costs, dual OT solver and semi-discrete OT.
Differentiability of OT costs The gradient formula ( is given in the seminal paper on WGAN (Arjovsky et al., 2017) with the assumption that both sides of the equality exist. This formula has been extended to more general costs and exploited in several papers related WGAN learning, for example (Liu et al. 2019).
In the context of discrete regularized OT, one can find in (Sanjabi et al.] 2018 Appendix C) gradient formula expressed through the primal formulation, with short proof limited to discrete regularized OT. All these results are based on some version of the so-called "envelope theorem" " (also called Danskin's 's theorem in the context of convex optimization), which allows to differentiate under the maximum. This theorem also requires regularity assumptions on the generator go- As we will see in Scction 2.3 in the discrete sctting, there exist some irregular cases where these assumptions are not sufficient to make formula ( licit.
In parallel to the literature on WGAN, the regularity and gradient of regularized OT costs p p+ Wx (with À > 0) are studied in (Cuturi & Peyré 2016 Prop. 2.3) for discrete distributions (p. q). The Gâtcaux- differentiabillity of (2,4) + Wx(v, g) is also proved in (Feydy et al. 2019), and exlended to continuous differentiability in (Bigot et al. 2019 Prop. 2.3). From these results, if (pe) is parametric family of distribution supported on the same finite set, the chain rule gives the differentiability of A + (PPP..))
Wasserstein Generative Models The method of Arjovsky et al. 2017 is based on the 1-Wasserstein distance and it only requires one dual variable that is constrained to be 1-Lipschitz. In practice, this dual variable is parameterized by a neural network, and the Lipschitz constraint is enforced by weight clipping (WGAN-WC). On similar formulation, Gulrajani et. al. (2017) encourage Lipschitzness by including a gradient penalty in the dual loss (WGAN-GP). Genevay et al. (2018) introduce the so-called Sinkhorn diver- gences (based on regularized OT) which reduce the problem of sample complexity when learning generative models. (Segyy et al. (2018) also consider regularized OT costs with a generic cost. function. This leads to an unconstrained dual problem, but with two dual variables. In practice, the authors choose to parameter- ize both dual variables with neural networks. For the same problem, the authors of [Sanjabi et al. (2018) study the convergence and stability of the training procedure, the convergence being proved for the case of discrete distributions. In particular, they give the expression of the gradient of (8), under a primal form, in the case of discrete regularized OT. This gradient expression is exploited to perform WGAN training by stochastic gradient descent. In Liu et al.] (2019), similar regularized OT framework is applied to empirical distributions (i.e. discrete distributions obtained from samples) to learn a generator, with the particularity that the cost function depends on a set of simultancously-earned features.
Closer to our framework, Chen et al. (2019) consider the semi-dual formulation of OT 66. In this work, the dual variable d is optimized with the the Average Stochastic Gradient Descent (ASGD) algorithm proposed in (Genevay et al.] 2016). Contrary to (Seguy et al.) 2018), the dual variable is not parameterized with neural network, which hinders the applicability of the method to very large datasets. Indeed, shown in (Leclaire & Rabin| 2021), the convergence speed of ASGD for optimizing t decreases when either the dimension d of samples or the dimension of vector và (equal to the number of training points) increases. In (Chen et al., 2019), the primal solution π of (2) is finally used to perform a gradient step on the generative model. As a result, their whole algorithm not expressed as a direct. minimization of (1.. This is a main difference with our work, in which the proposed gradient calculation for (8) makes it possible to train the generator go and the dual variable y with an alternating min-max procedure on the dual cost (
In similar work, Mallasto et al. (2019a) parameterize the dual variable & by neural network and obtain the second dual variable & with an approximated c-transform computed on mini-batches. With this approx- imation, the pair of dual variables may not satisfy the constraint (4) A penalty on c(æ, v) - <(x) - vby) is thus integrated in the loss function. This approach scales up to large databases, with a relatively ac- curate estimation of the Wasserstein cost. On batch stratogy, Fatras et al. (2020) consider an alternative Wasserstein cost defined as an expectation over mini-batches, This stochastic approximation introduces an estimation bias which is shown in practice to regularize the transportation problem.
3

---

Published in Transactions on Machine Learning Research (MM/YYY)
OT dual solvers Several authors (Mallasto et al.) 2019b Stanezuk et al. 2021 Korotin et al. 2021 2022
question the performance of OT dual solvers and its impact on WGAN learning. Mallasto et al. 2019b) compare several algorithms to estimate the dual variables, namely WGAN-WC, WGAN-GP and two methods denoted as "c-transform" and "(c, -ttransfoom""" These two last methods, while better estimating the OT cost, do not improve the visual quality of the generative model when used WGAN learning, producing very blurry images for the CelebA database. These findings are confirmed by Stanczuk et al. (2021) who provide explanations related to biased estimation of Wasserstein gradients, false Wasserstein minima supported on barycenters, and limitations of the use of the Euclidean distance between natural images.
2022). In To pursue these investigations, benchmarks for OT solvers are proposed in (Korotin et al. 2021
these works, absolutely continuous measures μ, together with their corresponding groundtruth OT map are provided for the 2- 2-Wasserstein and 1-Wasserstein costs. The compared OT solvers are all based on parameterizations of the dual problem with neural networks, whose optimization requires to draw some batches of μ and v, which regularizes the OT cost and induces an estimation bias.
In this paper, in order to stay close possible to the original OT cost, we do not apply batch procedure V, thus restricting our experiments to smaller datasets. Our numerical study shows that, with the simpler MNIST database, WGAN learning based on c-transforms computed on all datapoints (i.e. not batchwise) can produce sharp images while relying on a provably-convergent estimation algorithm for the Wasserstein cost. Also, our theoretical analysis of gradients enables to better understand the impact of the errors made by the OT dual solver: the performance of the dual solver does not guarantee the sharpness of generated images, but it plays role in making the generative distribution cover the whole database.
Semi-discrete OT The theoretical results of the present paper rely heavily on concepts related to semi- discrete OT, that is, OT between an absolutely continuous distribution and a discrete distribution v supported on a finite set. The connection between semi-discrele OT and a concave optimization problem is originally made in Aurenhammer et al. (998). Many numerical solutions have been proposed to solve semi- discrete OT, see Kitagawa et al. (2017) and references therein. From these works, we will use the concepts of Laguerre diagram (illustrated in Fig. 2 and c-transforms of functions defined on a finite set. The concept of c-transform is also central in the construction of the benchmark of (Korotin et al., 2022), where the so-called "MinFumnel" functions can be seen, for c(x,y) = |z (--y/ yll, c- c-transforms attached to a set of discrete points, Finally, let us mention that Lei et al.] (2019) studied some connections between WGAN learning and several formulations of the semi-discrete OT problem, recalling its equivalence with other well-known problems from convex geometry. In this perspective, the present paper provides new insights on the connection between the WGAN and OT problems, which pursue the observations formulated in (Genevay et al., 2017).
1.2 Contributions and outline
The main purpose of this paper is to propose a complete set of hypotheses that ensure the validity of the gradient formula referred to as equation (8) above and (Grad-OT) in a more general form below. Our approach is not restricted to the cost c(x, v) = || - yll related to the 1-Wasserstein distance. involves weak regularity hypotheses on the cost (called z-regularity as introduced in Definition [ below) and the generator (Definition 3). Based on this gradient formula, we consider a stochastic algorithm for learning a generative model that can be understood as alternating optimization algorithm on the semi-dual cost (6)
The main contributions of this paper are the following ones.
In Section 2 we recall the WGAN learning framework, and in particular necessary existing results on the dual formulations of OT costs. Then we provide a counterexample (Proposition 2 that illustrates how (raddOTT can fail for unrogularized OT when a technical hypothosis is not met.
Section 3 focuses on the gradient formula Grad-OT) in the case of unregularized (A = 0) semi- discrete OT (i.e. when v is discreto). We first prove the formula for z-regular costs (Theorem 3 and extend it to less regular costs (Theorem 4 Both these results are based on a tochnical assumption that for any 0, no does not charge particular subset called the Laguerre interface.
4

---

Published in Transactions on Machine Learning Research (MM/YYYY)
In Section 4 extend the gradient formula to the case of entropy-regulartzed OT, proving (Grad-OT) for z-regular costs (Theorem 5 with no assumption v. We also adapt this result for the differentiation of the Sinkhorn divergence (Theorem 6p.
In Section [ we illustrate the behavior of the alternating optimization algorithm for generative model learning. First, with the toy example of Proposition 2 cramine the trajectory of the optimization algorithm, and explain why it does not get trapped in a singular point with no gradient. Second, for various synthetic cases in dimension 2, we exhibit that the alternating algorithm generally stabilizes, but may also oscillate or converge to sub-optimal configurations, depending on the choice of gradicnt step size strategies. Third, we consider the learning of a WGAN for MNIST digits generation. In this high-dimensional case, we examine the stability of the loss function, and underline the impact of the entropic regularization both on numerical and visual results.
We emphasize that the theorems cnsuring (Grad-OT) are based on weak regularity assumptions for the cost and the generator that can be met in practice. Our regularity hypotheses are for instance true with the quadratic cost c(r,y) = ||~ - y/2² and with generators given as neural networks with 8 activation functions. Also, in the case of unregularized OT, the technical hypothesis is true except for degenerate positioning of the support of μag. Therefore, our results apply to most practical cases of WGAN training, and explain why the algorithms for WGAN learning generally do not get caught in singular points with inexisting gradients.
2 The Wasserstein GAN Problem
In this section, introduce in Section 2.1 the primal, dual and semi-dual formulations of the OT cost. The OT problem is presented in the general case including entropic regularization with parameter À 2 0, thus encompassing the unregularized case x == 0. 0. Next, we introduce in Section 2.2 the generative learning problem as well as the regularity hypothesis on the generator, which will be used to show the existence of gradients of the OT cost with respect to In Section 2.3 we finally present a counter-example of measures Pg and for which the gradient formula (8) does not hold.
First, let give some notations that used in the whole paper. Tet N, be compact subsets of Rd. and let e: X x y + R be a continuous function. Let @ be an open subset of IR used to parameterize the generator go- We say that yp : X + R is 81 X' if it is 61 an open neighborhood of X.
Definition (d-regularity). We say that is x-rrgular if there is L > 0 and an open set U with X C U C C such that for any y E y, v) can be extended to a L--Lipschitz 61 function on U.
We illustrate this definition with the cost c(x, v) || ull on Rd, with p 2 1. For p 1, is smooth function on Rd x Rd and thus æ-regular, as V,c is continuous function on Ed RR that is bounded on U x y for any bounded open set U containing X. For = 1, the cost c(x, y) = | is not x-regular as soon as X' and y are not disjoint. Indeod, for a fixed y E V, x + || yl is not differentiable at y.
2.1 Optimal Transport, Primal and Dual Problems
Definition 2 (Primal formulation). Let pr, v be two probability measures on X, respectively. For X > 0, the regularized optimal trunsport cost is desined by
[ xxxy
W v)
inf *EIl(H.))
dr + XKL(TT/
(9)
where I(H, ) is the set of probability distributions on X y with marginals μ and v, and where KL ( (T(()))V) dn ) dd if π admits a density dy@v w.r.t. a & v and +oo otherwise. apso
f log(
dx
Theorem 1 (Dual formulation (Santambogioo, holds in the sense that
2015
Genevay
2019
Feydy et al. 2019 Strong duality
max (E / ((x)dd(())+ + ((o)dd(s) - mm mx(((x) + v(v) c(x, v) (p())du()) (10)
W W)(,v))
5

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where, for À x= 0, mo(t) 0 if O, and - oo otherwise, and for >> O, m)(t) Mee - A solution 1h) (v,,h)) of this dual problem is called a pair of Kantorovich potentäals. When X > 0, the solutions are uniquely to an additive constant (i.e. if (F,,4) is a solution, then any solution can be written (g - k. Φ + k) with E R). Also, when x > 0, the primal problem admits a unique solution
(ye,
defined almost everywhere
dr(r, v) = exp (p(x) + (v)) c(x.,)) dp(x))duly)
(11)
A
If À = 0 the primal solution æ of (9) may not be absolutely contimuous w.r.t. @ v anymore. Nevertheless, under weak assumptions (e.g. n,, v admit second-order moments and ju is absolutely continuous), one can show (Santambrogio 2015) that the support of is actually supported on the graph of an optimal transport map T", i.c. the optimal is the probability distribution of (X, (X,T" (X)) where X has distribution j and (X) has distribution
For & E (()), let us define the regularized c-transform as in Feydy et al. 2019
Vz X.
w (z) = softmin c(2, v) - vp())
(12)
yEY
where the softmin operation is defined as
min u(y)
if X 0,
yEy
softmin u(y) yEy
/ e -
(13)
-Alog
x0-xx dv(y) if X
We also define the analoguous operators for the v-variable. It must be noted that the regularized c-transform Rea also depends on v even if y is omitted in the notation.
Given a pair of dual variables (4e, v) E (X) x ()), one can see that taking c-transforms
aod
(14)
leads to new pair ()) of dual variables that have better dual cost (10) than (q. v). Thus the dual problem can be restricted to e-concave functions, i.e. functions that write as c-transforms. Such e-concave functions inherits regularity from the cost function (see Appendix C and can be extrapolated to any a E X.
Theorem 2 (Semi-dual formulation (Genevay 2019 ). The dual problem problem
10 is equivalent to the semi-dual
/ (o)(x)))()))) f (y))du(y).
W)(u,v) sup w
(15)
A solution &b of the semi-dual problem is called a Kantorovich potential. In other words, vp is Kantorovich potential if and only if (1)222 vb) is pair of Kantorovich potentials. By symmetry, can also formulate semi-dual problem the dual variable sp.
2.2 Learning Generative Network
Estimating Wasserstein generative adversarial network (WGAN) from an empirical data distribution v consists in minimizing
(x) Wx(He,v),
(16)
where the generated distribution is assumed to be the distribution of go (Z), with Z a random variable.
Denoting by { the probability distribution Z on the measurable space Z, μg is the image measure of < by the generator ga, also known as the pushforward 14 = gotC. More precisely, the notation Oo refers to g(f,)) where g + Z Rd is function defined on the product of the open θ C R2 with Z. In the following, we give different sets of conditions on g that allow to compute the derivatives of hx-

---

Published in Transactions on Machine Learning Research (MM/YYYY)
All the results of this paper are related to the behavior of the function
1(0,0) = J odwo, ( 0 0 E),,
(17)
which allows to reformulate the semi-dual expression of optimal transport
15 as
I( 0) / vdv. (EE
(0) max
(18)
In order to study the gradient of hx, we define Fx: x + R with
V& (O))) O, Fx(2,0) I(bod 1/L jjaiApa Elb ( (2)],,
(19)
where the expectation is taken with respect to the probability distribution of Z. Combining all previous definitions, the problem we tackle writes
Wx(uo; v) h0) max Hx(1s, 0) Fx(1,0)+ + / wblue (EB())
(20)
and our objective is to study the relationship between (h) and VoFa 0). In the unrogularized case, we use simpler notations, h, W, H, and F for ho, Wo. Ho and Fg respectively, dropping the index
As we will see later, computing the derivatives of hy boils down to differentiating under the max, which is allowed by the so-called envelope thcorem. This result appears under different forms in the literature (Oyamal & Takenawa 2018). In Appendix D we recall the version of the envelope theorem that is used in our proofs.
If we admit the differentiability of all terms, the computation of the gradient is straightforward: Proposition 1. Let On and vo satisfying hx (0o) = Hx (o). hy and 0 + Fx(vo, 0) are both differentiable at G,. then
(hx( = V VeFi(eto 0o).
(Grad-OT)
Proof. First, notice that - and -V differ by constant, and thus have same gradients. Us- ing (18, hx(0) >> HA(vo, 0) for any 0 with equality if 0 = 0.. Therefore, the function 0 + hx(0) - HA 0) has a minimum at = Oo, and its gradient at On vanishes, so that (O)) = VoHla 0o).
However, showing the existence of (aFx(Vo, 0o) is not straightforward, one has to differentiate under the expectation in 19 To this end, we introduce the following technical hypothesis.
Definition 3 (Hypothesis (Go)). For 0o O, we say that g: θ x Z + X satisfies Hypothesis (Go,) if there crists neighborhood V of 0o and K E (S) such that almost surely f + g( Z) is 8 on V with differential 0 + Dag(0, Z) and
VO V C-a.8. 11 2) - g(0. 2)1l & K(Z) - 0oll-
(21)
We say that satisfies Hypothesis (Ge) i satisfies Hypothesis (Goo) for any 0g E O.
A sufficient condition for Hypothesis (Ge) is that almost surely, 0 + g(0, Z) is E6 on O and that there exists
K e (C) such that
00 E Ç-a.s. lg((0', 2) g(0, Z) < K(Z) - 0||
(22)
Hypothesis (Go) is also satisfied as soon as g is E1 on θ x E with 2 C R compact. In this case, for any 0g E θ, there r > 0 such that V = B(Og, r) is included in e and then (11 holds with the constant bound K supex [Dag]]- This is the case when g parameterized by a neural network with 8 activation functions, and with an input noise supported on a bounded subset of R² (e.g. Z uniform on 1]*). In Appendix A we show that Hepothesis (Go) is satisfied in more general setting with integrable noise.
7

---

Published in Transactions on Machine Learning Research (MM/YYN)
2.3 A telling counter-example
We now show that the differentiation with respect to 0 under the max in 188 can fail, even for regular generators 9, thus discarding the formula. [Grad-OTy. To illustrate this point, let us consider simple unregularized OT problem (i.e. À = 0) between a Dirac óg located at E IR and a sum of two Diracs at positions y1 * y/ E R This setting can be obtained by setting go(2) (for any distribution Z).
Proposition 2. Let bg and = y + 2220..
For 2 1, consider the cost c(r.y) y) = || yll where ||.11 is the Euclidean norm on Rd. Then
h(0) W (We, v) is differentiable at any 0 & (ui 223 for p 1, and at any 0 for > 1, for any w/w E arg m H1,, 0o), the function 0 + F(1lo, 0) is not differentiable at 8g-
Hence relation
Grad-OT never stands.
Proof. The only distribution on X x y having marginals μea v/ is क = to(0.0 + (d Therefore, recalling that h(0) = (( v) and from the definition of the primal problem
( we have
1 h()) 2 p0 v1)
1
2 c0 y2)
(23)
which gives the first point.
Next, one can explicitly solve the dual problem, which, from the equivalent semi-dual formulation
15 and
the definition 19 of F, reduces to the following optimization problem with respect to (+b(1), (v2) E R
max (bb,0) 0) with H(b,0) = (0) + ((11) + v1122)
(24)
WER²
2
where, for any v. the e- c-transform
13
writes
[((0,v) m1) (11) if v1) - v(n) < c(0,92) - (122))
(0)
(25)
c(0,, 12) (g22 otherwise.
Therefore,
(vb0) = c((0,))) (V((2) v((1)) if (12) - -(r)) & <c00,)))
((0,11),
(26)
c(0, y2) (v((2) (b(1)) otherwise.
For a fixed b, (0, is maximal at any ei.o such that
( - (=o(vi) = c(fo.z2) c(fu, 81).
(27)
Besides, from 266 one sees that (1b,)) :) is made of two pieces whose gradients can be computed explicitly for the cost c(zz v) = ||æ "l
Vθ + y/
V =z0(0, yU) pl1 yソ 20 4/).
(28)
and, when p > 1 we also have v, v₁) 0 for 0 yj- Therefore, illustrated on Fig. the gradients of the two picces agree at no point 0: for any 0 V.c(f. vn) + v.c(0. In particular, the function H is
- v1) v(12) ((r1) }. As F(b,-) only differs from (w,,) :) by the constant p(n)) it is also not differentiable on Ag. But then, for tho satisfying (27) 2 to lies on the interface Ag... which gives the second point. Fig. thus highlights the main pitfall in the proof: the measure dg puts some mass thin subset where + F (w 0) is not smooth.
not differentiable at the interface Ag = { E Rd
8

---

Published in Transactions on Machine Learning Research (MM/YYX)
V1
Figure 1: Counter-example for the gradient formula. This diagram illustrates the counter-example
Proposition 2 for p The notations used in this diagram are detailed in the proof. The function - (vboo, 0) is drawn in blue background. For the optimal d.o corresponding to Ou, the function 0 + H (1h.o 0) is not differentiable on the interface Apwor where On lies.
H H(p....0 0)
V H (1--0. 0)
A App
0
1
Y2
For the same example, we show in Appendix B that relation (Grad-OT) holds with regularized OT only in the case p > This illustrates the need for a regularity hypothesis on the cost, even for regularized OT.
This counterexample can be extended to other situations where the measure pa is not supported on single point. For example, for the same V, the gradient issue still happens if Me is the distribution of 0 Zu where Z is uniform random variable on [-1,1] and where E Rd is orthogonal to Y1 (Mp is the uniform distribution on segment orthogonal to [-1, 1] centred at 0). In the following section, we adopt an hypothesis on the generator to avoid this objection.
3 Gradient formula in the unregularized semi-discrete setting
In this section, we prove the formula Grad-OT] in the semi-discrete case, iee. when the target measure v is supported on a finite set of points. We only consider the unregularized case À and recall that the index A is dropped in this setting, with the notations W Wo, == ha, and F Fo respectively defined by (9) 16 and 19 More general results are given for regularized OT in the next. section.
Our analysis builds concepts related to semi-discrete OT (Aurenhammer et al. 1998
Kitagawa et al.
2017), and in particular to the notion of Laguerre diagram presented in Section 3.1 In Section 3.2 the Laguerre diagram is used to formulate a condition on the generator ge which allows the computation the gradient of h, by differentiating under the max in 20
In the studied semi-discrete case, X' C Rd is compact and y is finile with points, so that &D)) identifies Rd We recall that the objective to show that Vh(-) FaF(b, so we study the function F: : x + E
F 0) / d = E El [))]
(29)
3.1 The Laguerre diagram and the semi-discrete transport maps
In this section, we recall the definitions of transport maps and Laguerre diagrams which are used in semi- discrete OT Aurenhammer et al. (1998); Kitagawa et al. (2017). We also give two lemmas in order to compute the gradient of c-transform functions. To any sb E R we associate a Laguerre diagram, which is a collection (Ly (w))mey of Laguerre cells defined by
(y) x Vy EV fub. c(x,y) 4(v) c(x.)) v051) }.
(30)
We also define the Laguerre interface by
A X U Lo))). yEy
(31)
which corresponds to the set of points for which there is a "tie" in the minimum defining (x). For example, if c(x, 1/) = ||a- 1 in Idd, Av contained in union of hyperplancs whose directions are orthogonal to the segments [y1, y2l. y1, U2 E V. In particular Ay has zero Lebesgue measure, and thus the Laguerre diagram form partition I&d up to negligible set.
9

---

Published in Transactions on Machine Learning Research (MM/YYYY)
By construction, for z E X' Ap, we can uniquely define the transport map
(x) = arg min c(r, v) - (b()).
(32)
NEY
If y a probability measure on X, one can verify that for any s R. Te an optimal transport map between a and Teīu. Conversely, μ is absolutely continuous on X, solving the OT problem from μ v is equivalent to find vp E TR such that Twin= v. We refer to Fig. for illustration of Laguerre diagram and semi-discrete transport maps; and to Kitagawa al. (017 for more details.
The two following lemmas will be useful to study the regularity of F and h. Lemma 1. The map (1b, x) + (x) is locally constant on R' Ap.
Proof. Let ())x) RR Av and let y = (x). By definition of Laguerre cells,
c(z, y) ((y) min (c(z,2) ()2)) 0. =Ev(it>
(33)
The left-hand side is function that jointly continuous in (v), x) and is < 0 at (v) Thus, there is a neighborhood W of (1) where it stays negative, that is,
V(d' w. c(z'.v) +'(y) min (c(x' (z)) < 0. =EVi(u)
(34)
Therefore (x') = on W.
Lemma 2. Assume that y is finite with J points and that is x-regular (see Definition Then d is '6' on X \ Ag and
Let ab E R
Vx Ag, Vel(x)= Vac(x,Tx(x)))
(35)
Proof. First, one can notice that x AA U Ly(y) is an open subset of X' because the Laguerre cells Lv(
yEY
are open (thanks to the continuity of c). Besides, if x E X' \ Ag, y = [T)( is well-defined and x E (y)
Thus Lp (y) is an open neighborhood of x on which we have
Vu (y), (u) = c(u,y) vby))
Therefore, on Lg (v), v0t is as regular as cl.,)) cl, (x)) and has the same gradicnt.
(y)
Ay
Voronoi diagram
Laguerre diagram
Figure 2: Laguerre diagram and semi-discrete transport maps. We display here two colored partitions corresponding to Laguerre diagrams associated to a set y with 6 points (drawn in dark blue), and with the quadratic cost c(2, y) = ||x - y/ on [o, 1|2. On the left we display the Laguerre diagram for e = 0, which corresponds to the classical Voronoi diagram. On the right we display the Laguerre diagram for a specific value of v.. The map To drawn as blue arrows. We also display in yellow the Laguerre interface Ag. Notice that, for Laguerre diagram, a point y does not necessarily belong to its Laguerre cell Lz()).
10

---

Published in Transactions on Machine Learning Research (MM/YYY)
3.2 Gradient of the unregularized Wasserstein loss function
We now state our main theorem for unregularized OT. To this end, we first analyse the regularity of F. Lemma 3 (Regularity of F). Assume that y is finite with J points and that is x-regular. Assume that g satisfies Hypothesis (Gog) (Definition 3) at some Op E ④. Assume that for any E R p0, (Ap) 0, i.c. g(0, 2) E E \ Ag almost surely. Then, for any v0 E ER, 0 + F(,,0) is differentiable at 0o and, denoting as Dog the portial differential of g with respect to 0, we have
FoF(W,O)) = (00 Z) (g(0,, 7))]-
(36)
Proof. Let V be the neighborhood of 0n given by Definition 3
For E O let us denole
f(1,,, 0, 2) = 2 (o(0,2))
(37)
so that we get F(V, 0) = E{ 0, 2)] from 29
The hypotheses on and Lemma 2 ensure that f(b,
7)
is almost surely differentiable at 0g and thanks to the chain-rule, we have
Vol(v, 0o: Z) = Dog(Oo, z)J Vi (g(o,, Z)).
(38)
Besides, since e is æ-regular, the e-transforms are L-Lipschitz thanks to Definition and Lemma 6 given Appendix Therefore, for any 0 E V,
1f(1,0,2) f(1,)) Go Z)I < Ll]g(0, Z) g(0. Z) < LK Bull a.s.
(39)
Next, replacing 0 by 8 t(0 0u) for t e R and letting t + O, we also get
|Vof(v, 8, Z). 6o)l < LK ||) Poll a.s.
(40)
In particular, E 0o Z exists. Therefore, we have for any = V,
0, Z) f(v, 8, Z) Vof(v, 0, Z) Oo)l (LK(Z)) a.s.
(41)
|0 -ool
When 0 > Go, the left-hand-side tends almost surely to zero, and thus, the dominated convergence theorem ensures that
[f 0, 2) f(b, 0, Z)
Vof(w, On 2).(0 - 0o)l
E
(42)
00 10-l
and in particular,
F(b, 0) F( 06) EVVof(,, 0u, 2)1.(0 - 0,) -0(10-6o1l). 0.ll)-
(43)
This proves that F(b,.)) ) is differentiable at d, with
VoF(b, = E[Vaf(V, Co Z)] = EiDag(O. 2) V (go (2))
(44)
Theorem 3. Assume that y is fonile with J points and that e. is x-regular. Also assume that.
1. for any 0 E 0, the Kanlorovich polential th. for W W(ua, v) (defined in Theorem is unique up to additive constants.
for any E O and any TR. (A((A)) = i.e. we have g(0, 7) X \ Av a.s.
3. g satisfies Hypothesis (Go) in Definition
Then h0)) W(Ha, v) is differentiable at any 0 θ and
( Vh(0) = VoF T.. [Dog(0, 2) (V((go(2)))
(45)
11

---

Published in Transactions on Machine Learning Research (MM/YYY)
Proof. The proof consists in applying the envelope Theorem (recalled in Appendix D to show that h is differentiable at fixed On E e. Let us denote by tho the corresponding Kantorovich potential for W W(u,:" v).
First, we need to build a selection of Kantorovich potentials that is continuous at 0o. Since we assumed that for any 0 E V, the Kantorovich potential for W W(pg, v) is unique up to additive constants, there is a unique tho E arg max F(: () such that (1)(()) = 0, where y1 is an arbitrary point in V. The continuity of + 1h.0 then follows from Lemma - given in Appendix C and the fact that 0 + μi is weak continuous at 0g. Indeed, Hypothesis 3 implies that when 0 - 8,, gv (Z) 9m. (Z)ll] + O, which means that go(Z) 9oo (Z) in L' (S, and thus in distribution.
Lemma 3 then ensures that VoF(V,0) 0) exists in the neighborhood of (v..,
Finally, we have to demonstrate that (v. H F (e), 0) is continuous at (tivo, fo). For that, we show that
the function f(b,, 0, Z) introduced Equation 37 has a simple expression in the neighborhood of (vh.o: 6o).
Indeed, for Ç-almost all 2, we can define y To. (ge, (2)). Lemma | gives a neighborhood W1 W2 of
(1h.o: 96, (=)) where To y. By continuity of g) U Wi [g(( ((W2)) is neighborhood of (1hoo 0o) such that V(th, 0) U. (e(o(2)) y. Thus,
V(,,0) EU, vof(v,,, Dog(00, V Dog(O, =)"V v=c((o()))))
(46)
In the neighborhood U, the right-hand side does not depend &e anymore. It is also continuous in 0 thanks to Hypothesis (Ge) and the fact that is z-regular. This proves that almost surely Vol(:, 2) is continuous at (aboo, 9o). Finally, Equation $40p proves that all components of Vef(.,-, 2) are almost surely bounded by LK(Z)= E L' (C). Therefore, the dominated convergence theorem ensures that F 0) = of,, 8, Z)] is continuous at (1)
We can thus apply the envelope Theorem 7 which gives the desired result.
The hypothesis that is z-regular (see Definition D may not be satisfied for some specific costs, like c(xr, y) = ||- in Rd, which is related the I-Wasserstein distance. We now give a similar result with a relaxed hypothesis that encompasses such non-smooth cost functions.
Theorem 4. Assume that y is finile with J points. Assume that c : X y + R is continuous, and that there is constent L > O, open set U with X c U C. Rd and set B C X closed in Rd such that for any y E V, c(:,y) can be extended to L--ippschitz '6' function on U \ B. Assume that g satisfies the three
assumptions of Theorem 3 and assume also that (B( = 0 for any A E e.
Then (00) = (Ju,, v) is differentiable at any 0 E θ with the gradient expression
45
In the case of the Euclidean distance c(x, y) = || - yll in R4, for any y E y, c(:.)) is 66' only on Rd (v}- Thus this cost satisfies the condition the last theorem with B = V, and the resulting hypothesis on the generator reads as ())))= = 0, in addition to the fact that the Laguerre interface As po-negligible.
Proof. One may check that the main parts of the proof given for Theorem 3 are still true with the relaxed hypothesis on the cost. We only highlight the minor modifications. First, in Lemma 2 one obtains that the c-transforms di are only Te on X \ (Ap U B). The proof of Lemma 3 is unchanged because go (Z) almost surely belongs (o X') (As BB where the c-transforms are differentiable. Finally, in the last step of the proof of Theorem 3 the neighborhood W, x W2 has to be replaced by W1 x W2 n B
4 Gradient formula for regularized optimal transport
In this section, we show the gradient formula Grad-OTT in the case of regularized optimal transport. With regularized OT, as soon as the cost is regular, the regularized c-transforms are also regular everywhere (see Lemma 6 in Appendix Cp. Hence no assumption are required on the target measure v, and the study is not restricted to the remi-discrete setting.
We recall the notations Wx, h2, and Fx from 16 and 19 In order to obtain the gradient of h2, we follow a similar strategy than in Section 3 and study the relation between (0) and Fx 0). We first
12

---

ulv)- Published in Transactions on Machine Learning Research (MM/YYY)
show the gradient formula for the unregularized Wasserstein loss function in Section 4.1 and then extend this result for Sinkhorn divergences in Section 4.2
4.1 Gradient of the loss with entropic regularization
We first recall result from Genevay et al. 2019 proof for further use.
the gradient of regularized o-transforms and detail its
Lemma 4 (Gradient of regularized c-transforms Genevay et al. (2019)) ) Let A > 0. Assume that is x-regular (see Definilion 1. Let w E ())).. Then U. is E on X and
EX (x) = / exp
(x) + (v) c(a,y) A
Vzclor v)de(y)
(47)
y
fy exp
(()))(())))) V VaclE, v)dv(()
(48)
Jy exp
((M) c(a. du(y)
Proof. By definition of the regularized c-transform (see relations
12 and
13 1 we have for any a E X,
((a)-c(r.)) dy(y).
Ve E X,
(49)
Since e is z-regular, then for any y E V, x. + e x with Lipschitz constant I exp( |lelle
is 86 on a neighborhood of X, and it is Lipschitz Therefore, we can differentiate under the integral to get
Ve E X, V. (e- -
(e-
- Vx y)e ((0)-c(r.))
dv()).
(50)
Expanding the lent-hand side, this is equivalent to
/ V V. y)e Maahellaai dv(y).
V X, (a)a
(51)
which gives the desired formula 47 for Vela. The second expression 48 follows from using the definition of viad again. Finally, using 48 one can see that all integrated functions are continuous with respect to x, and bounded. The dominated convergence theorem thus ensures that Viged continuous.
We now look the differentiation of Fx before showing the gradient formula (Grad-OT] Lemma 5 (Regularity of Fx). Let > 0. Assume that e is x-regular and that g salisfies Hypothesis (Ge) (Definition Let vp (D)). Then the function 0 Fx(1, 0) differentiable on O and
vO, E O
VeFx(e, 0o) = E [Deg(00. 2) ( 2))]
(52)
Proof. As in the proof of Lemma 3
let us introduce
fa 0, 2) = (go (2))
(33)
so that (xb,, 0) R[SA (w), 0, 2)). Using Hypothesis (Ge) and Lemma fa(b, 2) is differentiable on almost surely, and, thanks to the chain-rule,
Vafx(v. z) Dog(O, (
(54)
Besides, the regularized c-transforms of a z-regular cost being still L-Lipschitz (by Lemma 6 in Appendix we have an integrable bound for the finite differences of fx- Indeed, for a fixed fg E +, and for any 0 in the neighborhood V of 0 given by Hypothesis (Go,); we have
|1,,,, [x 0o 2) & Tl]g(0, 2) g(0,, 2)1l & LK(Z)) 0oll
(55)
13

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The proof can then be ended as the one of Lemma 3 For further use, notice that the previous bound implics
vOp O Vo 0o, Z)ll Dog((e, Z)= ( Z))l| < LK(Z)
(56)
where IIIIII is the dual norm associated with || ||-
Theorem 5. Assume that e is x-regular and that g satisfies Hypothesis (Ga). Then hx is Et on O and
40 O (0) VoFx(e.. 0) E [Dag(0, 2) V v (9(0, [))]
(57)
where th, arg m H2 (1, 0), and where V is given by 47
Proof. As in Theorem 3 the proof is based on the envelope Theorem given in Appendix D applied
(0) = WX(Po, v) = max Hx 0) (sce (18) and (20)). With entropic regularization, the uniqueness (up to additive constants) of the solutions of the dual problem provides a continuous selection of Kantorovich
[ ensures that V&Fx exists for any t/ E 80)) and any 0 E O. It remains to show that VoF is continuous in (v,, 0). For that, recall that VoFx(V. B) E[Vofx(V, (1p, 0, Z)] where fx is defined in (53). and let us fix dg
potentials, thanks to Lemma [ in Appendix C Besides, Lemma
and dlxo an optimal
Kantorovich potential for Wx(ua, U), and let also vp E 8 ()) be arbitrary. Then, for any 0 in the neighborhood V of 8o given by Hypothesis (Ge,).
( Z) fx Po, Z)I & L)) g(0,,
& (K(Z)) Poll
(58)
which ensures that all components of Vofa(V: Z) are almost surcly bounded by (Z( an integrable bound which does not depend on (v, 0). Since A + g(0, Z) is almost surely 86 on V. using 54 the last is almost surely continuous.
step is to show that (1) > Vilei (go
Let us fix 2 E Z for which g( 2) is 6 on V and for which Hypothesis (Go) 21 holds. From
51 we have
(g0~) = (o0())))))) / V=c(go(z). wwn -ta-)tta0))).))
du(y).
(59)
For the first term, if v and 0, E
(o0=)))) - (x)) < (g)=((9(2)) (or + (xxx))
(60)
< [lgo(=) 9-(()] + 1/yb 11
(61)
< LK(2)]10 -ll + 1| - x1100
(62)
C and thus (v, 0) + (gg(t)) is continuous. For the integral term, + Vzc(go(z),)) y) is continuous on because e is æ-regular and because f + g(f, 2) is continuous on V. Additionally, (vh, 0) + ((g))))))()).))
by virtue of Lemma 7 given in Appendix
is a separable product of two terms which are continuous in & and respectively. Finally, if eb restricted in a neighborhood Po of &4-0 bounded by R 0, then all terms under the integral are bounded by Le
Again, the dominated convergence theorem implics that (w,0)~ + (g)=)))(=)) is continuous on Po x V. Finally, using the bound (56) and the dominated convergence theorem gives that (v) + F 0) is contimuous on Po x V. Therefore, all required conditions are satisfied to apply the envelope theorem on Fx,, which gives the desired formula.
4.2 Gradient of the Sinkhorn divergence
We here assume that X' = V, that the cost (x, + c(z, is '6' on X' x X and symmetric (i.e. c(x,y) = cly,,) Φ)) for all x, y E X) and that it is L-Lipschitz with respect to (x,y):
V(,,)), v/) E X X, X, le(x, v) - c(x', (/,,1/)) < M[Ix - x'll + ll v/l).
(63)
Genevay el al. (2018) and Feydy et al. 2019h have shown that learning a generative model based on the Wasserstein cost Wx induces a bias. For this reason, they propose to use instead the so-called Sinkhorn divergence definod as
Sx(ux)) Wa(H.v) 1 - (Ww(m))) + Walu.v)).
(64)
14

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Since we focus here on the regularized WGAN learning problem, we study the function
1 (0 = Sx(1,, v) = Wa(Ho.v) - 2 (a) Wx(K,
(65)
and we extend the previous regularity results to this new criterion. The first term of 655 has already been studied, and the last. term does not depend on 0. It thus remains to study the middle term. To this end, we rely on the dual formulation of (N(ee po) given by
/ xdua+ +
/ ndpo
J xxxx
X (pp(z))ppo()) + X. (66)
W (x(Mo
max Fx(x. .) = (x)
The problem 666 can be restricted to functions which are regularized c-transforms with respect to 14g. Similar to Lemma 5 one can show that such regularized o-transforms are still 6 on X and that the gradient can be computed by differentiating under the integral. Besides, because of the symmetry of Wx po), one can show that the couple of optimal potentials (x,,)-) that solve (66) is such that X+ and h), are equal up to additive constant. Based on these observations, we can now state the regularity result for the Sinkhorn divergence. Recall that notations I, Fx are defined in 117 and 19
Theorem 6. Assume that is rr-regular and that g satisfies Hypothesis (Go). Then 8n is 86 O and 4A O Vos = (os: 0) VoI(x.,)) = (o 2) (VW5~ 2)) (x())(02))))] (67)
where vh E arg max, Fx 8) and (x., 17.) E arg max Fx(x.1,0)
The proof is postponed to Appendix
5 Experiments
The goal of this section is to provide a practical analysis of the proposed approach for learning a generative model by means of the regularized optimal transport framework. More preciscly, we aim at examining the impact of the regularization parameter and the choice of parameterization for the dual variable of the corresponding optimization problem. We first provide in Section 5.1 an alternating algorithm that tackles the minimization of (16) for learning a generator from a dataset. In Section 5.2 we apply this algorithm to synthetic datasets with few number of points in dimension 2. This helps to understand and explain the
possible trajectories of the alternating algorithm. Then we consider in Section 5.3 the MNIST dataset (LeCun)
et al. 1998 composed of 60000 digits in dimension 784.
5.1 Alternating Algorithm
In the semi-discrete setting, ) is a finite set of data points, and elements vb E ())) identifies to vectors in R as in Section 3 On the other hand, pe is the output distribution of generative network, which can be sampled demand. We thus aim at solving the optimization problem
min (0) min max HA 0) = / wo dpo + / vddu Fx(1,0) Σ (())((())) lee
(68)
dEe vEE()
NEY
We adopt an algorithm that alternates between updating 0 with one gradient step, and updating & with several iterations of dedicated algorithm.
45 and 57 computing the gradient of ly requires optimal dual potential 4p- v.A In general, we only have access to approximation of p... Tn our work, rely the stochastic algorithm for semi-discrete OT proposed in (Genevay et al. 2016) to approximate the optimal potential. We recall that from the notation in the proof of Lemma have
As shown in main theorems (see relations
Fx (vb, 0) E[fx Z))
(69)
15

---

Published in Transactions on Machine Learning Research (MM/YYY)
where fi(t) 0, = e (g) It has been shown in (Genevay et al, 2016
Houdard et al. 2023 that 1/, 0) = 02. H 0) can be written as
Hx(,0) defined in 68 is concave function whose supergradient D(1),
D(v (e) 0, Z] where 0)) = d2 (f((v.02)) - ff vidv
(70)
This element. Div,, 2) E TR'' can be computed with an explicit formula given in (Genevay et al. Houdard et al. 2023). It is in practice implemented by automatic differentiation.
2016
Therefore, for a current 0, we can optimize & with a stochastic supergradient ascent (for which we adopt the common referencing ASGD for averaged stochastic gradient descent)
v/x = vx- +
7 1
1 EeEn, 0(1x-1,0,2)) BN
(71)
1/4 = (v22 +.... +2k).
where 7 >> 0 is the learning rate, a E (0, 1), Ba is a batch containing b independent samples of the distribution of Z, and the different batches Ba's are also independent. In ASGD, the variable th can be initialized at 0 (cold start), or alternately at the value of & obtained by ASGD for the previous A (warm start). As recalled in (Genevay et al.) 2016) and (Galerne et al. 2018), for a = 0.5, the ASGD algorithm has a convergence guarantee in ( ( on the function values. After K iterations of the inner loop, we obtain an approximation s of the optimal dual potential v., for Wx v), and use it to perform the gradient descent step on 0
vE
Vohx(0)= = (oHA(#,0) Fo 0) = E Dooo(, Z)" (g 2))
(72)
Using VOH 0) a proxy for (o) in the gradient descent step be interpreted an alternating optimization Hx(1, 0), with inner loop on & at each iteration. As the expectation in 72 cannot be computed in closed form, we realize an approximation by taking another batch B' on 2 (drawn with distribution Q):
VoHi(
Σ =EB'
Dog(O, 2) V 2 ( 2))
(73)
B'
The overall method, summarized in Algorithm T can be interpreted as stochastic alternating optimization algorithm on fixed cost. Hx 0). This generalizes the related work of (Chen et al. 2019 which is restricted to unregularized OT X = 0. The stochastic gradient steps taken 1o and can be implemented by automatic differentiation on fixed cost Hl,, and the updates can be implemented with predefined optimizers. A neural network parameterization 4/2 of the variable vp can also be adopted as in (Seguy et al. 2018). The update of & then translates on an update of the neural network parameters 4, which can be done by backpropagating the gradient of t + fx(wr, 0, 2) - I vidv = (gx(() - Eyey (b(())((v)) through the differentiation of (v, 2) (go()) for a batch of z values. The exact computation of ai requires to visit all the dataset ), which is prohibitive for large databases. An alternative strategy is to work with batchwise version of the OT cost, but this introduces an estimation bias Fatras et al. (2020).
Algorithm Alternating algorithm to learn generative model μi Initialization: th = 0 and (randomly) For n= to N
Approximate Vn RS arg Ha(: 0): inner loop with K iterations of ASGD using supergradient 770 batches B,, of size b on = initialized at wh-1 (warm start) or at (cold start)
Update 8 with one step of ADAM algorithm on Hx(bm,)) using gradient 73 on a batch B', of size on 2
Output: estimated generative model parameters 0
5.2 Generator learning for Synthetic datasets
We examine the behavior of the alternating Algorithm for fitting a generative model a small 2D synthetic dataset (J 2 points in Section 5.2.1 and J 6 points in Section 5.2.2.. For each experiment, give
16

---

Published in Transactions on Machine Learning Research (MM/YYYY)
diagrams to illustrate the position of the dataset Y and the evolution of the support of μi along the iterations
n. of the main loop of the algorithm. The square support of these diagrams corresponds to [0, 1|2. The Laguerre diagram associated with a given & E RR' is drawn as a colored partition of [0, [0. On the right column of the figures, we display the evolution of the loss Hx 0). Since Hx 8) involves a po-integral, for plotting we always use a Monte-Carlo estimate obtained with a batch drawn from plg.
We use the quadratic cost c(z, y) = || - yll and the settings detailed in Appendix Algorithm [ the ADAM algorithm is used to update the model, which is often parametrized by a neural network, as done in the following with an MLP generator. However, when considering simpler models (dirac, disc and cllipse distributions that are explicitely paramctrized), we rely on stochastic gradicnt descent (SGD) a algorithm with fixed learning rate v = 0.2. In both cases, the dual variable v is optimized with the ASGD algorithm written in 71 with learning rate y and a cold start initialization. The number K of ASGD iterations is always fixed to K 100.
Note that in
5.2.1
2- 2-point dataset
We use the generative models detailed in Appendix F.1 for larget distribution & uniform on y -11, y2).
Dirac generator We first study the example of Proposition 2 and consider the Dirac generator Me 58. In this case, the gradient descent on 0 is actually deterministic. Besides, from the calculations of Section 2.3
we have that the global minimum of 1 (0)= = Wx v)) is reached at 0 - 11
Fig. 3 displays the results for the Dirac generator. It illustrates the position of the estimated Laguerre diagram along iterations. Let us recall that, as illustrated in Fig. [ for a fixed 0, the solution of the dual transportation problem makes the Laguerre interface go through B. This is not the case when using Algorithm D even in this deterministic setting. Hence the current. point O can get close to the Laguerre interface but it does not get caught by this interface. Indeed, with the chosen initialization of 0 and gradient strategies, the combination of gradient steps on sp and f has no reason to put the interface exactly on A.
In view of Proposition 2 it means that for a current 0, the ASGD on to does not reach the optimum vh in finite time. Hence the corresponding interface does not pass through and the algorithm does not get trapped in a point where the gradient of - Ho( f) does not exist. This illustrates that it is very unlikely to encounter the gradient problem highlighted in Proposition in real use cases. In contrast, the gradient problem appears when taking an optimal gradient step on s instcad of fixed step size. Indeed, with such a strategy, one iteration of v puts the interface exactly on 0, which prevents from computing the next gradient.
Fig. 3 exhibits four different behaviors of the alternating algorithm: without regularization (A = 0) in the three first rows, and with A = 0.1 in the last one. In the first row, the alternating algorithm stabilizes, but for a wrong reason: the learning rate y of ASGD is too small, and thus the interface will not get past 0. Therefore, / being always in the same Laguerre cell, the gradient descent on f makes the generator collapse to the corresponding data point yj, which is not even a local minimum of hx.
An opposite phenomenon appears in the second row, where Y is larger: case, because of the fixed number of iterations of the inner loop, ASGD always makes a non negligible error. This reflects in the position of the interface, which hardly get close to 0, and actually moves periodically on opposite sides of A. Thus, the point 0 is alternately pushed towards y/1 and y2, which corresponds to the oscillations in the evolution of the loss function. This example shows that, with a fixed step size strategy, the alternating algorithm may not converge in certain cases. Note that using decrcasing step, which is often used to mitigate oscillating behaviour during stochastic optimization, does not necessarily solve this issue. As illustrated in the third row, with carefully tuned gradient step strategy and smaller learning rates n7, the algorithm stabilizes around the optimal position 0.,, with slight oscillations.
the algorithm now oscillates. In this
Finally, for the regularized case shown in the fourth row, one can see that 0 quickly gets close to the global 122 Indeed, from the gradient formula 557. the Ve-descent direction points to a weighted average of y 0 and 1/2 0 at cach itcration, which helps to push / towards A,, One can observe that using the transported measure tue never solves the WGAN problem because would just copy y11 or y2 whereas the true solution de, realizes a compromise between all data points. The proposed alternating algorithm is
optimum 0, = 2
17

---

Published in Transactions on Machine Learning Research
A= 0
7= 0.05
0.
R
A= 0
? = 0.1
f = 0.2
d = 0.05
A= 0 2
0.1
1 0.2
Initialization = 5 Y1 10
20
Y1 30
n1 40
Loss
Figure 3: Generator learning for 2-point dataset y and Dirac generator dg. In the first columns, we display y (dark blue) and the current position of (light blue) along iterations n. The Laguerre dia- gram associated to the current value of b is displayed last column shows the evolution of the loss Hx along the iterates. For each line, the regularization parameter and the learning rates 7, for & and 0 are indicated the left. Depending the choice of parameters and gradient strategy, the alternating algorithm oscillate stabilize. See the text for additional comments.
the background with the colored partition. The
a relevant way to find this compromise, provided that its hyperparameters are carcfully tunod. Besides, this example illustrates that entropic regularization may help to reach this compromise faster, while introducing non negligible bias in the problem as explained in Genevay et al. (2018).
Disk generator We now consider the same data set y {ur y23 and a generator go inducing the uniform distribution μĄ (()(),r)) on the disk of center and of fixed radius r. In this case, μı is absolutely continuous w.r.t. the Lebesgue measure; thus the SGD 0 is truly stochastic. All hypotheses of Theorem 3 are satisfied in this setting, which validates the gradient formula (Grad-OT) for all values of tb and 6.
Different behaviors can nevertheless be observed with the alternating algorithm, as illustrated in Fig. which present experiments conducted with À = 0. If r is sufficiently small (rows and 2), the algorithm behaves as in the case of the Dirac generator: for large value y the algorithm can oscillate around the optimal $1 position 2 (row 1), and for low values of 7, it can make 0 collapse to one of the data point (row 2). In this latter case, the "cold start" initialization
0 actually explains the bad positioning of the interface.
With "warm start." " initialization of s (row 3), the estimated interface is indeed able to closely follow the position of 0. However, this amplifies the oscillations of 0, since the interface goes past 0 more often.
Note that the oscillatory behavior is redueed when the radius of the disk is increased (rows and 5). Indeed, if the disk is larger, the interface stays close to D(0,r) r) as soon as they intersect. This illustrates that a largely spread distribution Ωe make the alternating algorithm stabilize faster, even when starting from a purely random initialization (row 5).
Other generators We consider in Fig. one cllipse generator (1-ellipse, row 1), one "mixture of two ellipses" generator (2-ellipse, rows 3), and multilayer perceptron (MLP, rows 5). these experi- ments, the generated distribution tends to concentrate either on y or one-dimensional structure close
18

---

Published in Transactions on Machine Learning Research
y = 0.005
7 =
r = 0.000
7 - 0.01
? 000 (WS)
r = 1.0.000
= 0.00
7 7= =001
y 0.05
7 = 0.1
Initializatinn
10
20
30
40
Estimated Loss
Figure 4: Generator learning for 2-point dataset y and Disk generator centered at 0. Results are displayed using the same presentation as in Fig. 3 with samples from μe in light blue. For each line, the disk radius r and the learning rate 7 are indicated on the left. The regularization parameter here fixed to A =. 0. The last column shows the evolution of the estimated loss H 0) along the iterates. In the third line, we used a "warm start" (WS) initialization for vi each iteration, as opposed to 'cold start" in other cases (see Alg. 1.. Depending on the choice of paraneters and gradient strategy, the alternating algorithm may oscillate stabilize (possibly to sub-optimal configuration). See the text for additional comments.
to the line (V1, 32). The difference between first rows is worth noticing: if possible, the generator collapses on the data points in order to decrease the W cost. This is possible in the 2-ellipse case (rows 2, 3), but not in the 1-ellipse case (row 1). This illustrates that the choice of the generative model is important and that mode collapse cannot be only attributed the loss function, f.e. the W2 cost or regularized version.
5.2.2 6-point dataset, neural generator
We now consider a dataset y with points, and we fit a generative model parameterized by a multilayer perceptron (MI.)), whose parameters can be found in Appendix F.1 The results are displayed in Fig. t below, and Fig. 11 Fig. 12 of Appendix G On Fig. the estimated generative model concentrates on a shape, which is close to the data points for phenomenon is confirmed by the results of Fig. I and agrees with the fact that entropic regularization introduces non negligible bias in the WGAN fitting problem, as already highlighted by Genevay et al. (2018). Correcting this bias requires the use of the Sinkhorn divergence Sx instead of Wx- However, since the source measure absolutely continuous, estimating Sx without relying on batch approximation is not straightforward. For this reason, we do not address WGAN estimation with the Sinkhorn divergence.
while it degenerates to barycenter for larger X. This
In these experiments, the loss tends oscillate. Following Section 5.2.1 this behavior can be explained by the large number of parameters of the ML. associated to the fixed number of iterations K of the inner loop.
19

---

Published in Transactions on Machine Learning Research (MM (YYY)
1-ellisee
4-
17
-=
2-ellipse
A - 0.
A= 0
MLP
== 0.1
Initialization
20
30
40
Estimated Loss
Figure Generator learning for 2-point dataset y and various generators: 1-ellipse (row 1), ellipse (rows 3), and MLP (rows 5). Results are displayed using the same presentation as in Figure The learning rate for is here fixed to ς 0.1. See the text comments for more details.
In the first row of Fig. [6. the loss slightly oscillates for K = 100, end the generated distribution μ사 realizes good approximation of y for = 200. In the second row, the number of iterations of the inner loop is reduced to K and the algorithm stabilizes to bad configuration. This suggests that when is too low, the ASGD does not converge fast, enough to irrigale all points the target distribution v. If the Laguerre cell of one data point Y/ stays empty, then, from equation Grad-OT) with À O, one can see that yj never appcars in the update of f. As consequence, nothing pushes (4g to visit y/-
The examples of Fig. give an intuition of the behavior of WGAN learning algorithms when applied to high-dimensional datasets, such as images. First, depending on the choice of hyperparameters, the learning process may stabilize or not, as already noticed by (Stanczuk et al. 2021). Convergence issues do not prevent the learned distribution from realizing good approximation of the data, the sense that a non stabilized generator can produce plausible samples. The learned distribution indeed able fit complex structure underlying the data, made of noisy curves that interpolate between datapoints. Samples obtained the interpolation between those two points. With better interpolation
branch linking two datapoints yj, Uı images, such an interpolation of yj ys could be blurry average (L2 interpolation) related to geometric deformation of yy into yk- This is what we observe in the next scction when fitting a generative model to the MNIST database. However, considering the instability of the learning process and the number of parameters involved, it difficult to ensure a priorí that a generative model with a given architecture appropriate for sampling accurately of given datasct. As illustrated in experiments, such a model should be able to produce plausible interpolations of data points while exploiting the diversity of the dataset to avoid mode collapse.
thus be seen
20

---

Published in Transactions on Machine Learning Research (MM/YYY)
K 100
== 0
534
X -= 0
K = 2
2013
5015
X = 0.05
バ = 100
3.0
3127
K = 100
= 0.1
300
0
50
100
71 150
n = 200
Estimated Loss
Figure 6: Generator learning for 6-point dataset y with MLP generator. Results are displayed using the same presentation as in Figure 4 On the left we indicate the regularization parameter À and the number of iterations the ASGD inner loop. The learning rate for y is here fixed to 7 = 0.1. See the text for comments.
5.3 Generator learning for MNIST dataset
We finally address the problem of digits generation by leaning generative model the MNIST database containing J 6 10* images. We discuss the behavior of the alternating Algorithm ] and examine the impact of the regularization parameter X both on the visual results and the convergence of the loss function. We also discuss the effect of parameterizing the dual variable vp by a neural network.
The detailed settings used for these experiments are given in Appendix F.2 The generator parameters 0 are optimized with ADAM algorithm (Kingma & Ba 2015). The dual variable is optimized with Pytorch implementation of ASGD, with warm start initialization.
On Fig. 7 we display sampled digits obtained with the generative networks learned with Algorithm run with different settings. The generators learned with unregularized OT (A = 0) produce mostly convincing samples, slightly more blurry than the images of the database. Some of the samples generated do not look exactly like a digit but like a mixture of different digits. This reflects the fact that the generative network interpolates between the images of the database. The two tested architectures for the generator are MLP and DCGAN. They produce comparable results, with slight advantage for DCGAN, which provides cleaner samples thanks to its more complex architecture adapted to two-dimensional data.
In all cases, the quality of visual results deteriorate when the regularization parameter À grows. For very small X, the results are comparable to the unregularized case. For larger X, the outputs the generative networks concentrate on a blurry average of the database, due to the estimation bias of Wx, (Genevay et al. 2018). This can be understood from the gradient formula. (57) which involves the gradient of the regularizod o-transform given by (47.. When À +00, Vijo.A (2) degenerates a simple average Jy Vzc(a, (y). With the blur created by entropic regularization the transport plan, the sampled points pushed
21

---

Published in Transactions on Machine Learning Research (MM/YYYY)
towards all the target points in mixed manner. In contrast, with unregularized transport, each sampled point x is pushed towards the data point T (3) assigned by the current OT map, as illustrated in Fig. 2
/
P
3
4
9
4
9
9
9
9
9
5
0 4
4 6
9
6
9
9
9
MLP SDOT
0
/ 7
9
4
4
9
9
9
9
9
9
9
9
9
6
9
9
9
7
1 9
7
0
9
0
4
9
9 {
7
9 9
9
9
9
0
4
9
9
9
7 0 4
9
9
4
9 4
R
9
9 9
7
9
9
9
4
69 8 9 O
1
3 3
4
2
\
G 9
9
/
9 9
/ 9 1 4 7
/
4
5
7 /
9
DCGAN
SDOT
/ 4 2 5 1
f 7
6 / 2 2
4 7
4
I 9 1
9 1 7
9 9
9
9
D 6 1 1 8 67
4 3
6
9 2
8 5
4
/
7
/
6 6
9 6
1 / 6
9
6 6644
7
/ 9 4 8 3
59 O
I
9
Y 774 17484461
9
1
6
7
7
9
7
6
/
19/7612
6
O
G
9
2
6566759 5 3
O
3
PO3 2 4
/
G
2 6
0 2
6
9 41
9
S 9
7 7624412
8 V S 2
6 5
3 9 S 9 0
3 I 8 3 6
SDOTNN
4 1 7 9 2
1 8 5
0 L
/ 8
DCGAN MLP
1700 4 74
5 6
5
5
2
4 8 O
3 103+3+2 4 1
9
8 6
2 0 2
6
8 9 8 8 2 3
70
7 5 1577277 2
3
7
4
7 0
3
9
E 708988S0
0077 f 4
89
3 3
6
O
07089898
9 1799998
10
2
2
7 1
4
4
5
5
7 & 5 7
S
O
8 9 8
6 7
6
O 1 9 5
3 5
7 7
7
5
SDOTNN
2 / 9 0
6 4 7
4 2
O
8
9
2 2
5 2 Q
7
9
4
4
6
9
I
4 4 / 9 3
9 9
7
6
9
7 2 9
2
3
9
9 3 2
4 7
5
5 9
9
4
0
2
3
9
7
9
I
I
1
8
8
6
0
5
7
$
/
0
0 1
6
2
8
0
0
6 9
2
4
/
6 7
7
0
2
9
/
7 9
9
0
7
0
0
7
7
O
6 4
O
1
3
0
A
0 6
0
8 P
1
2
8
3
2
8
8
x= 0
X = 0.025
À = 0.05
À = 0.075
A=
0.1 001.1
À A= 0.5
Figure 7:
Generator learning for MNIST dataset. We compare here several generative networks trained with different architectures for the generator go (MLP or DCGAN) and the dual variable ge with no parameterization (SDOT) in the two first rows, or MLP parameterization (SDOTNN) in the two last rows, and varying the parameter λ of entropic regularization.
To better understand these visual results, we now examine the behavior of the loss function depending on the adopted setting. Fig. shows the evolution of the estimated loss HA H 0) along the itcrates of Algorithm 1 when the dual variable vi is either parameterized as a vector in R' (SDOT, for semi-dual OT) or a neural network (SDOTNN, for semi-dual OT with neural network).
The loss stabilizes, with small oscillations, in & 500 iterations, and the limit values obtained with both parameterizations (SDOT and SDOTNN) are similar. Note that the limit value is lower with the SDOTNN parameterization. Since the adopted multilayer perceptron has here > 5 10 parameters (and is thus much larger than J == 6 10*), it is likely that any value (1(1,)))sEE E R can be attained with such a parameterisation for th. Notice also that the loss decreases in a more stable way with the SDOTNN parameterization. This parameterization is indeed likely to be more robust to the individual changes on (w;) when updating the parameters 0 of the generator, even when using warm start as done here.
The convergence speed does not improve drastically when using a larger regularization parameter A, contrast to what we observed with the Dirac generator of Section 5.2.1 This obscrvation confirmed in Fig. where we display results obtained with various regularization parameters X and the four tested combinations of architectures for the generative network and the dual variable. These experiments illustrate that increasing the regularization parameter leads to smoother optimized functional, which reflects in a more stable evolution of the loss. For very small X (5 0.025), we do not observe improvement of convergence speed with respect to 0. In this low regularization regime, we suggest that the behavior of the loss evolution depends on the chosen architecture and the hyperparameters (step size strategies for ASGD or ADAM).
We finally display in Fig. 10 for fixed generator parameters 6, the evolution of the loss sb H Hx(3. 8) (defined in (68) during the inner ASGD loop used for optimizing the dual variable 1). In order to complete
22

---

Published in Transactions on Machine Learning Research (MM/YYY)
3.0
SDOT SDOTNN
SDOT SDOTNN
2.5
1.5
1.9-
95-
0.5
200
400 Ron 1000
400
800
1000
X 0
A 0.025
Figure 8: Evolution of the estimated loss o 0) along the iterates of Algorithm to learn DCGAN generaling MNIST digits. For each update of 0, the loss is computed by using the current estimate v of the dual variable. For two values of the regularization parameter (A = 0 on the left and 0.025 on the right), we compare the OT loss values obtained by parameterizing &i directly as a vector in I (SDOT) or as neural network (SDOTNN). See the text for comments.
Figure 9: Evolution of the estimated loss Hx 8) along the iterates of Algo- rithm [ for the four tested combinations of parame- terizations of the generator (MLP DCGAN) and the dual variable (SDOT SDOTNN). For each update of 0, the loss is computed by using the current estimate v of the dual variable. Let us recall that the loss function HA depends the regularization parameter X, which explains why the limit value attained by the amgorithm actually increases when À - See the text for additional comments.
200
0=0,0
A=0,00
>=0.025
25-
A=0.025
2-0.550
A-0.050
150-
2.0
2=0.075
A
2=0.100
1.5
==0.10
100
1.0
050
05-
200
820
2003
200
420
620
1000
MLP,, SDOT
DCGAN, SDOT
2-0.000
Y-0000
d=0.025
A=0.025
25.
2=0.050
A=0.050
0-0.075
A-0.075
0=0.10
A=0.10
100
1.5
050
05-
MLP, SDOTNN
DCGAN, SDOTNN
the comparison, also include the convergence plot obtained with the ADAM algorithm applied the same problem. These convergence curves reflect again the slow convergence of the ASGD algorithm. We observed that a careful tuning of the learning rate of ASGD is necessary to obtain a sufficient decrcase of the loss. Next, the convergence plots obtained with ASGD are similar with both parameterizations SDOT and SDŌTNN. For small value of the regularization, turning to the ADAM algorithm does not improve the convergence speed for the SDOT parameterization. However, we remark that using the ADAM algorithm with the SDOTNN parameterization seems beneficial for all tested regularization parameters. The loss value obtained after 100 iterations is lower with SDOTNN than with SDOT, and the convergence faster.
23

---

Published in Transactions on Machine Learning Research (MM/YYY)
-2.0
SDOT-ASGD
SDOT-ASGD
SDOT-ASGD
SDOT-Adam
SDOT-Adam
-2.0
500 1-0m-
-220
Mw
SDOTNN-ASGO
SDOTNN-Adam
-229
SDOTNI-ASED
SDOTNN-Adaa
-2.30
SDOTNN-ASCO
SDOTNN-Adam
-220
2.80
-241
-2.22
4.37
-2.35
-333
20
X 0
= 0.001
X = 0.005
Figure 10: Evolution of the estimated loss s + Hx 0) along the iterates of the inner loop of Algorithm Hero, the paramcters of the DCGAN generator is fixed, i.c. we consider a semi-discrete OT problem between a fixed μg and v. For several values of the regularization parameter, we compare the evolution of the loss when parameterizing & directly as a vector in RJ (SDOT) or as a neural network (SDOTNN). For both parameterizations, the optimization is done using either ASGD with decreasing step size for SDOT and gos for SDOTNN) or ADAM (with learning rate 0.001). See the text for comments.
VR
0.1
6 Conclusion
In this paper we give new insights on the thoory and practice for learning generative networks with regularized Wasserstein distances. On the theoretical side, we prove gradient formula for the minimized loss in two different frameworks: in the semi-discrete case (i.e. when the larget distribution has finite support) without regularization, and in more general case (with a general v) with entropic regularization. These results are based on weak regularity hypotheses on the cost and the generator, which are satisfied for many E6' cost functions and neural network generators with 8 activation functions. In the semi-discrete setting, it is also required that the generator does not charge the Laguerre interface, which is the generic case encountered in practice. These hypotheses are helpful to better understand the possible degenerate cases that can be encountered, and we provide such a counterexample.
On the practical side, we show that alternating algorithm approximate the solution of this optimization problem. The inner loop of this algorithu consists in approximating optimal dual potential for regularized OT with a stochastic optimization algorithm. With experiments on oow-dimenioonal dataset, we illustrate that this alternating optimization algorithm has no reason to fall on the points of inexisting gradients, but that it may exhibit various singular behaviors. In most cases, it stabilizes to a generator which forms a relevant approximation of the larget measure. Nevertheless, because of the fixed number of iterations for the inner loop, it can also oscillate or get trapped in sub-optimal positions (e.g. mode collapse on a single data point), depending on the choice of hyperparamcters. Experiments on MNIST digits demonstrate that our algorithm is able to learn neural network generating plausible images in high-dimensional setting, Convincing visual results are indeed obtained with zero or small regularization parameter X. We observe that the smoothing of the targeted loss function is not sufficient to significantly improve the convergence speed of the optimization algorithm estimating the generator parameters, while inducing a bias.
From this study, we claim that the success or failure of the WGAN learning process not only affected by the chosen loss function (L-Wasserstein, 2- 2-Wassers,iin, Jensen-Shannon divergence, etc) but its also crucially depends on the choice of generator architecture and the choice of the optimization strategy.
Concerning the stochastic optimization used to solve the semi-dual OT problem, we observed that it may be beneficial in terms of convergence speed to parameterize the dual variable with a neural network, provided that one uses a well-chosen and carefully tuned algorithm for the optimization.
The main limitation of the considered algorithm is that the inner loop based on the computation of regularized c-transform. It thus requires, each iteration, to visit all data points, in order to find a kind of biased nearest neighbor. In order to scale up to larger database, a possibility is to approximate
24

---

Published in Transactions on Machine Learning Research (MM/YYYY)
the regularized c-transform with batch strategy (Mallasto et al. 2019a). As perspectives, it would be interesting to control the errors made at each iteration by the ASGD early-stop or by a batch strategy, in order to get a globally stable optimization process; or to consider other Stochastic Gradient Descent Ascent strategics (Sebbouh et al. 2022)
Acknowledgments
This study has been carried out with financial support from the French Research Agency through the GOTMI, Mistic and Prod projects (ANR-16-CE33--0000) ANR-19-CF:40-00 and ANT-119-CF223-0027-01) and from the GdR ISIS through the Remoga project.
References
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223, 2017.
Franz Aurcnhammer, Friedrich Hoffmann, and Boris Aronov. Minkowski-type theorems and least-squares clustering. Algorithmica, 20(1):61-76, 1998.
Jérémie Bigot, Elsa Cazelles, and Nicolas Papadakis. Central limit theorems for entropy-regularized optimal transport on finite spaces and statistical applications. Electronic Journal of Statislics, 13(2::5120 5150, 2019.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In International Conference on Machine Learning, pp. 537-546. PMLR, 2017.
Yucheng Chen, Matus Telgarsky, Chao Zhang, Bolton Bailey, Daniel Hsu, and Jian Peng. A gradual, semi- discrete approach to generative network training via explicit wasserstein minimization. In International Conference on Machine Learning, pp. 1071-1080. PMLR, 2019.
Lénaïc Chizat. Unbalanced Optimal Transport: Models, Numerical Methods, Applications. PhD thesis,
Université Paris Dauphine, PSL, 2017.
Marco Cuturi and Gabriel Peyré. A smoothed dual approach for variational Wasserstein problems. SIAM Journal on Imaging Sciences, 9(1):320 343, 2016.
Muhammad Fadli Damara, Gregor Kornhardt, and Peter Jung. Solving inverse problems with conditional-
GAN prior via fast network-projeeted gradient descent. arXiv preprint wxXi:2219.01105, 2021.
Kilian Fatras, Younes Zine, Rémi Flamary, Remi Gribonval, and Nicolas Courty. Learning with minibatch Wasserstein asymptotic and gradient properties. In Silvia Chiappa and Roberto Calandra (eds.), Pro- ceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 2131-2141. PMLR, 2020.
Jean Feydy, Thibault Séjourné, François- Xavier Interpolating between Optimal Transport and MMD using Sinkhorn Divergences. In The 22nd Interna- tional Conference on Artificial Intelligence and Statistics, pp. 2681-2690, 2019.
Praner Vialard, Shun-ichi Amari, Alain Trouve, and Gabriel Peyré.
Bruno Galerne, Arthur Leclaire, and Julien Rabin. A texture synthesis model based on semi-discrete optimal transport in patch space. SIAM Journal on Imaging Sciences, 11(4):2456-244 2493, 2018.
Aude Genevay. Entropy-regularized optimal transport for machine learning. PhD thesis, Université Paris Dauphine, 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-3444 2016.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. GAN and VAE from an optimal transport point of view. arXiv preprint or X 1706:1700000 01807, 2017.
25

---

Published in Transactions on Machine Learning Research (MM/YYY)
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning Generative Models with Sinkhorn Divergences. In Amos Storkey and Fernando Perez-Cruz (eds.), Proceedings of the Twenly- First. International Conference on Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine Learning Research, pp. 1608-1617. PMLR, 2018.
Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, and Gabriel Peyré. Sample complexity of Sinkhorn divergences. In The 22nd international conference on artificial intelligence and statistics, pp.
1574-1583. PMLR, 2019.
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 informalion processing systems, pp. 2672-220222 26800 2014.
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 5777, 2017.
Paul Hand and Babhru Joshi. Global guarantecs for blind demodulation with generative priors. Advances in Neural Informalion Processing Syslems, 32, 2019.
Reinhard Heckel and Mahdi Soltanolkotabi. Denoising and regularization via exploiting the structural bias of convolutional generators. In Proceedings of the 8th International Conference on Learning Representations, ICLR, 2020.
Antoine Houdard, Arthur Leclaire, Nicolas Papadakis, and Julien Rabin. A generative model for texture synthesis based on optimal transport between feature distributions. Journal of Matheratical Imaging and Vision, 65(1):4-28, 2023.
Rakib Hyder and M Salman Asif. Generative models for low-dimensional vidco representation and recon- struction. IEFE Transactions Signal Processing, 68:1688-170) 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, ICLR, 2015.
Diederik P. Kingma and Max Welling. Auto-encoding variational Bayes In Proceedings of the 2nd Interna- tional Conference on Learning Representations, ICLR, 2014.
Jun Kitagawa, Quentin Mérigot, and Boris Thibert. A Newton algorithm for semi-discrete optimal transport. Journal of the European Math Sociely, 2017.
Alexander Korotin, Lingxiao Li, Aude Genevay, Justin M Solomon, Alexander Filippov, and Evgeny Burnaev. Do neural optimal transport solvers work? continuous Wasscrstein-2 benchmark. Advances in Neural Information Processing Systems, 34:14593 14605, 2021.
Alexander Korotin, Alexander Kolesov, and Evgeny Burnaev. Kantorovich Strikes Back! Wasserstein GANs are not Optimal Transport? Tn Thirty-sinth Conference on Neural Information Processing Sys- tems Datasets and Benchmarks Track, 2022.
Arthur Leclaire and Julien Rabin. A stochastic multi-layer algorithm for semi-discrete optimal transport with applications to texture synthesis and style transfer. Journal of Mathematical Imaging and Vision, 63 (2):282-300 -08, 2021.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner, Gradient- learning applied to docu- ment recognition. Proceedings of the IEEE, 86(11):2278-22) 2324, 1998.
Na Lei, Kehua Su, Li Cui, Shing-Tung Yau, and Xianfeng David Gu. A geometric view of optimal trans- portation and generative model. Computer Aided Geometric Design, 68:1-21, 2019.
Oscar Leong. Learned Generative Priors for Imaging Inverse Problems. PhD thesis, Rice University, 2021.
26

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Dong Liu, Minh Thanh Vu, Saikat Chatterjee, and Lars K Rasmussen. Entropy-reen ceatropy-regllarized optimal transport generative models. In Proceedings of the TEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3532 3536. IEEE, 2019.
Anton Mallasto, Jes Frellsen, Wouter Boomsma, and Aasa Feragen. (q, p)-wasserstein gans: Comparing ground metrics for wasscrstein gans. arXiv preprint arXiv:1902.0866 2019a.
Anton Mallasto, Guido Montúfar, and Augusto Gerolin. How well do WGANs estimate the Wasserstein metrie? arXiv prepriat (rXXi:19100005 2019b.
Sachit Menon, Alexandru Damian, Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Self-supervised photo upsampling via latent space exploration of generative models. In Proceedings of the ieee/cuf conference on computer vision and pattern recognition, pp. 2437-2445, 2020.
Daisuke Oyama and Tomoyuki Takenawa. On the (non-) differentiability of the optimal value function when the optimal solution is unique. Journal of Mathematical Economics, 76:21 32, 2018.
Gabriel Peyré and Marco Cuturi. Computational optimal transport. Foundations and TrendsB in Machine Learning, 11 11(5-6):355-007, 2019.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convo- lutional generalive adversarial networks. In Proceedings of the 4th International Conference on Learning Representations, ICLR, 2016.
Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and Jason D Lee. On the convergence and robustness of training GANs with regularized optimal transport. In Aduances in Newral Information Processing Systems, pp. 7091 7101, 2018.
Filippo Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 2015.
Othmane Sebbouh, Marco Cuturi, and Gabriel Peyré. Randomized stochastic gradient descent ascent. In International Conference on Artificial Intelligence and Statistics, pp. 2941-2969. PMLR, 2022.
Vivien Seguy, Bharath Bhushan Damodaran, Remi Flamary, Nicolas Courty, Antoine Rolet, and Mathieu Blondel. Large-scale optimal transport and mapping estimation. In Proceedings of the 6th International Conference on Learning Representations, ICLR, pp. 1-15, 2018.
Fahad Shamshad and Ali Ahmed. Compressed sensing- based robust phase retrieval via deep generative priors. IEEE Sensors Journal, (2(2):2286220) 2298, 2020.
Yujun Shen, Jinjin Gu, Xiaoou Tang, and Bolei Zhou. Interpreting the Latent Space of GANs for Semantic Face Editing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogration (CVPR), June 2020.
Jan Stanczuk, Christian Etmann, Lisa Maria Kreusser, and Carola-Bibiane Schönlicb. Wasserstein GANs work because they fail (to approximate the Wasserstein distance). arXiv preprint arXim:2103.0167% 2021.
A A Neural Network Architecture validating Hypothesis (Go)
In this section, we consider a neural network architecture given by a composition of affine layers and &e Lipschitz activation functions. More precisely, the generator defined as the composition of elementary layers defined by
Va E Edi-, fr.) = pe(a,x + be).
(74)
where ag 1 Rede and where Pe : Rdd Rde is E1 and Lipschitz function. With a random input noise Z in Z R and intermediate dimensions do, di....,dy = d, the generator is defined by
v0 V z00,)) -t a... ),
(75)
27

---

Published in Transactions on Machine Learning Research (MM/YYYY)
where the parameters 0 (at, be)isesL are taken in open set + C IT Rdexde- R
The following proposition shows that Hypothesis (Go) is satisfied for such a neural network architecture.
Proposition 3. Let consider generator g of the previous form (75). Assume that the activation functions Pl.....Ph. PT. are E and Lipschitz with the same constant Kp. Assume also that the input noise is integrable, that is, B[|| co. Then g salisfies Hypothesis (Ga).
Proof. Since the affine layers and activation layers are E6, it is clear that 0 + g(0, is 80, In order to show Hypothesis (Ga); we only have to show that (22) holds on any compact subset of θ. Let V C θ be a compact. Since V is bounded, there is A >> 0 such that for all = (ag, E V, we have || & x. and | & k. In particular, the corresponding function feaaee is x-p--iischi...
Let 0= == (ap,be) be)ss E V and 8' =d/z by)isest. EV. First, assume that 0,0 only differ on one component: for fixed L, let us decompose (re, B2 st), 0 (ré, se) with re- = (ft)ece and st = (0))sz. We can then write
g(0,z) = Re,re (e (Te,e (=)) Re (ereee + by))
(z)++
(76)
where Re = fL.OLde de o... fe+1,a biy: and Te,e, fe- .... flanbb. It is clear that Re,,, and Ted are respectively (kK,)² b- and (K: 6
(( Lipschitz. Therefore,
119(0', 900 2) s (kK,)
+ pe(aiiTe,,, (2) K'll S (kKKp) | K 1 (,)Te,,,(3) + by b/1l
(77)
(78)
< (k<K)) K delll [.),)) + 11be B'll)-
(79)
It remains to bound (TTe,, For that, let remark that for any 1,
br (x)] & al (0)Il + =K2 = (()) + xK1l S a + <KGll=|1,
(80)
where a [0)( + kKp- Thus, with simple recursion, get
11a(0, z)1l S > (kK,)* + (nK,)*
(81)
1=1
Since Te,, is the concalenation of only the l --1 1 first layers, we have also
[TT,,, (=)]I S Ce + (kK,)) ||=|| with C a= (kK,)) (kK, --2 1-1- Gathering the previous incqualitics, we get llo(0', 2) - g(0. S (Ce(nKK,) (r Upper bounding ||ay af'l and l|b. b/ll by ||0 0'll. l|. we finally get, if 0, o' differ only on the f-component,
(82)
||ar - dill + (xK,)= Bbll-
(83)
[ De (x.K)) { D = (nK,)*
Vz E2, 11)(0', g(0, =)1l s (D++ + D/||=11110 0'll with
(84)
1- K
Therefore,
1.
vO, EV, VEER" 1l)(0',))) - s K())]10 - 0'll with K(=) = Σ
Dr + D211=11,
(85)
t=1
and we have [[K( < oo because Elll 21] x0.
28

---

Published in Transactions on Machine Learning Research (MM/YYX)
B
Counter-example with regularized OT
We consider the same measures than in Proposition 2 μi 6g and
2,6r + 2 26
For A > 0, one has
c(0 (-wm)
(1 viozi
Fx 0) = ())) = -Alog
_ 2
(86)
and from the primal formulation, one can also get directly that
1 (x) マ (0, vn) + (c(0,0)).
1
(87)
For any 4i, the function 0 Fx differentiable on Rd for p and on E (y1, y2) for p Thus in the regularized case À > 0, (x -) has singularity the interface Ag. For a fixed Ou, the maximization of H(, 0o) leads to the same solutions satisfying (27 than in Proposition 2 d.e. any tho0 such that
(88)
It follows that Formula
Grad-OT) holds in that case:
(hx(0)) = v.c(0, v1) + 1 Vac(O, v2) = VoFx
(89)
2
Let us also notice that using regularized OT docs not allow to cope with all differentiability issues. Indeed. for 1, æy is not differentiable at y1, 1/2 even for X > 0. This illustrates the need of a regularity hypothesis on the cost, even in the case of regularized OT.
C Continuity of c-transforms
In this section, we will recall properties of regularized c-transforms. For that, need modulus of continuity of the cost function, that is, the smallest function such that
Vz, x' E X, Vy. v' V/ [c(2, y) c(2', s/1 < (1x x' + 11y v'll)
(90)
Since e is continuous on the compact X' x V, it is uniformly continuous, thus lim w(8) = 0.
Lemma 6 ((Santambrogio 2015 Feydy et al. 2019)). For X t any c-transform ver. has modulus of continuity which is bounded by the modulus of continuity of the cost function.
Proof. If & holds pointwise, then softmin & softmin pointwise. Also, for constant k E I, softmin(k+ u) = k + softmin(u). But, from the definition of w, we have c(æ, v) vyy) & w(]læ - x' + c(x',)) (vy). By taking the soft-min, we thus obtain ())(r) < w(Ix - æ'll) + ()) and by symmetry, this leads to
(2) v (x') & w([l x'1)).
(91)
Lemma 7. For X >>0 O, and any v. x E E()), / x 1oo < 1| x In other words, the map s + a/aaA is 1 1-Lipschitz for the uniform norm.
Proof. Applying the monotonicity of the softmin operation to the inequality c(x,y) (vy) < 1/ xll +
c(x,y) y) x(v), we get (e)(x) < [| xlloo (x). On can conclude with symmetry argument. ]
The following lemma states that the optimal dual potentials vary continuusly with respect to the input measure they are unique up to additive constants.
29

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Lemma 8 ((eeydy et al. 20191). Assume that X,Y are compact and is continuous. Let füx X. Assume that v is fined, and that (nn converges wenk-* to I in the space of probabilily measures on X. Assume that the Kantorovich potentials associated with Wa(H, v) are unique to an additive constant, which is the case if X >>>000000 O. For each n, let Pn be a c-concave Kantorovich potential for Wx(pn, v) such that fn(#o) = and lel vp be the (necessorily e-coneave) Kantorovich polentåal for Wx(1,, u) such that p(xo) = Then in + &p uniformby on X.
Proof. By compactness of X x V, e has a bounded modulus of continuity w(6) which tends to zero when 0. By 911, we obtain that the functions 1px1 are bounded by supzex w(llar mol)) co. Besides, Lemma also shows that the functions yn are uniformly equicontinuous X. Therefore, Ascola-Ascoli theorem ensures that the family {pn, E NJ is relatively compact in (X)).
Now, assume, by contradiction, that (Px) does not tend to y in (x)). Then there would cxist > 0 and subsequence (Pr(w)) such that
[lpr(a) - pl >E Vn.
(92)
By relative compactness, one can then extract a subsequence (Pr(a(n)) which converges (X) to a function G. Using the monotonicity of soft-min, this implies that (F also converges in (xt) to God, Thus
W ((n. v) = pndde + f vs m n / pduu + / (
(93)
Finally, also have W(pn v) - W(H, v) since Un 2 μ. Thus w(,,v) J pdu J / and is Kantorovich potential for (H, and ((xo) lim pn((x)) O. Using the uniqueness assumption, get
+ = o which contradicts 92
D Technical Results
We first recall the proof of the envelope theorem Oyamaa & Takenawa 2018 Prop. A.1).
Theorem 7 (Envelope theorem Oyama & Takenawa 2018)). Let X be topological space. Let A be open set of normed vector space E. Let f X A R be function and let denote
Va A, v(a) sup f(0, a.) =EX
(94)
Lel A X be such that for all A, v(a) = [(s(a), a). Let A be a point such that
is continuous al a.
the portial differential Daf of f with respect to ewists in neighborhood of (s(a),a), and is continuous at (s(a))
Then u is differentiable at a and Du(a)= D)
Proof. Let { = s(a) and let 6 > 0. The second hypothesis gives an open neighborhood x V of (5, ar) X A such that for any aI e U V, f(x,-) is differentiable a and such that the partial differential (x, a) + Dzf(x a) continuous on U V. By continuity of s, -1) n is an open neighborhood of a and thus it exists 17 > 0 such that ||h|| 17 implies + h E V and s(a + h) E.
By definition of v, we have for any h E such that ||b]|| <
f().a) < v(a + h) v(a) < f(s(a + h), a + h) f(s(a + h))
(95)
On the one hand, by definition of D.f(E, there exists m E (0, m) such that || m implies
[s h) a(E - DaS(E, el|hi]-
(96)
30

---

Published in Transactions on Machine Learning Research (MM/YYYY)
On the other hand, for ||b]| < n, E [0, f(s(a + h), a th) is differentiable on [0, 1] and therefore, by virtue of the mean value theorem, there exists 0^ E (0, such that
f(s(a + h), h) f(s(a a) D.f(((a h), + 0nh)h.
(97)
By continuity of Daf: there is an open neighborhood U V U of (5, a) such that
[Da](r, a) Daf(E. a)l c,
(98)
Again, by contimuity of s, s-' (U) V is an open neighborhood of and thus, there exists 72 E (0, such that ||b]] < implies a - h E s (U) n. Therefore, for ||4]| < m2, (s(a + hi, a + 0nh) E U x V and thus
I (PPa[((aa Finally, for ||A|| < min(m), 7222 we get (e(a+)) - DD, < < which proves that is differentiable at and Dav(a)= af)
a ||ll|| < E||A||- (99)
The next proposition gives the support of fush-forward distribution. Proposition 4. Let Q = [-1,1]", and Q + Rd continuous. Let Z be random variable with uniform distribution ( on Q and let = gtC be the distribulion of g(Z). Then the support of p. is eractly g(Q).
Proof. Since y is continuous, n{Q) is compact and closed. Thus U = g(Q) is open, and we have
((U)= ((o(() = (U)) 0.
(100)
because g (U) does not intersect Q- This proves that Supp(μ) g(Q)- Now, if V is open set such that v(V) = 0, then P(Z (V)) 0, which gives g -VV n Q Ø because g (V) is open. It follows that
V C sQ)),, which proves that Supp(u) is exactly gQQ).
E Proof of Theorem 6
Using Theorem we only have to study the regularity of + Wa(No: po) for >> O. We will use again the envelope theorem recalled in Appendix D We consider the set of E and L-Lipschitz functions on X equipped with the norm [x + o/ and we use the dual expression 66) which can be written with the integral operator of 17 and with
Fx(x,n,0) = 1(x,0) + 1-n..(. 0) + XEx(x,7,
(101)
0, T(x T,x.7,0,2, W) ]
where Ex(xn,0) = exp
(102)
and T(, 7. 2, = x(go(2)) + ((go(r)) - (z))()), go()),
(103)
where W, Z are two independent random variables of distribution Ç. For any x E C, differentiating under the integral as in Lemma 5 gives that .) is differentiable on θ with gradient
Vol(x, 0) E [Deg(0, Vx(ex((( Z))]
(104)
By the same reasoning, one obtains that Ex(x, n. -) is differentiable on O with gradient
Vel 0, Z, W)
T VIx.n,0,,40 W)
VeEx ())) E
cxp
(105)
A
with V,I(x.7,8,2,0)) Dog(0, 2)²h (Vx(g(0,2)) - v. 2), g(0, w)))
(106)
+ Dog(O0 w) (Vn(g(0, w)) vyc(o(0, 2), g0 w)))
(107)
If Po any bounded set of C, using bound similar to 56 and the dominated convergence theorem shows that (x I(x, 8) is continuous Po x V. Similarly, one can that I is Lispchitz in 0 with (z, W)-integrable bound
T(x, n. 2,)
& V1 K(z) + V K(w) + T.) 7|]-
(108)
31

---

Published in Transactions on Machine Learning Research (MM/YYYY)
Since I is also bounded by + + ||+b|l be deduced from 103 this is enough to show that (x:7), - VoFx(x, 7) 0) is continuous on Po x V.
||e]|eo and since the continuity of I with respect to (x. 7, 0)
As we have a continuous selection of optimal dual variables (x. 1i) and as the gradient VaFx 7) 0) exists and is contimuus (x, 17, 0), all the conditions required by the envelope theorem are satisfied. Thus we can differentiate under the max (66
V WWW (no: pe) VgFx 0)
(109)
where (7), is pair of Kantorovich potentials for (x pe)). Finally, by symmetry, there exists k R such that 7). + & and by definition Ex(x.. 1),, 0) 1, so that Fx(x.. = 2I(x., l and therefore
VoFa(x., no. ne, 8) = (x 8) = 2E Dog(O, Vx- 2)]]
(110)
Putting all terms logether, we get the desired formula for (0)
F Detailed Settings used for Experiments on generator learning
F.1 Detailed Settings for the experiments with synthetic datasets
We here gather the parameters and network architectures used in the experiments of Section 5.2
50 iterations on 0 with SGD algorithm (with constant learning rale r = 0.2), except for the MLP generator which optimized with Adam (with constant learning rate 0.05)
100 iterations of the inner loop with ASGD algorithm (see learning rates below) with cold start initialization (unless otherwise specified)
The cost c(z, y) is the quadratic cost || y/1
For the generator consider various architectures go and input noise Z:
Dirac generator gdirac(2) (2) = 0 parameterized by 0 R2,
disk generator with fixed radius with Z uniform random variable on [0, 1J3, parameterized by
f E 2
disk (z) = 0 + rV (2o//(/cos(222))) sin (2T22))))
an ellipse generator (referred to as 1-ellipse) with Z a uniform random variable on [0, 1J2, parameterizel by 0 = (t,a, b) E 2 R:
ge (z) t (a (sin
a mixture of two ellipses (denoted by 2-ellipse generator) with a uniform random variable on [0, 1]3 parameterized by (01, 02) E (T22 R. x 12)
gon (21, 22)
if 23 <
mixell gø
got (2), otherwise.
multilayer perceptron (MLP) with Z a uniform random variable on [0, 1]din nhid fully-connected layers with dimension dhid and activation function Elu(l). In Section 5.2.2 the layers are to din 5, dhid 10 and nhid 3. In Appendix G the parameters are indicated in the captions of the figures.
All batches of are made of = 100 samples, except for the Dirac generator where sample suffices.
The dual variable & is modeled by vector eb E R
The dual variable is optimized with the ASGD algorithm written in The step size strategy is y with learning rate y 0 (values indicated in the text).
32

---

Published in Transactions on Machine Learning Research (MM/YYYY)
N--00 0,63
4 0005
4271
+.00
0.1
32
10
05
= 0
71 = 50
= 100
n2 150
200
Estimated loss
Figure 11: Generator learning for 6-point dataset y with MLP generator. The parameters of the MLP are din = 100, dhid 256, nhid 3. In the first columns, along the mumber of iterations n, we display y (dark blue) and the current position of μig (sampled points in light blue). The Laguerre diagram associated the current value of 3 is displayed in the background with the colored partition. The last column shows the estimated loss HA H 0) along the iterates. On the left we give the regularization parameter X.
F.2 Detailed Settings for the MNIST experiment
We here gather the parameters and network architectures used in the experiments of Section 5.3
3000 iterations on 0 with ADAM algorithm Kingma & Ba 2015) with learning rate 0.001
K 10 iterations of the inner loop with ASGD algorithm with warm start initialization
The cost c(x,v) v) is the quadratic cost a -= y| normalized by = 4 E |lyl
For the generator go we consider two different architectures:
multilayer perceptron (MLP) with four fully-connected layers; the number of channels for the succes- sive hidden layers 256, 512, 1024 with activation functions LeakyReLU(O.2))
Deep Convolutional GAN (DCGAN) (Radford et al. 20166) adapted for the dimension 28x28 of MNIST
images, with 4 deconvolution layers; the number of channels for the hidden layers 256, 128, 64.
The input of these generators is a random variable Z following the uniform distribution on [-1, 1 100 All batches of Z are made of b = 200 samples.
The dual variable & is either directly modeled by a vector & E R', or parameterized by a multilayer perceptron with four fully-connected layers; the number of channels for the successive hidden layers is 512, 256, 128. These two different settings are respectively referred to as SDOT (for semi-dual OT) and SDOTNN (for semi-dual OT with neural network).
33

---

Published in Transactions on Machine Learning Research (MM/YYYY)
The dual variable is optimized with the Pytorch implementation of ASGD (torch asgd), which has parameters Ir and alpha. The step size strategy for the ASGD inner loop has been chosen as:
for the parameterization SDOT, Ir 5, alapph = 0.5,
for the parameterization SDOTNN, 1r 0.1, alpha 0.8.
The other parameters are fixed to default values.
G Additional experiments on 6-point dataset
In this appendix we provide additional results of generative model learning on the G-point dataset. In Fig.
I1 for fixed large MLP architecture, vary the regularization parameter A.
In Fig. we fix the regularization parameter À = 0 and we vary the configuration of the MLP architecture.
(2.
(2 24100 10. 100
(10, 10,
(10, 10, 10)
71 50
100
150
200
Estimated loss
Figure 12: Generator learning for 6-point dataset y with MLP generator. On the left we indicate
the tuple of parameters (din, dhid, nhid). In the first columns, along the number of iterations n, display y (dark blue) and the current position of pe (sampled points in light blue). The Laguerre diagram associated to the current value of 4 is displayed in the background with the partition indicated in colors. The last column shows the estimated loss HA (x 0) along the iterates. The regularization parameter is set. to À = 0.
34


Reviews:
[{"review_id": "UFyrRiBmTU", "reviewer": "Reviewer_ndPu", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- There is definitely a need to better understand the learning procedure and how/under what condition current algorithms work (or do not work). This paper is definitely a good step in that direction from a mathematical perspective. \nWeaknesses:\n- Writing: \n  - The paper is notation heavy and I believe the presentation of the paper could be greatly improved with an introductory section on notations.\n  - The related work section could be moved to the end of the paper or changed in a way that it is easier to follow with notations/contexts provided in the introduction.\n- Regularity conditions:\n  - I am still a bit uncertain about the differences between this work and previous works; Are there any concrete cases that this work shows the gradient exists/does not exist where the previous works cannot provide. If so, are there any practical implications?\n  - Moreover, it is very difficult to gain intuitions on the regularity conditions. I am assuming that these regularity conditions are not verifiable in practice? If so, I believe this should be indicated in the paper.\n  - Regarding Proposition 2, could the authors provide more intuition? For example, they could provide some insight on the intuitions behind this example. I am also wondering what happens when the objective is regularized? Would the gradient relationship still fail?\n- Approximating the gradient:\n  - As the authors have mentioned, it is impossible to exactly compute the inner dual solutions. One thing that is missing from the paper is the relationship between the approximations of the dual solution, and approximations of the gradient. This would be necessary for any practical algorithm to perform on this problem.\n- Experiments:\n  - The experimental section is a bit detached from the rest of the paper. For example, based on the experiments is there any practical reason why one might want to use regularization if it does not improve performance or speed of convergence? \n  - As the authors have mentioned, increasing regularization introduces biases in approximating the generative distribution. Previous works have shown that one can overcome these by using methods such as Sinkhorn divergences. I am curious what the results would look like with those approaches.\n  - Regarding the SDOTNN scenario, is it possible to change the number of parameters (compared to the number of data points) to see how/at which point does it affect the performance.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers entropy regularized and un-regularized OT formulation for learning generative models through GANs. The work proves formulas for obtaining gradient of the generative model in this formulation under some regularity assumptions.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Could you please provide updates/answers corresponding to the points mentioned above.", "broader_impact_concerns": "No applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "CSikmbXcZZ", "reviewer": "Reviewer_H5qL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is the detailed theoretical study of existence of the gradient of the optimal transport objectives which are used to train WGANs. The paper studies both the regularized case (semi-discrete) and entropic case and discusses conditions under which these gradients exist. At the same time, I think a noticable weak side of the paper is its writing. In the text, there are a lot of existing theoretical results (from Santambrogio's book, Genevay's papers etc.) and they are mixed together with the new results of this paper. It is not clear what is really new, how significant is the contribution w.r.t. the existing part. While there are some sections trying to describe this (e.g., Section 2.4), I have to admit that I got lost and can not fully access the amount of the theoretical contribution of this paper. Overall, I miss a short section (somewhere at the beginning) summarizing in a sufficiently detailed form the main theorems/statements which the authors claim as their contribution.\n\nI do not understand the point of experimental evaluation in this paper. In particular, using Entropic Wasserstein loss in GANs (lambda>0) leads to biased solution, i.e., W_{\\lambda}(\\mu_{\\theta}, v) is minimal not necessarily when \\mu_{\\theta}=\\nu. Thus, the minimizer in entropic WGAN is not necessarily the data distribution \\vu. Probably this is what we see in Figure 1 (the bias of the optimal solution increases?). I think this issue can be alleviated by considering Sinkhorn divergences (a.k.a. unbiased entropic transport) which the authors discuss in Section 4.4. However, their algorithmic methodology and is entirely about biased Wasserstein. I do not think this evaluation (or their proposed WGAN learning methodology) adds any value to the paper.\n\nSince the paper is mostly about existence/inexistence of objective gradient, a relevant experimental exaluation would be to show what are the potential pitfalls of the inexistent gradient in practice. So far I see the opposite: the case when this gradient may not exist (lambda=0) leads to the best generative model.\n\nThe paper misses discussion of several related works [1,2,3,4] where the authors also study some relevant aspects of WGAN training. In particular, the authors make several unsupported claims which I am not sure are correct. For example, \"When learning a Wasserstein generative model, the performance of the dual solver used for estimating the OT cost (3) is therefore a key point.\" -- the above-cited works mostly dismiss this claim.\n\nIn the unregularized case (lambda=0), it is widely known that the OT gradient of the potential is related to the OT map and with mild assumptions they can be recovered one from another. In particular, there are a lot of works studying the semi-discrete optimal transport formulations and OT maps -- their methodology is very similar to what the authors discuss with the Laguerre cells [5]. I wonder how the presented results are related to semi-discrete OT in general. Thus, I think including some deeper discussion about semi-discrete OT methods is desired.\n\nMinor\nIt would be nice to see some explanatory image in the section about semi-discrete OT.\nsection 1.3: inclucing -> including\n\n\n[1] Mallasto, A., Montúfar, G., & Gerolin, A. (2019). How well do WGANs estimate the wasserstein metric?. arXiv preprint arXiv:1910.03875.\n\n[2] Korotin, A., Li, L., Genevay, A., Solomon, J. M., Filippov, A., & Burnaev, E. (2021). Do neural optimal transport solvers work? a continuous wasserstein-2 benchmark. Advances in Neural Information Processing Systems, 34, 14593-14605.\n\n[3] Stanczuk, J., Etmann, C., Kreusser, L. M., & Schönlieb, C. B. (2021). Wasserstein GANs work because they fail (to approximate the Wasserstein distance). arXiv preprint arXiv:2103.01678.\n\n[4] Korotin, A., Kolesov, A., & Burnaev, E. (2022). Kantorovich Strikes Back! Wasserstein GANs are not Optimal Transport?. arXiv preprint arXiv:2206.07767.\n\n[5] Lei, N., Su, K., Cui, L., Yau, S. T., & Gu, X. D. (2019). A geometric view of optimal transportation and generative model. Computer Aided Geometric Design, 68, 1-21.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a complete set of hypotheses that ensure the validity of\nthe gradient formula which commonly appears in WGAN learning. Specifically, the authors consider the semi-discrete case (which appears in most WGANs - generator generates some distribution, data distribution is empirical) and additionally consider the general entropy-regularized case. They study the gradient formulas in these two cases. Also, for the (biased, not Sinkhorn) entropy-regularized case, the authors propose an algorithm to learn WGAN and test it on the grayscale MNIST dataset.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I think the authors should improve their paper in terms of separation of their contribution and existing results (see the previous section comments). \n\nFrom the experimental point of view, I think it might be better to study WGAN convergence with the unbiased entropy cost = Sinkhorn (see the reasons above), especially taking intro account the fact that the author provide a theoretical discussion of it, its potentials and gradient. \n\nAlso, it would be nice to see some experiment which is relevant to the “inexisting gradient issue”, e.g., demonstrating that the WGAN does not converge in this case. In other words, is the inexisting gradient an issue in practice, e.g., in some toy example?\n\nAdditionally, I suggest adding a discussion of the above-mentioned related works.\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "VYiwMi7dUz", "reviewer": "Reviewer_GVxx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper approaches an important problem of generative modeling via optimal transport. The semi-dual formulation proposed in [1] has a broad range of applications, and the rigorous outline of its differentiability (the contribution of the current paper) has both theoretical and practical implications. I've gone through all the derivations, and the proofs are correct to the best of my knowledge. However, I'm not an expert in the optimal transport field, and I might have skipped some subtle mistakes. For the empirical part of the paper, the authors base their claims only on the empirical facts presented in the paper.\n\nIn my opinion, the main weakness of the paper is the absence of immediate practical implications. First, the motivational example is not very practical; I'm not aware of any problem where the considered parametrization would be helpful. Second, the authors establish a set of sufficient conditions for the differentiability of the objective, but they don't discuss how one can satisfy these conditions in practice. For Theorem 3, the authors discuss how to relax the x-regularity condition and discuss that the potential uniqueness (Remark 2) condition can be discarded in the case of regularized transport. However, the x-regularity condition appears again in Theorem 5 (regularized transport), and the condition on $G_\\Theta$ is not discussed at all. After all, it is not clear whether these conditions can be satisfied in practice for any relevant model and data. As a consequence, the empirical part of the paper seems to be unattached to the theoretical part and reads like an algorithm from [2] but with a neural network.\n\nThe list of minor issues:\n- I find the proof of the motivational example (Proposition 2) not completely clear. Namely, I don't understand why the whole space $\\mathcal{Y}$ is restricted to two points $y_1,y_2$ while performing the c-transform in (33). Do we always restrict $\\mathcal{X}$ and $\\mathcal{Y}$ to the support of distributions? I haven't found this detail in the paper.\n- Throughout the paper, the authors use the nabla operator, not defining the differentiation argument, which might be confusing (although it's still possible to infer from the context). I think it will add a bit of clarity if the authors simply mention in the notation section that this notation means differentiation w.r.t. the immediate input of the function.\n- Typo on page 9. \"the c-transform (12)\" -> \"the c-transform (11)\"\n- page 10. Instead of \"By definition of Laguerre cells,\" I think the authors really mean \"from (40)\".\n- equation (43) is confusing. As follows from the proof of Lemma 5, the differentiation in (43) is performed only w.r.t. the first argument of $c(x,T_\\psi(x))$. However, in the formula, the differentiation is w.r.t. $x$, which also means differentiation w.r.t. the second argument in this case.\n- equation (54) $\\nabla_x c(g_\\theta(z), y)$. I guess this is the differentiation w.r.t. the first argument.\n- the plots would benefit from axis labels.\n- there is a typo in conclusion: \"not charge\".", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper approaches the problem of generative modeling. Namely, the authors consider the optimal transport formulation of the problem. That is, given the target measure $\\nu$, one tries to minimize the Wasserstein distance\n$$W(\\mu_\\theta,\\nu) = \\inf_{\\pi} \\int c(x,y) d\\pi (x,y),$$\nwhere $\\pi$ is the joint distribution with marginals $\\mu_\\theta$ and $\\nu$, w.r.t. parameters $\\theta$ of the parametric model $\\mu_\\theta$. In the general case, the objective includes entropy regularization, which is the KL-divergence between $d\\pi(x,y)$ and $d\\mu_\\theta(x)\\cdot d\\nu(y)$. Further, the regularized problem is reformulated to the semi-dual formulation (proposed in [1])\n$$W(\\mu_\\theta,\\nu) = \\sup_{\\psi} \\int \\psi^{c,\\lambda}(x) d\\mu_\\theta(x) + \\int\\psi(y)d\\nu(y),$$\nwhere $\\psi$ is a continuous function and $\\psi^{c,\\lambda}$ is its regularized c-transform. Note that the parameter $\\lambda$ is the entropy regularization coefficient.\n\nThe paper's main contribution is the development of rigorous conditions on the differentiability of $W(\\mu_\\theta,\\nu)$ (in the semi-dual formulation) w.r.t. $\\theta$. Besides the theoretical results, the authors study the role of $\\lambda$ and the convergence of the algorithm empirically.\n\nThe theoretical part of the paper is structured as follows. First, the authors give the motivational example for the case when the considered objective is not differentiable (section 2.5). In more details, the authors parameterize the model $\\mu_\\theta$ as a delta-function as point $\\theta$, i.e., $\\delta(x-\\theta)$. Motivated by this example, the authors prove Theorems 3 and 5 for $\\lambda = 0$ (unregularized transport) and $\\lambda > 0$ (regularized transport) correspondingly. The main tool for the proof is the envelope theorem. This theorem defines the differentiability conditions for the function\n$$f(\\alpha) = \\sup_x g(x,\\alpha)$$\nw.r.t. $\\alpha$. After defining the sufficient conditions, the formula for the gradient is obtained simply by the chain rule.\n\nThe empirical study presented in the paper is not an immediate consequence of the theoretical developments. For the generative model $\\mu_\\theta$, the authors consider a neural network, which is then optimized via ADAM using the gradient of the semi-dual formulation. To find the dual function $\\psi$, the authors perform optimization in the inner loop and consider two cases: $\\psi \\in \\mathbb{R}^J$, and $\\psi$ is parameterized by a neural network. Note that in the case $\\psi \\in \\mathbb{R}^J$, this algorithm boils down to the algorithm proposed in [2].\n\n[1] Genevay, Aude, Marco Cuturi, Gabriel Peyré, and Francis Bach. \"Stochastic optimization for large-scale optimal transport.\" Advances in neural information processing systems 29 (2016).\n\n[2] Liu, Dong, Minh Thành Vu, Saikat Chatterjee, and Lars K. Rasmussen. \"Entropy-regularized optimal transport generative models.\" In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3532-3536. IEEE, 2019.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "To address my main concern, I would suggest discussing the practical implications of the established sufficient conditions supported by corresponding empirical study. To be concrete, \n- based on the motivational example (section 2.5) describe which parameterizations of $\\mu_\\theta$ (potentially practical) lead to non-differentiable functions;\n- discuss the x-regularity condition of the cost function giving examples for practitioners;\n- discuss the family of algorithms satisfying the hypothesis $G_\\theta$.\n\nIf some conditions are too strict and since the proposed set of conditions is not a criterion, I would suggest discussing the gap between sufficient and necessary conditions.\n\nI would also suggest fixing the minor issues from the list. However, they are not critical for acceptance.", "broader_impact_concerns": "The paper doesn't discuss the broader impact and doesn't have to, in my opinion.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I think the message of the paper is great. There are several interesting theorems that fill a corner of the literature. My only concern is that the paper size has grown too much after revisions. While this is great to include reviewers' comments, this has the side-effect of diluting further the message of the paper. It feels at times the paper holds a "pot-pourri" of several loosely connected results and remarks. Unfortunately, the criticism of a lack of a unified message was one of the issues highlighted by reviewers.

I also second the reviewers on the relative opacity of what's really brought forward by the experiments. They are all on fairly simple, if not synthetic data, and do not necessarily align with the rest of the paper. The abstract also concludes on a bias issue in experiments using Sinkhorn, but, on the other hand, debiasing is presented as a result in the theory part.

I think it is therefore important that the authors go back to the drawing board and significantly cut the length of the paper. I think going down to 20 pages for the main body would be reasonable, given that the main message of the paper is quite easy to parse. I really believe some areas are worth cutting, or redesigning completely, starting with Figures 3,4,5,6 in the experiment that are barely readable, and all other figures which I find overall poorly executed (legends or axis ticks are not readable). In terms of content, it's not entirely clear to me what Section 5 provides, and the abundance of numbered Remarks does blur the overall message. To what extent should a remark be part of the main message of the paper, rather than a technical side-effect of a result that is proved? Putting them on equal footing makes it quite bad to analyze.

I think that, while I expect items above will require significant work to improve presenation, they are "only" cosmetic, and will mostly involve making editorial choices, which is why I am inclined to accept pending a (not so minor) revision on form.

minor comment:
- "repercuted" (Rk.8) is not an English word
Decision: Accept (poster)