# Trust the Critics: Generatorless and Multipurpose WGANs with Initial
Convergence Guarantees

Tristan Milne1, Étienne Bilocq1, Adrian Nachman1,2
University of Toronto
Dept. of Mathematics1, The Edward S. Rogers Sr. Dept. of Electrical and
Computer Engineering2
tmilne {ebilocq<EMAIL_ADDRESS>
###### Abstract

Inspired by ideas from optimal transport theory we present Trust the Critics
(TTC), a new algorithm for generative modelling. This algorithm eliminates the
trainable generator from a Wasserstein GAN; instead, it iteratively modifies
the source data using gradient descent on a sequence of trained critic
networks. This is motivated in part by the misalignment which we observed
between the optimal transport directions provided by the gradients of the
critic and the directions in which data points actually move when parametrized
by a trainable generator. Previous work has arrived at similar ideas from
different viewpoints, but our basis in optimal transport theory motivates the
choice of an adaptive step size which greatly accelerates convergence compared
to a constant step size. Using this step size rule, we prove an initial
geometric convergence rate in the case of source distributions with densities.
These convergence rates cease to apply only when a non-negligible set of
generated data is essentially indistinguishable from real data. Resolving the
misalignment issue improves performance, which we demonstrate in experiments
that show that given a fixed number of training epochs, TTC produces higher
quality images than a comparable WGAN, albeit at increased memory
requirements. In addition, TTC provides an iterative formula for the
transformed density, which traditional WGANs do not. Finally, TTC can be
applied to map any source distribution onto any target; we demonstrate through
experiments that TTC can obtain competitive performance in image generation,
translation, and denoising without dedicated algorithms.111Code available at
https://github.com/tmilne5/Trust-the-Critics.

##  1 Introduction

Wasserstein GANs (WGANs) were introduced in [2] as a technique for training
generative models using the Wasserstein-1 (or Earth Mover’s) distance as a
measure of dissimilarity between the real and generated distributions. WGANs
consist of two neural networks, a generator and a critic. The generator
$G_{w}$ (with $w$ as its parameters) is applied to a latent probability
distribution $\zeta$ to produce the pushforward measure
$\mu:=(G_{w})_{\\#}\zeta$. Given data sampled from a probability distribution
$\nu$, the critic $u$ is used to measure the discrepancy between $\mu$ and
$\nu$ by computing the Wasserstein-1 distance, given by

$W_{1}(\mu,\nu)=\sup_{u}\mathbb{E}_{x\sim\mu}[u(x)]-\mathbb{E}_{y\sim\nu}[u(y)],$
(1)

where the supremum is computed over all functions $u$ which have a Lipschitz
constant of $1$. It was proposed in [17] to approximately solve this problem
using a gradient penalty on $u$. Given a solution $u_{0}$ to (1) (called a
Kantorovich potential), the generator is then trained by applying gradient
descent to $W_{1}((G_{w})_{\\#}\zeta,\nu)$ over $w$. WGANs have been very
successful, becoming one of the standard benchmarks for high quality image
synthesis [28, 24, 21].

Existing formulations of WGANs do not, however, make full use of the
information contained in a Kantorovich potential. Indeed, it follows from
$L^{1}$ optimal transport theory that $-\nabla u_{0}(G_{w}(z))$, where it
exists, provides the exact direction, if not the distance, in which the
generated image $G_{w}(z)$ should move so as to most rapidly reduce
$W_{1}((G_{w})_{\\#}\zeta,\nu)$. One may ask, then, the extent to which
performing gradient descent on $W_{1}((G_{w})_{\\#}\zeta,\nu)$ over the
parameters $w$ actually obtains this optimal direction at each point
$G_{w}(z)$. In Section 3 of this paper we demonstrate experimentally that
standard generator architectures fail to obtain this optimal direction.

We were thus motivated to resolve this issue and obtain the ideal direction of
flow everywhere by simply modifying the initial distribution by a gradient
descent step on $u_{0}$ with step size $\eta$; that is, to obtain a new
distribution, $\tilde{\mu}$, from the formula

$\tilde{\mu}:=(I-\eta\nabla u_{0})_{\\#}\mu.$ (2)

With $\tilde{\mu}$ now in hand, we next train a new critic solving (1), with
$\tilde{\mu}$ replacing $\mu$, and repeat the process. Given the connection
between the gradients of a Kantorovich potential and the optimal transport
directions, this process should push $\mu$ towards $\nu$.

The selection of the step size $\eta$ is non-trivial, however. If $\eta$ is
too small the algorithm will require many iterations to converge; since a new
critic must be trained after each step, this makes the technique
computationally expensive for any distributions $\mu$ and $\nu$ which are not
close initially. If $\eta$ is too large, then recalling that $-\nabla
u_{0}(x)$ provides the direction but not the distance of the optimal
transport, the gradient step $x\mapsto x-\eta\nabla u_{0}(x)$ may overshoot
the desired target. Ideally, the step size $\eta$ should be derived from the
distance that points should move under the optimal transport. In fact, the
average of this quantity is equal to $W_{1}(\mu,\nu)$. Fortuitously, the value
of $W_{1}(\mu,\nu)$ is available to us at no extra computational cost as a by-
product of computing $u_{0}$ via (1).

Hence, in TTC, we select the step size $\eta$ as some fraction of the current
estimate of $W_{1}(\mu,\nu)$. This allows for large step sizes, but avoids
undesirable overshooting of the targets. In practice, this enables efficient
transformation of $\mu$ to $\nu$ even when they are initially far apart.

In addition, since we have freed $\mu$ from being the output of a generator,
TTC can be applied to map any source distribution $\mu$ onto any target $\nu$.
Thus, various tasks in generative modelling, such as image synthesis,
translation, and denoising, can be completed using TTC, the only requirement
being changing the source and target data. This stands in contrast to the
typical approach, where specialized generator architectures or algorithms are
designed for each task.

The contributions of this paper are as follows:

  1. 1.

We introduce TTC, a novel technique for generative modelling distinguished
from existing algorithms by its adaptive step size selection method.

  2. 2.

We demonstrate quantitatively that standard WGAN architectures fail to move
generated data points in optimal directions over the course of training. This
misalignment is resolved by TTC.

  3. 3.

We provide a formula for the density of the updated measure $\tilde{\mu}$,
assuming $\mu$ has a density, and calculate the exact value of
$W_{1}(\tilde{\mu},\nu)$ in terms of the step size $\eta$ under the assumption
that the minimal transport distance is larger than this step size.

  4. 4.

We prove a geometric convergence rate of a sequence of measures generated
using TTC. Such a result is applicable until the minimal transport distance is
zero, which occurs only when a non-negligible set of synthetic data is
essentially indistinguishable from real data.

  5. 5.

We demonstrate the effectiveness of TTC in practice by showing it generates
more realistic looking images than comparable WGANs, as determined by the
Fréchet Inception Distance (FID) [18].

  6. 6.

Finally, we demonstrate the multipurpose applicability of TTC by showing that,
in addition to image generation, with just a simple change to the source and
target distributions it can be successfully used for image translation as well
as denoising tasks.

The remainder of this paper is structured as follows. Related work is reviewed
in Section 2. Section 3 describes experiments which show a large degree of
misalignment between the optimal transport directions at generated data points
and directions of movement actually obtained when training a generator. In
Section 4.1, we provide some background on $L^{1}$ optimal transport theory
which is necessary to describe our algorithm. The TTC algorithm is defined in
Section 4.2, and we prove convergence results in Section 4.3; detailed proofs
of all mathematical results are included in Appendix A. Section 5.1 describes
an experiment which shows the improved performance of TTC against comparable
WGANs, and Section 5.2 shows the performance of TTC on the task of translating
photographs into paintings in the style of Monet. Section 5.3 points out a
connection between TTC and the adversarial regularization technique of [29],
and demonstrates that TTC has improved performance versus this technique when
applied to an image denoising task. We conclude in Section 6 with a discussion
of TTC’s limitations and potential societal impact.

##  2 Related work

The idea to perform generation without an explicitly parametrized generator,
but instead using the gradients of trained critics or discriminators is not
new. It was applied in [19] and [25] to discriminators trained with the
standard GAN objective [14], and in [27] and [35] to critics trained with the
gradient penalty method from WGANs [17]. Since we also train our critics using
the gradient penalty method, we will compare our work to [27] and [35]. In
[27] generation of new samples is performed by applying Adam [22] with added
noise to learned critics. Iterations are halted based on a heuristic stopping
condition depending on a random number selected between the minimum and
maximum value of the critic on the target samples. This method is not directly
connected to the optimal transport problem and consequently has no convergence
guarantees. In contrast, our technique applies a simple gradient descent step
which is motivated by the concept of transport rays from $L^{1}$ optimal
transport theory; this connection allows us to provide exact initial
convergence rates for TTC. Moreover, the size of our step is proportional to
the current estimate of the Wasserstein-1 distance, whereas in [27] it is a
small constant; at the start of training our step size can be quite large,
which leads to fast convergence at no cost to the quality of generated
samples. We also show superior performance of TTC as compared to WGANs for a
fixed generator and critic architecture on three standard datasets, which was
not achieved in [27]. On the other hand, [27] is able to obtain reasonably
good performance using only four critic networks, which is more efficient than
our technique.

The work in [35] contains novel qualitative insights regarding functional
gradient descent, and suggests that explicitly parametrized generators in
standard WGANs may be unable to correctly follow the gradients of the critics.
We had similar insights, and our experimental results in Section 3 provide
quantitative evidence for these claims by showing that the actual directions
in which generated data move during training are far from the ideal ones. The
authors of [35] also use a constant step size for the gradient descent, and do
not prove that their technique reduces the Wasserstein-1 distance. The
application of their algorithm is to fine-tune pre-trained WGAN generators,
possibly because their choice of constant step size leads to long computation
times when the source and target are not already close. While the fine-tuning
of pre-trained generators is a valuable idea, our adaptive step size is large
when the Wasserstein-1 distance between source and target distributions is
large, and so we do not have these issues.

Consequently, our generation scheme is applicable to any source distribution
(_i.e_. not necessarily one produced by a pre-trained generator). This allows
us to apply our technique not only to image generation, but to image
translation and denoising as well; similar flexibility was demonstrated for a
different technique in [25]. Because of this flexibility, we speculate that
our technique is applicable to more than just imaging problems.

In Section 5.3 we point out a connection between our work and an adversarial
regularization technique for inverse problems in [29]. In particular, we show
that under certain conditions the implicit reconstruction technique used in
[29] is equivalent to a single step of TTC. While our paper was in development
we learned of the recent paper [34], which contains, in a similar fashion to
our work, iterations of the implicit technique in [29]. Our work complements
that of [34], since we study distinct generative modelling problems and
provide an explicit reconstruction technique (as opposed to an implicit one
specified by a variational problem) coupled with a proof of initial
convergence obtained from $L^{1}$ optimal transport. Furthermore, [34] is
devoted to a more general class of inverse problems than our denoising
example, and we see an extension of our theory to their setting to be an
interesting avenue for future work.

There has been a profusion of recent papers applying concepts from optimal
transport to generative modelling [6, 10, 12, 13, 33, 36, 40], some of which
have convergence results. These publications tend to focus on optimal
transport settings distinct from ours which are typically more amenable to
analysis, such as the case where the cost function is the square Euclidean
distance [10, 12, 36], or where the cost function is regularized by entropy
[40]. To our knowledge, our initial convergence results are unique in the
$L^{1}$ optimal transport setting relevant to WGANs.

Finally, let us point out that the quality of our generated images, while
better than comparable WGANs, is not comparable to the state of the art
(_e.g_. [20]). However, the intent of the present paper is to focus on
fundamental issues arising in adversarial approaches to generative modelling.
Given the observed improved performance versus comparable WGANs, it will be
interesting to apply TTC with state of the art discriminator architectures,
but this is outside the scope of the current paper.

##  3 Misalignment of data movement

Given a Kantorovich potential $u_{0}$ for a generated distribution
$\mu=(G_{w})_{\\#}\zeta$ and a target distribution $\nu$, the optimal
direction of movement for a generated sample $G_{w}(z)$ is provided by the
gradient $-\nabla u_{0}(G_{w}(z))$. When training a WGAN generator, however,
the movement of generated samples is ruled by the gradient descent algorithm
used to minimize $W_{1}((G_{w})_{\\#}\zeta,\nu)$ in terms of $w$. A standard
gradient descent step will update $w$ in the direction of

$\displaystyle-\nabla_{w}W_{1}(($ $\displaystyle
G_{w})_{\\#}\zeta,\nu)=-\nabla_{w}\mathbb{E}_{(G_{w})_{\\#}\zeta}[u_{0}],$ (3)
$\displaystyle=-\mathbb{E}_{\tilde{z}\sim\zeta}\left[D_{w}G_{w}^{T}(\tilde{z})\nabla
u_{0}(G_{w}(\tilde{z}))\right].$ (4)

When the expectation is calculated by averaging over a random mini-batch
$\\{z_{i}\\}_{i=1}^{M}$ (_i.e_. when using stochastic gradient descent), this
leads to movement of a generated sample $G_{w}(z)$ parallel to

$-D_{w}G_{w}(z)\left(\frac{1}{M}\sum_{i=1}^{M}D_{w}G_{w}^{T}(z_{i})\nabla
u_{0}(G_{w}(z_{i}))\right).$ (5)

In this section we present our results on the misalignment between this
expression and $-\nabla u_{0}(G_{w}(z))$.

We computed the cosines of the angles between vectors of the form (5) and
$-\nabla u_{0}(G_{w}(z))$ at randomly generated samples $G_{w}(z)$ and at
various stages throughout the training of a WGAN generator, using mini-batches
$\\{z_{i}\\}_{i=1}^{M}$ drawn separately from $z$. The critic network used to
approximate $u_{0}$ was trained using the one sided gradient penalty from
[17]. The experiment was run on the MNIST dataset using both the InfoGAN
architecture ([5], which we selected since it was also used in the large-scale
study [28]) and the DCGAN architecture [38] for comparison. We used the batch
size $M=128$. The results are summarized in Table 1, and histograms of the
cosine values obtained are provided in Appendix B.1. The results clearly
demonstrate that the movement of generated samples during WGAN training is not
well aligned with the optimal directions provided by the Kantorovich
potential. This discrepancy tends to increase as training goes on, to the
point where negative cosine values (denoting undesirable movement in a
direction along which $u_{0}$ increases) are obtained for a non-negligible
portion of the generated samples, which may help explain why a generator can
stop improving before the generated distribution is sufficiently close to the
target. Table 1 also presents the performance of the generators as indicated
by the FID. The InfoGAN generator obtained higher cosine values and lower FIDs
than the DCGAN generator, suggesting that better alignment throughout training
correlates with better performance. In Appendix B.1, we also include a similar
experiment describing the misalignment obtained when replacing (5) by updates
computed with Adam.

Stage in training | InfoGAN | DCGAN
---|---|---
Early | $0.488\pm 0.071$ | $0.441\pm 0.075$
| ($410.4\pm 9.0$) | ($414.3\pm 26.8$)
Mid | $0.150\pm 0.080$ | $0.086\pm 0.081$
| ($22.9\pm 0.5$) | ($40.8\pm 7.1$)
Late | $0.100\pm 0.070$ | $0.085\pm 0.081$
| ($21.8\pm 0.4$) | ($31.1\pm 1.8$)
Table 1: Misalignment cosine measurements. All results are reported in the
form mean $\pm$ standard deviation. The top lines show the statistics of the
cosines of the angles between (5) and $-\nabla u_{0}(G_{w}(z))$, computed over
the training of five separate initializations of each model, each with 256
randomly sampled noise inputs $z$. The statistics appearing in parentheses are
for FID values computed over the five training runs. The values were computed
at three different stages in training, with the late stage chosen such that
the generators were close to the best performance obtained, but still
improving slightly.

##  4 The TTC algorithm

###  4.1 Background on $L^{1}$ optimal transport theory

Here we will summarize the necessary background from $L^{1}$ optimal
transport; for more details, see, for instance, [41]. Let
$\Omega\subset\mathbb{R}^{d}$ be a compact convex set representing the space
of images with $c$ colour channels and $h\times w$ pixels per channel (i.e.
$d=c\times h\times w$). Let $\mu,\nu$, the source and target, respectively, be
in $\mathcal{P}(\Omega)$, the space of probability distributions on $\Omega$.
The $L^{1}$ optimal transport problem is the problem of finding a map
$T:\Omega\rightarrow\Omega$ mapping $\mu$ onto $\nu$ while minimizing the
average Euclidean travel distance. Formally, it is

$\min_{T_{\\#}\mu=\nu}\int_{\Omega}|x-T(x)|d\mu,$ (6)

where the constraint $T_{\\#}\mu=\nu$ specifies that the pushforward measure
$T_{\\#}\mu$, defined by the equality

$T_{\\#}\mu(E)=\mu(T^{-1}(E)),$ (7)

agrees with $\nu$. A solution $T_{0}$ to (6) is called an optimal transport
map for the pair $(\mu,\nu)$, and the existence of such a map can be
guaranteed by the assumption that $\mu$ has a density with respect to Lebesgue
measure on $\mathbb{R}^{d}$, an assumption we will denote with the notation
$\mu\ll\mathcal{L}_{d}$ (see, for example, Theorem 3.18 in [41]).

In general the existence of an optimal map $T_{0}$ is difficult to prove. In
the Kantorovich relaxation of (6), one instead minimizes over probability
distributions $\gamma\in\mathcal{P}(\Omega\times\Omega)$ with marginals given
by $\mu$ and $\nu$. Formally, we write this as

$\displaystyle\min_{\gamma\in\Pi(\mu,\nu)}$
$\displaystyle\int_{\Omega\times\Omega}|x-y|d\gamma,$ (8)
$\displaystyle\Pi(\mu,\nu):=\\{\gamma\in\mathcal{P}(\Omega\times\Omega)$
$\displaystyle\mid(\pi_{x})_{\\#}\gamma=\mu,(\pi_{y})_{\\#}\gamma=\nu\\}.$ (9)

Here $\pi_{x}(x,y)=x$, and $\pi_{y}(x,y)=y$ are the projection maps, and
$\Pi(\mu,\nu)$ is called the set of admissible plans. The value of the
minimization problem in (8) is written $W_{1}(\mu,\nu)$ and is called the
Wasserstein-1 distance between $\mu$ and $\nu$.

Under certain conditions (see Section 1.5 of [41]) the values of problems (6)
and (8) agree. The existence of an optimal map is typically shown starting
from Kantorovich Duality, which asserts that the optimal values in (1) and (8)
are the same. The relationship between a Kantorovich potential $u_{0}$ and an
optimal map $T_{0}$ is well known (_e.g_. [8, 17]) but we include a statement
of it for completeness.

######  Lemma 1.

Let $\mu\ll\mathcal{L}_{d}$, $u_{0}$ be a Kantorovich potential and $T_{0}$ be
an optimal map for the pair $(\mu,\nu)$. Then $\mu$-almost everywhere,

$x\neq T_{0}(x)\Rightarrow-\nabla u_{0}(x)=\frac{T_{0}(x)-x}{|T_{0}(x)-x|}.$
(10)

Equation (10) implies that given a step size $\eta_{0}$, if we were to apply
the map

$f_{0}(x)=x-\eta_{0}\nabla u_{0}(x),$ (11)

then as long as $\eta_{0}$ is less than the minimal transport length we can be
assured that under $f_{0}$ all points $x$ move towards their targets
$T_{0}(x)$ without overshooting them, and thus we can expect that
$W_{1}((f_{0})_{\\#}\mu,\nu)$ will be less than $W_{1}(\mu,\nu)$. This
observation forms the basis for our algorithm, which we will describe in the
next section.

###  4.2 The algorithm

We now define the TTC algorithm. Set $\mu_{0}:=\mu$, and define, for
$n=1,2\ldots$

$\mu_{n}=(f_{n-1})_{\\#}\mu_{n-1},$ (12)

where $f_{n-1}$ is as in (11), but with $u_{0}$ replaced by a Kantorovich
potential $u_{n-1}$ for the pair $(\mu_{n-1},\nu)$. To compute such a
Kantorovich potential we train standard critic neural networks from the
literature using the one sided gradient penalty from [17], which was found to
provide more stable training [37]. In order to use this technique it is
necessary to be able to sample both $\mu_{n}$ and $\nu$. For $\mu_{n}$, we
draw an initial point $x_{0}$ from $\mu_{0}$, and apply gradient descent maps
from the sequence of pre-trained critics. Precisely, a sample $x\sim\mu_{n}$
is obtained via the formula

$x=(I-\eta_{n-1}\nabla u_{n-1})\circ\ldots\circ(I-\eta_{0}\nabla
u_{0})(x_{0}).$ (13)

Note that in light of (13), we can view TTC as building up a generator layer
by layer using the gradients of the critics, as in [35].

We choose the step size via

$\eta_{n}=\theta W_{1}(\mu_{n},\nu),$ (14)

where $\theta\in(0,1)$ is a hyperparameter. We note again that the value of
$W_{1}(\mu_{n},\nu)$ is available as a by-product of computing a Kantorovich
potential, so this choice of adaptive step size requires no extra computation
in practice. More precisely, we use the negative of the minimal value of the
functional from WGAN-GP [17], that is

$W_{1}(\mu_{n},\nu)\approx\frac{1}{M}\sum_{j=1}^{M}u_{n}(x_{j})-u_{n}(y_{j})-\lambda(|\nabla
u_{n}(\tilde{x}_{j})|-1)_{+}^{2},$ (15)

where the $x_{j}$ and $y_{j}$ are samples from $\mu_{n}$ and $\nu$
respectively, $M$ is the mini-batch size, $\tilde{x}_{j}$ is a random convex
combination of $x_{j}$ and $y_{j}$ as in [17] and $(z)_{+}=\max(0,z)$. When
training WGANs, researchers will typically use $\lambda=10$ for the gradient
penalty coefficient [17, 29, 34], however we use a value of $\lambda=1000$. In
practice we found that this value of $\lambda$ stabilizes the estimates of
$W_{1}(\mu_{n},\nu)$ and the training of TTC; using smaller values of
$\lambda$ leads to inflated estimates of $W_{1}(\mu_{n},\nu)$, leading to
overly large step sizes and unstable training. This is confirmed by the recent
analysis in [30], which shows that at best the value in (15), in expectation,
converges to $W_{1}(\mu_{n},\nu)$ like $O(\lambda^{-1})$.

Depending on the mini-batch size $M$ the value of (15) can vary considerably
across mini-batches, so we compute an average over the last $100$ mini-batches
used to train the critic $u_{n}$. The method for training TTC is summarized in
Algorithm 1.

Data: Samples from source $\mu$ and target $\nu$, untrained critics
$(u_{n})_{n=0}^{N-1}$ with parameters $(w_{n})_{n=0}^{N-1}$, gradient penalty
coefficient $\lambda$, number of critic iterations $C$, batch size $M$, Adam
parameters $(\epsilon_{c},\beta_{1},\beta_{2})$.

Result: A distribution $\mu_{n}$ which can be sampled from $\mu$,
$(u_{n})_{n=0}^{N-1},(\eta_{n})_{n=0}^{N-1}$ via (13).

for  _$n\in\\{0,\ldots,N-1\\}$_ do

for  _$i\in\\{1,\ldots,C\\}$_ do

for  _$j\in\\{1,\ldots,M\\}$_ do

Sample $x_{j}\sim\mu_{0}$, $y_{j}\sim\nu$, $t_{j}\sim U([0,1])$;

for  _$k\in\\{0,\ldots,n-1\\}$_ do

$x_{j}\leftarrow x_{j}-\eta_{k}\nabla u_{k}(x_{j})$;

end for

$\tilde{x}_{j}\leftarrow(1-t_{j})x_{j}+t_{j}y_{j}$;

$L_{ij}\leftarrow u_{n}(y_{j})-u_{n}(x_{j})$

$\hskip 28.90755pt+\lambda(|\nabla u_{n}(\tilde{x}_{j})|-1)_{+}^{2}$;

end for

$L_{i}\leftarrow\frac{1}{M}\displaystyle{\sum_{j=1}^{M}}L_{ij}$ ;

$w_{n}\leftarrow\text{Adam}(L_{i},\epsilon_{c},\beta_{1},\beta_{2})$ ;

end for

$\eta_{n}\leftarrow\frac{-\theta}{100}\displaystyle{\sum_{i=C-99}^{C}}L_{i}$;

end for

Algorithm 1 TTC Training

###  4.3 Convergence results for TTC

In this section we will provide guarantees that up to some iterate,
$W_{1}(\mu_{n},\nu)$ decreases with geometric rate determined by $\theta$.
Detailed proofs for all mathematical results can be found in Appendix A.

Let $u_{n}$ be a Kantorovich potential for the pair $(\mu_{n},\nu)$. Since
$u_{n}$ is Lipschitz continuous, $\nabla u_{n}$ is a priori only defined
almost everywhere. To provide a convergence analysis, it is convenient to
extend $f_{n}$ to the negligible set where $u_{n}$ is not differentiable via
the formula

$f_{n}(x):=\begin{cases}x-\eta_{n}\nabla u_{n}(x)&\quad{\text{ if }\nabla
u_{n}(x)\text{ exists}},\\\ x&\quad\text{ else.}\end{cases}$ (16)

We emphasize that this extension does not affect the definition of the
measures $\mu_{n}$ as long as they have densities, which we will prove up to a
certain iterate. In order to state our main results we first need to define
the minimal transportation length in an appropriate way.

######  Definition 1.

For $\mu,\nu\in\mathcal{P}(\Omega)$, $\mu\ll\mathcal{L}_{d}$, let $T_{0}$ be
an optimal transport map for the pair $(\mu,\nu)$. Set

$\displaystyle\ell_{0}(T_{0})$ $\displaystyle:=\text{essinf}_{\mu}|I-T_{0}|,$
(17)
$\displaystyle=\sup\\{\ell\in\mathbb{R}\mid\mu\left(\\{x\in\Omega\mid|x-T_{0}(x)|<\ell\\}\right)=0\\}.$
(18)

Our first theorem gives precise information on the effects of one iteration of
TTC.

######  Theorem 1.

Suppose that $\mu\ll\mathcal{L}_{d}$ and let $u_{0}$ be a Kantorovich
potential for the pair $(\mu,\nu)$. Set $\tilde{\mu}=(f_{0})_{\\#}\mu$ where
$f_{0}$ is defined in (16). Let $T_{0}$ be an optimal transport map for the
pair $(\mu,\nu)$. If

$\eta_{0}<\ell_{0}(T_{0}),$ (19)

then

  1. i.

$u_{0}$ is a Kantorovich potential for the pair $(\tilde{\mu},\nu)$,

  2. ii.

$W_{1}(\tilde{\mu},\nu)=W_{1}(\mu,\nu)-\eta_{0}$,

  3. iii.

With $g_{0}:\Omega\rightarrow\mathbb{R}^{d}$ defined by

$g_{0}(x)=\begin{cases}x+\eta_{0}\nabla u_{0}(x)&\quad{\nabla u_{0}(x)\text{
exists}},\\\ x&\quad\text{else,}\end{cases}$ (20)

then $T_{1}:=T_{0}\circ g_{0}$ is an optimal map for the pair
$(\tilde{\mu},\nu)$ and

$\ell_{0}(T_{1})\geq\ell_{0}(T_{0})-\eta.$ (21)

  4. iv.

$\tilde{\mu}$ has density $\tilde{\rho}$ satisfying, for $\mu$ almost all $x$,

$\tilde{\rho}(f_{0}(x))=\rho(x)|Dg_{0}(f_{0}(x))|,$ (22)

where $\rho(x)$ is the density for $\mu$.

We now iterate Theorem 1 (specifically part ii) to obtain our convergence
results. In view of (19), this requires that $\eta_{n}$ is less than the
minimal transportation length for the pair $(\mu_{n},\nu)$. Recalling the
definition of $\eta_{n}$ (see (14)) and that $W_{1}(\mu_{n},\nu)$ is the mean
transportation length according to $\mu_{n}$ (see (6)), we see that $\eta_{n}$
will satisfy this requirement provided the transport distances are clustered
around the mean and $\theta$ is small enough.

More precisely, the next theorem shows that up to an iterate which is
determined by the ratio $\ell_{0}(T_{0})/W_{1}(\mu,\nu)$, which measures the
clustering of the transport distances around the mean, the sequence
$(\mu_{n})_{n=0}^{\infty}$ converges to $\nu$ at a geometric rate.

######  Theorem 2.

Let $T_{0}$ be an optimal transport map for the pair $(\mu,\nu)$. The measure
$\mu_{n}$ defined iteratively by (12) satisfies

$W_{1}(\mu_{n},\nu)=(1-\theta)^{n}W_{1}(\mu,\nu)$ (23)

for all $n\in\\{0,\ldots,N(\theta)\\}$, where

$N(\theta)=\lceil\log_{1-\theta}\left(1-\ell_{0}(T_{0})/W_{1}(\mu_{0},\nu)\right)\rceil-1,$
(24)

where $\lceil\cdot\rceil$ denotes the ceiling function. In particular, if
$\ell(T_{0})<W_{1}(\mu,\nu)$, then

$W_{1}(\mu_{N(\theta)},\nu)\leq\frac{W_{1}(\mu,\nu)-\ell_{0}(T_{0})}{1-\theta}.$
(25)

Theorem 25 gives us precise knowledge of $W_{1}(\mu_{n},\nu)$ up until
$n=N(\theta)$. At this point the convergence rate ceases to apply because the
step size $\eta_{N(\theta)}$ will exceed the current minimal transport length.
In principle, we may then reduce $\theta$ until the step is small enough and
resume iterations. In practice, however, this is difficult because the minimal
transport length is unknown. Further, we found that a constant value of
$\theta$ was sufficient to produce high quality results. Note that if no
positive value of $\theta$ will make the current step size less than the
minimal transport length, then this length must be zero, so a non-negligible
set of generated data is essentially indistinguishable from real data.

Let us also observe that according to Theorem 1, the initial $u_{0}$ will be a
Kantorovich potential for the pair $(\mu_{n},\nu)$ until $\eta_{n}$ is larger
than the minimal transport distance for that pair, and hence could be re-used
as the critic. In the TTC algorithm, however, we train a new critic at each
step. This is for two reasons. First, since the minimal transport distance is
unknown to us, it would be difficult to know when we should begin re-training
$u_{0}$. Second, since $u_{0}$ is parametrized by a neural network, it may not
be precisely equal to the ideal Kantorovich potential. Motivated by Theorem 1,
however, we initialize the parameters of $u_{n}$ at the parameters of the
preceding critic $u_{n-1}$, which we found leads to improved performance.

##  5 Experiments

We apply TTC to image generation, translation, and denoising. Regarding image
generation, we test TTC against WGAN-GP for a fixed generator and
discriminator on three standard datasets and show that TTC produces more
realistic images, as measured by lower FID. We then apply TTC to the
translation of photographs to Monet paintings using the datasets in [45]. We
finish with an application of TTC to image denoising inspired by [29].

###  5.1 Comparison to WGAN-GP

As a first experiment we compare TTC to WGAN-GP on the tasks of generating the
MNIST [26], FashionMNIST (abbreviated here as F-MNIST) [44], and CIFAR-10 [23]
datasets. We select the InfoGAN architecture [5] for our generator and
discriminator. We train each generative technique for a fixed number of
minibatches of training data (100,000 for MNIST/F-MNIST, and 200,000 for
CIFAR-10). In order to have a fair starting point, when training TTC we
initialize the source distribution $\mu_{0}$ to be the output of the
corresponding untrained generator from WGAN-GP; thus, the initial FIDs for
both techniques are equal when given the same initialization. We also run a
similar experiment for TTC that uses the standard normal distribution on
$\mathbb{R}^{d}$ as the source $\mu_{0}$. The hyperparameters for TTC and
WGAN-GP for each experiment are summarized in Table 2. Where possible, the
same hyperparameters are used for both techniques. Important exceptions to
this are $\theta$ and $\epsilon_{g}$ (the generator learning rate) which are
specific to TTC and WGAN-GP, respectively, and strongly impact performance.
Both of these hyperparameters are optimized via a grid search for each
dataset, and the best performing value is used for all experiments. For all
datasets and algorithms we measure performance by calculating the FID using a
PyTorch implementation [42] every $n$ minibatches ($n=10{\small,}000$ for
MNIST/F-MNIST, and $n=20{\small,}000$ for CIFAR-10). FIDs are computed by
generating a set of $10{\small,}000$ images and comparing these to the
standard test set from each dataset. Both techniques are trained using five
random initializations, and the average values of the best FID over each
training run are recorded in Table 3. Some examples of generated images are
given in Appendix B.2.

Dataset | TTC | WGAN-GP
---|---|---
| $N$ | $C$ | $\theta$ | $\epsilon_{g}$
MNIST | $20$ | $5000$ | $0.9$ | $0.001$
F-MNIST | $20$ | $5000$ | $0.9$ | $0.001$
CIFAR-10 | $40$ | $5000$ | $0.9$ | $0.0005$
Table 2: Experimental setup for comparing WGAN-GP to TTC. The symbols $\epsilon_{c},\epsilon_{g}$ represent the learning rates of the critic and generator, respectively. The values of the parameters in Algorithm 1 were taken to be $\lambda=1000,M=50,\epsilon_{c}=0.0001,\beta_{1}=0.5,\beta_{2}=0.999$ for all experiments and both techniques. Note that twice as many critics are used for CIFAR-10 experiments on TTC since twice as many minibatches of training are available. Dataset | WGAN-GP | TTC 1 | TTC 2
---|---|---|---
MNIST | $20.9\pm 0.6$ | $19.0\pm 1.5$ | $\mathbf{18.0}\pm 0.3$
F-MNIST | $26.9\pm 1.6$ | $22.2\pm 0.7$ | $\mathbf{22.1}\pm 0.5$
CIFAR-10 | $29.2\pm 0.7$ | $28.7\pm 0.6$ | $\mathbf{27.3}\pm 0.6$
Table 3: Best FIDs obtained over the course of training for WGAN-GP and TTC.
TTC 1 uses an untrained generator to create the source $\mu_{0}$, while TTC 2
starts from a standard normal distribution on $\mathbb{R}^{d}$. The FIDs are
reported as mean $\pm$ standard deviation, with statistics computed over five
training runs. TTC reliably produces better FID values than WGAN-GP for all
datasets; the improvement is magnified when using the standard normal
distribution on $\mathbb{R}^{d}$ as $\mu_{0}$.

###  5.2 Image translation

By simply changing the source and target distributions we can use TTC for
image translation. We demonstrate this here using datasets from [45].
Specifically, we used their Photograph dataset as $\mu_{0}$, rescaled to have
$h=w=128$, and used their Monet dataset as $\nu$, with each target image taken
as a random crop of a Monet painting with $h=w=128$. Since the InfoGAN
discriminator we used in Section 5.1 is not appropriate for images of this
size, here we choose the SNDCGAN discriminator from [24] (see also [31]).

Besides making $N=30$ and $M=16$ the hyperparameters for this application are
exactly the same as in Table 2. An example photograph $x_{0}$ and the result
of applying (13) to it with $n=30$ is given in Figure 1; additional examples
can be found in Appendix B.3.

Figure 1: An example of TTC applied to translating landscape photos into Monet
paintings.

###  5.3 Image denoising

To further demonstrate the multipurpose flexibility of TTC, we apply it to
restore images that have been corrupted with Gaussian noise. Specifically, we
follow the experimental framework of [29], where $\nu$ consists of random
crops of the BSDS500 dataset [1], and $\mu_{0}$ is $\nu$ corrupted by adding
i.i.d. Gaussian noise with standard deviation $\sigma$. In this setting TTC
bears an interesting relation to [29]. In that paper a critic $u_{0}$ is
obtained using the method from [17] for the pair $(\mu_{0},\nu)$, which is
then used as a learned regularizer in an inverse problem. This is applied to
image restoration in the following way; given a noisy observation $x_{0}$, a
denoised version is obtained by solving the minimization problem

$\min_{x\in\Omega}\frac{1}{2}|x-x_{0}|^{2}+\eta u_{0}(x),$ (26)

where the parameter $\eta$ is estimated from the noise statistics.
Incidentally, this requires the noise model to be known a priori, as in [32];
as we will see, TTC requires no such model since the corresponding step size
parameter is estimated with $\theta W_{1}(\mu,\nu)$. The next proposition
shows that provided $\eta$ is small enough the solution to (26) is equivalent
to the solution obtained from a single step of TTC with step size $\eta$. As
such, in this context TTC can be thought of as an iterated form of the
technique in [29], where the critic is updated after each reconstruction step.

######  Proposition 1.

Let $T_{0}$ be an optimal transport map for the pair $(\mu,\nu)$. If
$\eta<\ell_{0}(T_{0})$, then for $\mu$-almost all $x_{0}$ there is a unique
solution to (26) given by

$x_{1}=x_{0}-\eta\nabla u_{0}(x_{0}).$ (27)

For a fair comparison of our results against the denoising technique in [29]
we use a discriminator from [29] for this application. For TTC’s
hyperparameters, we use $N=20$, $M=16$ and $\theta=0.7$, with all other
hyperparameters as given in Table 2; interestingly, we found in this case that
the performance is quite insensitive to variations in $\theta$. Table 4 shows
mean PSNR values over a set of 128x128 crops from a held out test set from
BSDS500 with 200 images. Figure 2 shows one denoised example; additional
examples are in Appendix B.4. Though our PSNR values are somewhat lower than
the state of the art (_e.g_. [32]), we feel that our results are impressive
given that we use unpaired data, we have no noise model, and that our
technique was not specifically designed for image denoising.

| Average PSNR (dB)
---|---
$\sigma$ | Noisy Image | Adv. Reg. [29] | TTC
0.1 | $20.0\pm 0.03$ | $27.1\pm 0.7$ | $\mathbf{29.9}\pm 2.2$
0.15 | $16.5\pm 0.03$ | $24.6\pm 0.7$ | $\mathbf{27.9}\pm 2.3$
0.2 | $14.0\pm 0.03$ | $22.9\pm 0.6$ | $\mathbf{26.4}\pm 2.4$
Table 4: Results for denoising experiments. PSNR values are reported as mean
$\pm$ standard deviation, where the statistics are computed over the test set.
In addition to having higher mean performance over the test set, TTC gives an
improved PSNR for every image in the test set. Figure 2: A single restored
image from BSDS500 from noise level $\sigma=0.15$. From left to right:
original image, noisy image (PSNR = 16.4), restored image using [29] (PSNR =
24.5), restored image using TTC (PSNR = 27.0).

##  6 Discussion and conclusion

###  6.1 Discussion of limitations and societal impact

In this section we will discuss the limitations and potential societal impact
of our contribution. To start with, our theoretical analysis relies on being
able to compute a Kantorovich potential $u_{0}$ for the pair $(\mu,\nu)$.
Given recent results in [30] showing that the optimization problem for
learning critics from [17] actually returns a function that solves a congested
transport problem, which is distinct from a Kantorovich potential, one may ask
to what extent our theoretical analysis applies to the types of critics
learned in practice. The distinction between these problems decreases as
$\lambda$ gets large, so we suspect that our assumption of being able to
compute a Kantorovich potential is reasonable for the $\lambda$ value we used
($\lambda=1000$), but this is certainly something to consider, especially for
the smaller values of $\lambda$ typically used in the literature.

Disadvantages of TTC are its memory and time complexity, which are $O(N)$ and
$O(N^{2})$, respectively. Nevertheless, standard critic architectures in WGANs
are typically simpler than their corresponding generators, so TTC can be
faster than traditional WGANs for low $N$. In fact, we were able to generate
high quality images in comparable time to WGANs without implementing ideas to
reduce the time and memory complexity.

TTC has outperformed WGANs in our experiments. However, given the results of
[28] showing that with enough hyperparameter optimization and random restarts
many generative models achieve comparable performance to each other, it would
be interesting to test whether the same trend holds for TTC versus WGANs.

In terms of societal impact, since we have demonstrated that TTC improves upon
the performance of WGANs, in principle it may be used to generate more
convincing deep-fakes, which pose a serious threat to the integrity of
information online. Though we are not experts in the detection of deep-fakes,
we can speculate that the understanding of the training process furnished by
our theoretical results may help the detection of fake data generated with
TTC.

###  6.2 Conclusion

In this paper we have introduced TTC, a new algorithm for generative
modelling. This was motivated in part by our observation that the directions
in which the training of WGANs moves generated data are misaligned with the
ideal directions given by a trained critic. TTC resolves this issue by
dispensing with the generator altogether. We then presented a convergence
analysis for TTC which applies until the algorithm produces a non-negligible
set of high-quality data. As well, we presented experiments successfully
applying our algorithm to image generation, translation, and denoising,
illustrating the multipurpose nature of TTC.

Furthermore, we provided an explicit formula for the updated density of $\mu$,
which is characteristic of normalizing flows [7, 39, 4, 15]. A trade-off
between sample quality and density estimation is often discussed in the
literature [16, 43]. Since TTC generates high quality samples and has an
iterative formula for the density, it may help to bridge this gap.

### Acknowledgements

This research was supported in part by the NSERC Discovery Grant RGPIN-06329
and a University of Toronto Doctoral Completion Award. Experiments were run on
the Graham and Narval clusters of Compute Canada.

## References

  * [1] Pablo Arbelaez, Michael Maire, Charless Fowlkes, and Jitendra Malik.  Contour detection and hierarchical image segmentation.  IEEE transactions on pattern analysis and machine intelligence, 33(5):898–916, 2010.
  * [2] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In International Conference on Machine Learning, pages 214–223. PMLR, 2017.
  * [3] Luis Caffarelli, Mikhail Feldman, and Robert McCann.  Constructing optimal maps for monge’s transport problem as a limit of strictly convex costs.  Journal of the American Mathematical Society, 15(1):1–26, 2002\.
  * [4] Ricky T. Q. Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud.  Neural ordinary differential equations.  In Advances in Neural Information Processing Systems, volume 31, page 6572–6583, 2018.
  * [5] Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel.  Infogan: Interpretable representation learning by information maximizing generative adversarial nets.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2180–2188, 2016.
  * [6] Biwei Dai and Uros Seljak.  Sliced iterative normalizing flows.  In ICML, 2021.
  * [7] Laurent Dinh, David Krueger, and Yoshua Bengio.  NICE: Non-linear independent components estimation.  arXiv preprint arXiv:1410.8516, 2014.
  * [8] Lawrence C Evans and Wilfrid Gangbo.  Differential equations methods for the Monge-Kantorovich mass transfer problem.  Number 653. American Mathematical Soc., 1999.
  * [9] Herbert Federer.  Geometric measure theory.  Springer, 2014.
  * [10] Chris Finlay, Jörn-Henrik Jacobsen, Levon Nurbekyan, and Adam M. Oberman.  How to train your neural ODE: the world of jacobian and kinetic regularization.  In ICML, pages 3154–3164, 2020.
  * [11] David Heaver Fremlin.  Measure theory, volume 2.  Torres Fremlin, 2000.
  * [12] Yuan Gao, Jian Huang, Yuling Jiao, Jin Liu, Xiliang Lu, and Zhijian Yang.  Deep generative learning via Euler particle transport.  Proceedings of Machine Learning Research vol, 145:1–33, 2021.
  * [13] Yuan Gao, Yuling Jiao, Yang Wang, Yao Wang, Can Yang, and Shunkang Zhang.  Deep generative learning via variational gradient flow.  In International Conference on Machine Learning, pages 2093–2101. PMLR, 2019.
  * [14] Ian 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 Information Processing Systems, pages 2672–2680, 2014.
  * [15] Will Grathwohl, Ricky TQ Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud.  FFJORD: Free-form continuous dynamics for scalable reversible generative models.  arXiv preprint arXiv:1810.01367, 2018.
  * [16] Aditya Grover, Manik Dhar, and Stefano Ermon.  Flow-GAN: Combining maximum likelihood and adversarial learning in generative models.  In AAAI, 2018.
  * [17] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of Wasserstein GANs.  In Advances in Neural Information Processing Systems, pages 5767–5777, 2017.
  * [18] Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  GANs trained by a two time-scale update rule converge to a local nash equilibrium.  In Advances in Neural Information Processing Systems, volume 30, page 6626–6637, 2017.
  * [19] Rie Johnson and Tong Zhang.  Composite functional gradient learning of generative adversarial models.  In International Conference on Machine Learning, pages 2371–2379. PMLR, 2018.
  * [20] Tero Karras, Miika Aittala, Janne Hellsten, Samuli Laine, Jaakko Lehtinen, and Timo Aila.  Training generative adversarial networks with limited data.  In Advances in Neural Information Processing Systems, volume 33, pages 12104–12114, 2020.
  * [21] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4401–4410, 2019.
  * [22] Diederik Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In International Conference on Learning Representations, 12 2014\.
  * [23] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  2009\.
  * [24] Karol Kurach, Mario Lučić, Xiaohua Zhai, Marcin Michalski, and Sylvain Gelly.  A large-scale study on regularization and normalization in GANs.  In International Conference on Machine Learning, pages 3581–3590. PMLR, 2019.
  * [25] Justin Lazarow, Long Jin, and Zhuowen Tu.  Introspective neural networks for generative modeling.  In Proceedings of the IEEE International Conference on Computer Vision, pages 2774–2783, 2017.
  * [26] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [27] Kwonjoon Lee, Weijian Xu, Fan Fan, and Zhuowen Tu.  Wasserstein introspective neural networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3702–3711, 2018.
  * [28] Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet.  Are GANs created equal? a large-scale study.  In NeurIPS, 2018.
  * [29] Sebastian Lunz, Ozan Öktem, and Carola-Bibiane Schönlieb.  Adversarial regularizers in inverse problems.  In Advances in Neural Information Processing Systems, pages 8507–8516, 2018.
  * [30] Tristan Milne and Adrian Nachman.  Wasserstein GANs with gradient penalty compute congested transport.  arXiv preprint arXiv:2109.00528, 2021.
  * [31] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida.  Spectral normalization for generative adversarial networks.  In International Conference on Learning Representations, 2018.
  * [32] Nick Moran, Dan Schmidt, Yu Zhong, and Patrick Coady.  Noisier2noise: Learning to denoise from unpaired noisy data.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 12064–12072, 2020.
  * [33] Youssef Mroueh, Tom Sercu, and Anant Raj.  Sobolev descent.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2976–2985. PMLR, 2019.
  * [34] Subhadip Mukherjee, Marcello Carioni, Ozan Öktem, and Carola-Bibiane Schönlieb.  End-to-end reconstruction meets data-driven regularization for inverse problems.  arXiv preprint arXiv:2106.03538, 2021.
  * [35] Atsushi Nitanda and Taiji Suzuki.  Gradient layer: Enhancing the convergence of adversarial training for generative models.  In International Conference on Artificial Intelligence and Statistics, pages 1008–1016. PMLR, 2018.
  * [36] Derek Onken, Samy Wu Fung, Xingjian Li, and Lars Ruthotto.  OT-flow: Fast and accurate continuous normalizing flows via optimal transport.  Proceedings of the AAAI Conference on Artificial Intelligence, 35(10):9223–9232, May 2021.
  * [37] Henning Petzka, Asja Fischer, and Denis Lukovnikov.  On the regularization of Wasserstein GANs.  In International Conference on Learning Representations, 2018\.
  * [38] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  In International Conference on Learning Representations, 2016.
  * [39] Danilo Rezende and Shakir Mohamed.  Variational inference with normalizing flows.  In International Conference on Machine Learning, pages 1530–1538. PMLR, 2015.
  * [40] Maziar Sanjabi, Jimmy Ba, Meisam Razaviyayn, and J. Lee.  On the convergence and robustness of training GANs with regularized optimal transport.  In NeurIPS, 2018.
  * [41] Filippo Santambrogio.  Optimal Transport for Applied Mathematicians: Calculus of Variations, PDEs, and Modeling, volume 87.  Birkhäuser, 2015.
  * [42] Maximilian Seitzer.  pytorch-fid: FID Score for PyTorch.  https://github.com/mseitzer/pytorch-fid, August 2020.  Version 0.1.1.
  * [43] L. Theis, A. van den Oord, and M. Bethge.  A note on the evaluation of generative models.  In International Conference on Learning Representations, 2016.  arXiv:1511.01844.
  * [44] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [45] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In Proceedings of the IEEE international conference on computer vision, pages 2223–2232, 2017.

## Appendix

##  Appendix A Proofs of the mathematical results

In order to prove Lemma 1, Theorem 1, Equation 25 and Proposition 1 we will
need some terminology and results from the theory of $L^{1}$ optimal
transport. Central to the story are the concept of transport rays, a term
coined in [8], which refers to segments over which the Lipschitz inequality of
a $1$-Lipschitz function is saturated.

######  Definition 2.

Let $u\in 1\text{-Lip}(\Omega)$, the set of Lipschitz functions on $\Omega$
with constant $1$. For $x,y\in\Omega$ the segment $[x,y]:=\\{(1-t)x+ty\mid
t\in[0,1]\\}$ is called a transport ray of $u$ if

  1. 1.

$x\neq y$,

  2. 2.

$u(x)-u(y)=|x-y|$,

  3. 3.

$[x,y]$ is not properly contained in any other segment $[z,w]$ satisfying
properties 1 and 2.

The open segment $]x,y[:=\\{(1-t)x+ty\mid t\in(0,1)\\}$ is called the interior
of the transport ray, and $x$ and $y$ are called its upper and lower endpoints
respectively.

######  Lemma 2 (Essentially Lemmas 3.5 and 3.6 from [41]).

If $[x,y]$ is a transport ray of $u$ then for all $t\in[0,1]$,

$u((1-t)x+ty)=(1-t)u(x)+tu(y).$ (28)

Further, $u$ is differentiable for all $z\in]x,y[$, with derivative satisfying

$\nabla u(z)=\frac{x-y}{|x-y|}.$ (29)

Lemma 3 is an easy extension of Lemma 29 that holds when the function $u$ is
also differentiable at the ray endpoints.

######  Lemma 3.

If $[x,y]$ is a transport ray of $u$ and $u$ is differentiable at either
endpoint then (29) also holds at that endpoint.

###### Proof.

The proof is contained in the proof of Corollary 3.8 from [41]. ∎

It was first shown in [3] that $\nabla u$ is actually Lipschitz away from the
endpoints of transport rays. To state this result formally we must define the
distance between a point $z$ in a transport ray and the endpoints of that ray.

######  Definition 3.

Given $u\in 1\text{-Lip}(\Omega)$, set

$D=\\{x\in\Omega\mid\nabla u(x)\text{ exists}\\}.$ (30)

Define $\ell_{+},\ell_{-}:D\rightarrow[0,\infty)$ by

$\ell_{\pm}(z)=\sup\\{t\in[0,\infty)\mid u(z\pm t\nabla u(z))-u(z)=\pm t\\}.$
(31)

Note that if $\ell_{+}(z)>0$ or $\ell_{-}(z)>0$, $z$ must be in at least one
transport ray, and if both are positive $z$ is on the interior of a unique ray
by Corollary 3.8 from [41].

The proof of the following result on the Lipschitz regularity of $\nabla u$
away from the ray endpoints is contained in the proof of Lemma 22 of [3],
however there it is stated with sufficiently specialized notation that it may
be helpful to provide a restatement and reproof here.

######  Proposition 2.

Let $u\in 1\text{-Lip}(\Omega)$ and define, for $j\in\mathbb{N}$,

$A_{j}=\\{z\in D\mid\min(\ell_{-}(z),\ell_{+}(z))>1/j\\}.$ (32)

Then $z\mapsto\nabla u(z)$ is Lipschitz on $A_{j}$ with constant $4j$.

###### Proof.

Let $z,z^{\prime}\in A_{j}$. Note that since $u\in 1\text{-Lip}(\Omega)$, if
$|z-z^{\prime}|\geq\frac{1}{2j}$ then we have the trivial Lipschitz bound

$|\nabla u(z)-\nabla u(z^{\prime})|\leq 2\leq 4j|z-z^{\prime}|.$ (33)

Hence, we focus on the case $|z-z^{\prime}|<\frac{1}{2j}$. In this case the
Lipschitz constant of $u$ allows us to bound the variation in $u$ on these
points;

$|u(z)-u(z^{\prime})|<\frac{1}{2j}.$ (34)

Set $w^{\prime}=z^{\prime}+(u(z)-u(z^{\prime}))\nabla u(z^{\prime})$. By (34),
we have that $w^{\prime}$ and $z^{\prime}$ are on the same transport ray.
Indeed, $w^{\prime}$ is at most $\frac{1}{2j}$ away from $z^{\prime}$, and
$z^{\prime}$ is at least $\frac{1}{j}$ from the endpoints of the transport ray
it is contained in by definition of $A_{j}$.

Since $w^{\prime}$ and $z^{\prime}$ are on the same transport ray,
$w^{\prime}$ lies on the same level set of $u$ as $z$. Indeed, using Lemma 29,

$\displaystyle u(w^{\prime})$
$\displaystyle=u(z^{\prime}+(u(z)-u(z^{\prime}))\nabla u(z^{\prime})),$ (35)
$\displaystyle=u(z^{\prime})+(u(z)-u(z^{\prime})),$ (36) $\displaystyle=u(z).$
(37)

Since both $w^{\prime}$ and $z$ are interior points of their transport rays
and exist on the same level set of $u$ we can then invoke Lemma 16 from [3] to
obtain that

$|\nabla u(w^{\prime})-\nabla u(z)|\leq\frac{1}{\sigma}|w^{\prime}-z|,$ (38)

where $\sigma$ is the minimal distance from $w^{\prime}$ or $z$ to the
endpoints of its transport ray; by construction this is at least
$\frac{1}{2j}$. Hence,

$|\nabla u(w^{\prime})-\nabla u(z)|\leq 2j|w^{\prime}-z|.$ (39)

Given that $\nabla u(w^{\prime})=\nabla u(z^{\prime})$, we therefore have

$|\nabla u(z^{\prime})-\nabla u(z)|\leq
2j|z^{\prime}-z|+2j|w^{\prime}-z^{\prime}|.$ (40)

Estimating the last term,

$\displaystyle|w^{\prime}-z^{\prime}|$
$\displaystyle=|u(w^{\prime})-u(z^{\prime})|,$ (41)
$\displaystyle=|u(z)-u(z^{\prime})|,$ (42) $\displaystyle\leq|z-z^{\prime}|,$
(43)

whence (40) gives us

$|\nabla u(z^{\prime})-\nabla u(z)|\leq 4j|z^{\prime}-z|$ (44)

for all $|z^{\prime}-z|\leq\frac{1}{2j}$. Combining this with (33), we obtain
that $z\mapsto\nabla u(z)$ is Lipschitz on $A_{j}$ with constant $4j$. ∎

###### Proof of Lemma 1.

We need to specify the set where (10) holds. We start by defining the set $C$
as all points $x$ such that the pair $(x,T_{0}(x))$ saturates the Lipschitz
inequality of $u_{0}$,

$C=\\{x\in\Omega\mid u_{0}(x)-u_{0}(T_{0}(x))=|x-T_{0}(x)|\\}.$ (45)

$C$ has full $\mu$ measure (meaning $\mu(C^{c})=0$) by the following argument:
it is a standard consequence of Kantorovich’s duality theorem (_e.g_. the
discussion following equation (3.2) in [41]) that

$\text{spt}((Id,T_{0})_{\\#}\mu)\subset\\{(x,y)\in\Omega^{2}\mid
u_{0}(x)-u_{0}(y)=|x-y|\\}.$ (46)

Letting $\Gamma_{T_{0}}(C^{c})=\\{(x,T_{0}(x))\mid x\in C^{c}\\}$, (46) gives
us that

$(Id,T_{0})_{\\#}\mu(\Gamma_{T_{0}}(C^{c}))=0,$ (47)

but $(Id,T_{0})^{-1}(\Gamma_{T_{0}}(C^{c}))=C^{c}$, so $\mu(C^{c})=0$. Hence
$C$ has full $\mu$ measure. Note also that $D$ has full $\mu$ measure by
Rademacher’s Theorem.

We claim that for all $x\in C\cap D$, (10) holds. Indeed, suppose $x\neq
T_{0}(x)$. Then by definition of $C$, the pair $(x,T_{0}(x))$ is in a
transport ray. By Lemma 29 or Lemma 3, we obtain that $\nabla u_{0}(x)$ is
aligned with the direction of that ray, and hence by the definition of $C$
again,

$\nabla u_{0}(x)=\frac{x-T_{0}(x)}{|x-T_{0}(x)|}.$ (48)

Thus, (10) holds on $C\cap D$, and $\mu((C\cap D)^{c})=0$. ∎

###### Proof of Theorem 1 parts i and ii.

Both properties will be proved simultaneously by Kantorovich duality. Since
$u_{0}\in 1\text{-Lip}(\Omega)$, Kantorovich duality gives

$\displaystyle W_{1}(\tilde{\mu},\nu)$
$\displaystyle\geq\int_{\Omega}u_{0}(x)d\tilde{\mu}-\int_{\Omega}u_{0}(y)d\nu,$
(49)
$\displaystyle=\int_{\Omega}u_{0}(f_{0}(x))d\mu-\int_{\Omega}u_{0}(y)d\nu,$
(50) $\displaystyle=\int_{C\cap
D}u_{0}\left(x-\eta_{0}\frac{x-T_{0}(x)}{|x-T_{0}(x)|}\right)d\mu,$
$\displaystyle\quad-\int_{\Omega}u_{0}(y)d\nu.$ (51)

The last line follows because (19) gives that $x\neq T_{0}(x)$ $\mu$-almost
everywhere, and hence by Lemma 1,

$\nabla u_{0}(x)=\frac{x-T_{0}(x)}{|x-T_{0}(x)|}$ (52)

on $C\cap D$, which was proven to be a full $\mu$ measure set in the proof of
Lemma 1. By (19) and Lemma 29 we get that $\mu$-almost everywhere in $C$,

$u_{0}\left(x-\eta_{0}\frac{x-T_{0}(x)}{|x-T_{0}(x)|}\right)=u_{0}(x)-\eta_{0}.$
(53)

Substituting this into our calculation, we obtain

$\displaystyle W_{1}(\tilde{\mu},\nu)$ $\displaystyle\geq\int_{C\cap
D}(u_{0}(x)-\eta_{0})d\mu-\int_{\Omega}u_{0}d\nu,$ (54)
$\displaystyle=W_{1}(\mu,\nu)-\eta_{0},$ (55)

the last equality holding because $u_{0}$ is a Kantorovich potential for the
pair $(\mu,\nu)$.

We will now show that the right hand side of (55) is also an upper bound on
$W_{1}(\tilde{\mu},\nu)$. Observe that the plan

$\gamma:=(f_{0},T_{0})_{\\#}\mu$ (56)

is in $\Pi(\tilde{\mu},\nu)$. Therefore,

$\displaystyle W_{1}(\tilde{\mu},\nu)$
$\displaystyle\leq\int_{\Omega}|x-y|d(f_{0},T_{0})_{\\#}\mu,$ (57)
$\displaystyle=\int_{\Omega}|f_{0}(x)-T_{0}(x)|d\mu,$ (58)
$\displaystyle=\int_{\Omega}|x-T_{0}(x)-\eta_{0}\frac{x-T_{0}(x)}{|x-T_{0}(x)|}|d\mu.$
(59)

In the last line we have again used Lemma 1. Using (19) again, we obtain that

$W_{1}(\tilde{\mu},\nu)\leq\int_{\Omega}|x-T_{0}(x)|d\mu-\eta_{0}=W_{1}(\mu,\nu)-\eta_{0},$
(60)

where here we have used optimality of $T_{0}$. Equality of the lower bound in
(55) and the upper bound in (60) mean that the inequalities are actually
equalities, proving that $u_{0}$ is a Kantorovich potential for
$W_{1}(\tilde{\mu},\nu)$ and that
$W_{1}(\tilde{\mu},\nu)=W_{1}(\mu,\nu)-\eta_{0}$. ∎

We are now ready to prove part 22 of Theorem 1. Our proof is just an
integration by substitution to calculate the density $\tilde{\rho}$ of
$\tilde{\mu}$ given the density $\rho$ of $\mu$, but we must be careful
because our change of variables can be irregular near the ends of transport
rays. The main idea is to remove $\mu$ negligible sets from $\Omega$ until we
can apply the Area Formula to compute $\tilde{\rho}$.

###### Proof of Theorem 1 part 22.

Let $E$ be a Lebesgue measurable set. Then with $\rho$ as the density of $\mu$
with respect to $\mathcal{L}_{d}$,

$\displaystyle\tilde{\mu}(E)$ $\displaystyle=\int_{f_{0}^{-1}(E)}\rho(x)dx.$
(61)

By (19) there exists $\epsilon>0$ such that
$\eta_{0}+\epsilon<\ell_{0}(T_{0})$. For this $\epsilon$, define

$F=\\{x\in\Omega\mid|x-T_{0}(x)|>\eta_{0}+\epsilon\\}.$ (62)

$F$ has full $\mu$ measure by (19). Set also $B=\ell_{+}^{-1}(0)$, which is
the set of points such that $u_{0}$ fails to saturate its Lipschitz constant
for any amount of movement in the direction $\nabla u_{0}$. We claim that

$P:=B^{c}\cap C\cap F$ (63)

has full $\mu$ measure. We are interested in $P$ because for all $x\in P$, $x$
must be in a transport ray which has descending length at least $\eta$ by
virtue of being in $C\cap F$, and must not be at the start of that ray by
virtue of being in $B^{c}$. Using Proposition 2, this will be the set where
our change of variables is sufficiently regular.

Since $C$ and $F$ both have full $\mu$ measure, to show that $P$ has full
measure we need only show that

$\mu(B\cap C\cap F)=0.$ (64)

If $x\in C\cap F$, however, $x$ must be in a transport ray of $u_{0}$, and if
in addition $x\in B$, then $x$ must be the upper endpoint of that ray. The set
of endpoints of transport rays has Lebesgue measure $0$ by Lemma 25 of [3],
and hence $\mu$ measure $0$ since $\mu\ll\mathcal{L}_{d}$. Thus (64) holds,
and hence $P$ has full $\mu$ measure. Thus we obtain

$\tilde{\mu}(E)=\int_{P\cap f_{0}^{-1}(E)}\rho(x)dx.$ (65)

We can write $P\cap f_{0}^{-1}(E)$ as the image of $g_{0}$ on a certain set.
In particular

$P\cap f_{0}^{-1}(E)=g_{0}(f_{0}(P)\cap E).$ (66)

To prove (66), note that on $P$ we have $g_{0}(f_{0}(x))=x$. Indeed, for $x\in
P$, both $x$ and $f_{0}(x)$ are on the interior of the transport ray
containing $x$ and $T_{0}(x)$, and hence by Lemma 29, $\nabla u_{0}(x)$ and
$\nabla u_{0}(f_{0}(x))$ exist and are equal, which implies
$g_{0}(f_{0}(x))=x$. So,

$P\cap f_{0}^{-1}(E)=g_{0}(f_{0}(P\cap f_{0}^{-1}(E))),$ (67)

from which (66) follows.

As a consequence of the Area Formula (Theorem 3.2.5. from [9]), if
$\rho:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is Lebesgue measurable,
$A\subset\mathbb{R}^{d}$ is Lebesgue measurable, and
$g:A\rightarrow\mathbb{R}^{d}$ injective and Lipschitz on $A$, we have

$\int_{g(A)}\rho(y)dy=\int_{A}\rho(g(x))|Dg(x)|dx,$ (68)

where $|Dg(x)|$ denotes the absolute value of the determinant of the Jacobian
of $g$. Thus, provided $f_{0}(P)\cap E$ is measurable and $g_{0}$ is injective
and Lipschitz on this set, the area formula gives

$\int_{g_{0}(f_{0}(P)\cap E)}\rho(x)dx=\int_{f_{0}(P)\cap
E}\rho(g_{0}(x))|Dg_{0}(x)|dx.$ (69)

Assuming we have this formula, we obtain

$\tilde{\mu}(E)=\int_{E}1_{f_{0}(P)}(x)\rho(g_{0}(x))|Dg_{0}(x)|dx.$ (70)

Hence, $\tilde{\mu}\ll\mathcal{L}_{d}$ with integrable density

$\tilde{\rho}(x)=1_{f_{0}(P)}(x)\rho(g_{0}(x))|Dg_{0}(x)|.$ (71)

Evaluating this formula at $f_{0}(x)$ for $x\in P$, we get (22), and part 22
of Theorem 1 is proved. Hence, it only remains to prove that $f_{0}(P)\cap E$
is measurable, and that $g_{0}$ is injective and Lipschitz on this set. These
facts are proved in Lemmas 4 and 6. ∎

######  Lemma 4.

The set $f_{0}(P)$ is measurable.

###### Proof.

By definition of $B$ we have $\ell_{+}>0$ on $P$. So, defining

$\displaystyle B_{j}$
$\displaystyle=\ell_{+}^{-1}\left(\left[\frac{1}{j},\infty\right)\right),\quad
j\geq 1,$ (72)

we obtain that $P=\bigcup_{j=1}^{\infty}P\cap B_{j}$. Hence,

$f_{0}(P)=\bigcup_{j=1}^{\infty}f_{0}(P\cap B_{j}).$ (73)

For all $j\geq 1$, $P\cap B_{j}=C\cap F\cap B_{j}$ is measurable because $C$
and $F$ are measurable and $\ell_{+}$ is an upper semi-continuous function on
its domain (see Lemma 5). Hence, if $f_{0}$ is injective and Lipschitz on
$P\cap B_{j}$, then Proposition 262E of [11] will give us that $f_{0}(P\cap
B_{j})$ is measurable for all $j$, proving the lemma.

In fact, $f_{0}$ is obviously injective on $P$ since $g_{0}(f_{0}(x))=x$ for
all $x\in P$. That $f_{0}$ is Lipschitz on $P\cap B_{j}$ follows from
Proposition 2. Indeed, by definition of $P$, $\ell_{-}(x)>\eta_{0}$ on $P$,
and by definition of $B_{j}$, $\ell_{+}(x)\geq 1/j$. Hence, there exists $k$
such that $P\cap B_{j}\subset A_{k}$, and thus $f_{0}$ is Lipschitz on $P\cap
B_{j}$. ∎

######  Lemma 5.

The function $\ell_{+}$ is upper semi-continuous on its domain.

###### Proof.

The proof is similar to that of Lemma 24 in [3], but the setting is different,
so we provide the details here. Let $(x_{n})_{n=1}^{\infty}\subset D$ converge
to a point $x\in D$. If

$\limsup_{n}\ell_{+}(x_{n})=0,$ (74)

then $\ell_{+}(x)\geq\limsup_{n}\ell_{+}(x_{n})$ trivially. If
$m_{0}:=\limsup_{n}\ell_{+}(x_{n})>0$, we can extract a subsequence and
relabel so that $m_{0}=\lim_{n}\ell_{+}(x_{n})>0$. Since $(\nabla
u_{0}(x_{n}))_{n}$ is a bounded sequence, we may extract a further subsequence
and relabel again so that $\lim_{n\rightarrow\infty}\nabla u_{0}(x_{n})=v$ for
some unit vector $v$. The continuity of $u_{0}$ then implies

$\displaystyle u_{0}(x+m_{0}v)-u_{0}(x)$
$\displaystyle=\lim_{n\rightarrow\infty}u_{0}(x_{n}+\ell_{+}(x_{n})\nabla
u_{0}(x_{n}))$ $\displaystyle\qquad-u_{0}(x_{n}),$ (75)
$\displaystyle=\lim_{n\rightarrow\infty}\ell_{+}(x_{n}),$ (76)
$\displaystyle=m_{0}.$ (77)

Since $x\in D$ and $u_{0}\in 1\text{-Lip}(\Omega)$ Lemma 29 or Lemma 3 implies
that we must have $\nabla u_{0}(x)=v$. As such, (77) implies $\ell_{+}(x)\geq
m_{0}$, proving upper semi-continuity. ∎

######  Lemma 6.

The function $g_{0}$ is injective and Lipschitz on $f_{0}(P)$.

###### Proof.

By definition of $f_{0}$ and $P$ we obtain that

$\inf_{x\in P}\min(\ell_{-}(f_{0}(x)),\ell_{+}(f_{0}(x)))>0.$ (78)

Thus, there exists $j$ such that $f_{0}(P)\subset A_{j}$, and hence by Lemma 2
$g_{0}$ is Lipschitz on $f_{0}(P)$.

To see that $g_{0}$ is injective on $f_{0}(P)$, let $x_{1},x_{2}\in P$ such
that

$g_{0}(f_{0}(x_{1}))=g_{0}(f_{0}(x_{2})).$ (79)

Since $g_{0}(f_{0}(x))=x$ for $x\in P$, we immediately obtain
$f_{0}(x_{1})=f_{0}(x_{2})$, and hence $g_{0}$ is injective on $f_{0}(P)$. ∎

Part iii of Theorem 1 now follows easily.

###### Proof of Theorem 1 part iii.

Since $g_{0}\circ f_{0}=I$ on $P$ and $\mu(P^{c})=0$, we obtain that

$\displaystyle(T_{1})_{\\#}\tilde{\mu}$ $\displaystyle=(T_{0}\circ
g_{0})_{\\#}(f_{0})_{\\#}\mu,$ (80) $\displaystyle=(T_{0})_{\\#}\mu,$ (81)
$\displaystyle=\nu.$ (82)

Hence $T_{1}$ is an admissible map for computing $W_{1}(\tilde{\mu},\nu)$. Its
cost is

$\displaystyle\int_{\Omega}|x-T_{1}(x)|d\tilde{\mu}$
$\displaystyle=\int_{\Omega}|f_{0}(x)-T_{0}(x)|d\mu,$ (83)
$\displaystyle=\int_{\Omega}|x-T_{0}(x)-\eta_{0}\frac{x-T_{0}(x)}{|x-T_{0}(x)|}|d\mu.$
(84)

Applying (19) we get

$\int_{\Omega}|x-T_{1}(x)|d\tilde{\mu}=\int_{\Omega}|x-T_{0}(x)|d\mu-\eta_{0}=W_{1}(\tilde{\mu},\nu),$
(85)

and hence $T_{1}$ is optimal. In the course of proving this we have shown that
$\mu$ almost everywhere

$|f_{0}(x)-T_{1}(f_{0}(x))|=|x-T_{0}(x)|-\eta_{0}.$ (86)

As such,

$\mu(\\{x\mid|f_{0}(x)-T_{1}(f_{0}(x))|<\ell_{0}(T_{0})-\eta_{0}\\})=0.$ (87)

Hence

$\tilde{\mu}(\\{x\mid|x-T_{1}(x)|<\ell_{0}(T_{0})-\eta_{0}\\})=0,$ (88)

which implies $\ell_{0}(T_{1})\geq\ell_{0}(T_{0})-\eta_{0}$. ∎

Before we proceed with the proof of Theorem 25, we present the following
lemma, which shows that provided $\mu$ has a density and the minimal transport
distance is positive, the gradients of Kantorovich potentials for the pair
$(\mu,\nu)$ agree $\mu$-almost everywhere. Thus, the measure $\mu_{n}$, which
in principle depends on a choice of Kantorovich potential for the pair
$(\mu_{n-1},\nu)$, is actually independent of this choice provided these
conditions hold.

######  Lemma 7.

Suppose that $\mu\ll\mathcal{L}_{d}$, $T_{0}$ is an optimal transport map for
the pair $(\mu,\nu)$, and $u_{0},\tilde{u}_{0}$ are Kantorovich potentials for
the same pair. If $\ell_{0}(T_{0})>0$, then $\mu$-almost everywhere

$\nabla u_{0}(x)=\nabla\tilde{u}_{0}(x).$ (89)

###### Proof.

Since $\ell_{0}(T_{0})>0$, we have that $x\neq T_{0}(x)$ for $\mu$ almost all
$x$. Applying Lemma 1 separately to $u_{0}$ and $\tilde{u}_{0}$, we obtain
(89) $\mu$-almost everywhere. ∎

###### Proof of Theorem 25.

Let $u_{0}$ be a Kantorovich potential for the pair $(\mu_{0},\nu)$. We begin
by claiming that for all $n\in\\{0,1,\ldots,N(\theta))$ we have

  1. i.

$u_{0}$ is a Kantorovich potential for the pair $(\mu_{n},\nu)$,

  2. ii.

$W_{1}(\mu_{n},\nu)=(1-\theta)^{n}W_{1}(\mu_{0},\nu)$,

  3. iii.

$\mu_{n}\ll\mathcal{L}_{d}$, and,

  4. iv.

for $n>0$ and setting $T_{n}:=T_{n-1}\circ g_{n-1}$ with

$g_{n-1}(x)=\begin{cases}x+\eta_{n-1}\nabla u_{0}(x)&\quad{\nabla
u_{0}(x)\text{ exists}},\\\ x&\quad\text{else,}\end{cases}$ (90)

$T_{n}$ is an optimal transport map from $\mu_{n}$ to $\nu$ satisfying

$\ell_{0}(T_{n})\geq\ell_{0}(T_{0})-W_{1}(\mu_{0},\nu)(1-(1-\theta)^{n}).$
(91)

Points (i - iv) will be proven simultaneously by induction. The base case is
true by definition. For the inductive step, suppose that (i - iv) hold for
index $n-1$. We will then check that the conditions of Theorem 1 hold with
$\mu_{n-1}$ as $\mu$, $\mu_{n}$ as $\tilde{\mu}$ and $T_{n-1}$ as the optimal
map from $\mu_{n-1}$ to $\nu$. Note that by definition of $N(\theta)$, our
inductive assumption guarantees that $\ell_{0}(T_{n-1})>0$, and hence via
Lemma 7 we have that $\mu_{n}=(I-\eta_{n-1}\nabla u_{0})_{\\#}\mu_{n-1}$.

Therefore, the only condition in Theorem 1 which must be checked is that

$\eta_{n-1}<\ell_{0}(T_{n-1}).$ (92)

But, by our inductive assumption we have that

$\displaystyle\ell_{0}(T_{n-1})$
$\displaystyle\geq\ell_{0}(T_{0})-W_{1}(\mu_{0},\nu)(1-(1-\theta)^{n-1}).$
(93)

Hence, the inequality (92) will hold if

$\displaystyle\ell_{0}(T_{0})-W_{1}(\mu_{0},\nu)(1-(1-\theta)^{n-1})$
$\displaystyle>\eta_{n-1}.$ (94)

Writing $\eta_{n-1}=\theta(1-\theta)^{n-1}W_{1}(\mu_{0},\nu)$ and rearranging,
this is equivalent to

$(1-\theta)^{n}>1-\frac{\ell_{0}(T_{0})}{W_{1}(\mu_{0},\nu)}.$ (95)

Taking logarithms in base $1-\theta$ we see that $n$ satisfies this inequality
if and only if

$n<\log_{1-\theta}\left(1-\ell_{0}(T_{0})/W_{1}(\mu_{0},\nu)\right).$ (96)

Hence, if

$n\leq\lceil\log_{1-\theta}\left(1-\ell_{0}(T_{0})/W_{1}(\mu_{0},\nu)\right)\rceil-1=N(\theta),$
(97)

we have (92). Thus we may apply Theorem 1, from which points i and iii are
immediate. From ii in Theorem 1 we obtain

$\displaystyle W_{1}(\mu_{n},\nu)$ $\displaystyle=W_{1}(\mu_{n-1},\nu)-\theta
W_{1}(\mu_{n-1}\nu),$ (98) $\displaystyle=(1-\theta)^{n}W_{1}(\mu_{0},\nu),$
(99)

which proves ii. Finally, iv follows from part iii from Theorem 1, together
with the computation

$\displaystyle\ell_{0}(T_{n})$
$\displaystyle\geq\ell_{0}(T_{n-1})-\eta_{n-1},$ (100)
$\displaystyle\geq\ell_{0}(T_{0})-W_{1}(\mu_{0},\nu)(1-(1-\theta)^{n-1})$
$\displaystyle\quad-\theta(1-\theta)^{n-1}W_{1}(\mu_{0},\nu),$ (101)
$\displaystyle=\ell_{0}(T_{0})-W_{1}(\mu_{0},\nu)(1-(1-\theta)^{n}).$ (102)

Thus we have proven claims i-iv. In particular (23) is proved, as it is claim
ii. Finally, since

$\displaystyle W_{1}(\mu_{N(\theta)},\nu)$
$\displaystyle=(1-\theta)^{N(\theta)}W_{1}(\mu_{0},\nu),$ (103)
$\displaystyle=\frac{W_{1}(\mu_{0},\nu)}{1-\theta}(1-\theta)^{N(\theta)+1},$
(104)

and

$N(\theta)+1\geq\log_{1-\theta}\left(1-\ell_{0}(T_{0})/W_{1}(\mu_{0},\nu)\right),$
(105)

we obtain that

$W_{1}(\mu_{N(\theta)},\nu)\leq\frac{W_{1}(\mu_{0},\nu)-\ell_{0}(T_{0})}{1-\theta},$
(106)

as claimed. ∎

###### Proof of Proposition 1.

Since $u_{0}\in 1\text{-Lip}(\Omega)$, the minimal value of (26) is bounded
below by

$\min_{x\in\mathbb{R}^{d}}\frac{1}{2}|x-x_{0}|^{2}-\eta|x-x_{0}|+\eta
u_{0}(x_{0})=\eta u_{0}(x_{0})-\frac{1}{2}\eta^{2}.$ (107)

The equality above follows by minimizing the one-dimensional function
$z\mapsto\frac{1}{2}z^{2}-\eta z$ over non-negative $z$, which has minimizer
$z=\eta$. By assumption, for $\mu$ almost all $x_{0}$ we have
$|x_{0}-T_{0}(x_{0})|\geq\eta$, and the segment $[x_{0},T_{0}(x_{0})]$ is
contained in a transport ray of $u_{0}$. In addition, for $\mu$ almost all
$x_{0}$ Lemma 1 gives us that $|\nabla u_{0}(x_{0})|=1$. Thus, by Lemma 29, we
get

$\displaystyle\frac{1}{2}|\eta\nabla u_{0}(x_{0})|^{2}+\eta
u_{0}(x_{0}-\eta\nabla u_{0}(x_{0}))$ $\displaystyle=\eta
u_{0}(x_{0})-\frac{1}{2}\eta^{2},$ (108)

and so $x_{0}-\eta\nabla u_{0}(x_{0})$ obtains the minimal value of (26). For
uniqueness, observe that any minimizer $x^{*}$ distinct from $x_{0}-\eta\nabla
u_{0}(x_{0})$ must satisfy

$u_{0}(x^{*})=u_{0}(x_{0})-|x^{*}-x_{0}|,$ (109)

and thus $x_{0}$ must exist at the intersection of at least two transport
rays. The set of $x_{0}$ for which this can occur is negligible, completing
the proof. ∎

##  Appendix B Additional experimental results

###  B.1 Misalignment experiments

Stage in training | InfoGAN | DCGAN
---|---|---
Early | $0.307\pm 0.0532$ | $0.284\pm 0.030$
| ($410.4\pm 9.0$) | ($414.3\pm 26.8$)
Mid | $0.148\pm 0.083$ | $0.081\pm 0.082$
| ($22.9\pm 0.5$) | ($40.8\pm 7.1$)
Late | $0.107\pm 0.075$ | $0.079\pm 0.084$
| ($21.8\pm 0.4$) | ($31.1\pm 1.8$)
Table 5: Misalignment cosine measurements. All results are reported in the
form mean $\pm$ standard deviation. The top lines show the statistics of the
cosines of the angles between (5) and $-\nabla u_{0}(G_{w}(z))$, computed over
the training of five separate initializations of each model, each with 256
randomly sampled noise inputs $z$. The statistics appearing in parentheses are
for FID values computed over the five training runs. The values were computed
at three different stages in training, the same as in Table 1

(a) SGD updates vs optimal direction for InfoGAN

(b) SGD updates vs optimal direction for DCGAN

(c) Adam updates vs optimal direction for InfoGAN

(d) Adam updates vs optimal direction for DCGAN

Figure 3: Histograms of the cosines of the angles computed between either SGD
or Adam updates of generated samples and the optimal movement direction given
by $-\nabla u_{0}(G_{w}(z))$. The SGD values corresponds to the statistics in
Table 1, while the Adam values correspond to the statistics in Table 5.

In Section 3 we reported on measurements of the misalignment between the
directions in which generated samples are updated by SGD steps on the
generator and the optimal directions given by $-\nabla u_{0}(G_{w}(z))$. Here,
we show additional measurements taken during the same experiments, but where
the directions of SGD updates are replaced by the directions of Adam updates
(Adam was used to train the network). Since Adam is a variation on SGD that
takes previous steps into account at every stage, one might expect it to yield
larger misalignment. For fixed noise inputs $z$, we computed the difference
between generated samples $G_{w}(z)$ before and after taking one step of an
Adam optimizer. We then computed the cosines of the angles between the
resulting vectors and the corresponding optimal directions $-\nabla
u_{0}(G_{w}(z))$. The Adam optimizer used parameters $\beta_{1}=0.5$ and
$\beta_{2}=0.999$. The statistics of the misalignment values obtained are
shown in Table 5. Comparing to the results in Table 1, we see significantly
more misalignment at an early stage in training, but similar values in mid and
late stages.

Figure 3 displays histograms of the misalignment cosine values, the statistics
of which appear in Table 1 and Table 5. To avoid cluttering, we only show the
results at early and late stages in training. The histograms clearly show that
the movement of generated samples is consistently misaligned with the optimal
direction, there being no cosine values above $0.75$. The misalignment is less
pronounced at early stages of training, especially when using SGD. Adam and
SGD give similar misalignment cosine values at late stages of training, with a
small but significant portion of these values being negative, which indicates
detrimental movement of generated samples in a direction along which the value
of the critic increases.

###  B.2 Generated images for MNIST, Fashion MNIST, and CIFAR-10

Figures 4, 5, and 6 include examples of images generated using the trained
models from the experiments in Section 5.1. Recall that TTC 1 uses a
corresponding untrained generator to create the source distribution $\mu_{0}$,
while TTC 2 uses the standard normal distribution on $\mathbb{R}^{d}$ as
$\mu_{0}$. Despite having lower FIDs, the images produced by TTC 1 and TTC 2
do not obviously appear to have improved quality. This is perhaps not
surprising, since FID measures the statistics of high-dimensional
distributions and thus the modest reductions in FID we have obtained may not
be visible to the naked eye for a single minibatch.

Figure 4: Generated examples for MNIST for a particular training run of each
technique. From top to bottom: WGAN-GP (FID 20.8), TTC 1 (FID 18.5), and TTC 2
(FID 18.2).

Figure 5: Generated examples for F-MNIST for a particular training run of each
technique. From top to bottom: WGAN-GP (FID 25.7), TTC 1 (22.4), and TTC 2
(22.2).

Figure 6: Generated examples for CIFAR10 for a particular training run of each
technique. From top to bottom: WGAN-GP (FID 28.9), TTC 1 (FID 27.8), and TTC 2
(FID 26.5).

###  B.3 Additional image translation examples

Figure 7 contains additional image translation examples, generated using the
same sequence of critics and step sizes that were used to generate Figure 1.

Figure 7: Additional examples of translating landscape photos into Monet
paintings using TTC. As the fourth example shows, the quality of the
translation worsens for source images which are far from Monet painting
samples; since our step size is determined by the average transport distance,
it is possible that it is not suitable for outliers with large initial
transport distances.

###  B.4 Additional image denoising examples

Figure 8 includes additional noisy images from BSDS500, restored using the
same sequence of critics and step sizes that were used to produce Figure 2.
The corresponding PSNR values for each restored image are given in Table 6.
Based on these PSNR values, the advantage of TTC over [29] seems to increase
when large parts of the image are roughly constant. Indeed, TTC has the
largest improvement for the image of the cardinal, which has large constant
portions. On the other hand, the improvement is smaller for the image of the
grassy underbrush, which has many fine details. As a possible explanation for
this trend, we note that on this dataset we have observed that the magnitude
of the noise, summed over the entire image, is bigger than the estimated
Wasserstein-1 distance, indicating that under the optimal transport some noisy
images are not mapped to their original clean versions. For such images, one
would expect that the improvement in PSNR after restoration would be lower.

Figure 8: Restored images from BSDS500 with noise level $\sigma=0.15$ using
the same sequence of trained critics as described in Section 5.3. From left to
right: original image, noisy image, restored image using [29], restored image
using TTC. For PSNR values, see Table 6. The image of the deer is the same as
the one in Section 5.3

.

| PSNR (dB)
---|---
Example | Noisy Image | Adv. Reg. [29] | TTC
Underbrush | $16.4$ | $23.6$ | $\mathbf{24.8}$
Deer | $16.4$ | $24.5$ | $\mathbf{27.0}$
Yellow Bird | $16.5$ | $24.8$ | $\mathbf{29.2}$
Cardinal | $16.5$ | $25.3$ | $\mathbf{33.0}$
Table 6: PSNR values for the images in Figure 8. As mentioned above, the
advantage of TTC increases when large parts of the initial image are almost
constant.