arXiv:1712.07822v2 [stat.ML] 12 Mar 2018

Geometrical Insights
for Implicit Generative Modeling
Leon Bottou a,b, Martin Arjovsky b,a, David Lopez-Paz a, Maxime Oquab a,c
a

Facebook AI Research, New York, Paris
b New York University, New York
c Inria, Paris.
March 14, 2018
Abstract

Learning algorithms for implicit generative models can optimize a variety of criteria that measure how the data distribution differs from the implicit model distribution,
including the Wasserstein distance, the Energy distance, and the Maximum Mean Discrepancy criterion. A careful look at the geometries induced by these distances on
the space of probability measures reveals interesting differences. In particular, we can
establish surprising approximate global convergence guarantees for the 1-Wasserstein
distance, even when the parametric generator has a nonconvex parametrization.

1

Introduction

Instead of representing the model distribution with a parametric density function, implicit
generative models directly describe how to draw samples of the model distribution by first
drawing a sample z from a fixed random generator and mapping into the data space with
a parametrized generator function Gθ (z). The reparametrization trick [13, 42], Variational
Auto-Encoders (VAEs) [27], and Generative Adversarial Networks (GANs) [20] are recent
instances of this approach.
Many of these authors motivate implicit modeling with the computational advantage
that results from the ability of using the efficient back-propagation algorithm to update the
generator parameters. In contrast, our work targets another, more fundamental, advantage
of implicit modeling.
Although unsupervised learning is often formalized as estimating the data distribution [24, §14.1], the practical goal of the learning process rarely consists in recovering
actual probabilities. Instead, the probability models are often structured in a manner that is
interpretable as a physical or causal model of the data. This is often achieved by defining
an interpretable density p(y) for well chosen latent variables y and letting the appearance
model p(x|y) take the slack. This approach is well illustrated by the inverse graphics approach to computer vision [31, 30, 43]. Implicit modeling makes this much simpler:
1

• The structure of the generator function Gθ (z) could be directly interpreted as a set
of equations describing a physical or causal model of the data [28].
• There is no need to deal with latent variables, since all the variables of interest are
explicitly computed by the generator function.
• Implicit modeling can easily represent simple phenomena involving a small set of
observed or inferred variables. The corresponding model distribution cannot be represented with a density function because it is supported by a low-dimensional manifold. But nothing prevents an implicit model from generating such samples.
Unfortunately, we cannot fully realize these benefits using the popular Maximum Likelihood Estimation (MLE) approach, which asymptotically amounts to minimizing the KullbackLeibler (KL) divergence DKL (Q, Pθ ) between the data distribution Q and the model distribution Pθ ,


Z
q(x)
q(x)dµ(x)
(1)
DKL (Q, Pθ ) = log
pθ (x)
where pθ and q are the density functions of Pθ and Q with respect to a common measure
µ. This criterion is particularly convenient because it enjoys favorable statistical properties
[14] and because its optimization can be written as an expectation with respect to the data
distribution,
argmin DKL (Q, Pθ ) = argmin Ex∼Q [− log(pθ (x))] ≈ argmax
θ

θ

θ

n
Y

pθ (xi ) .

i=1

which is readily amenable to computationally attractive stochastic optimization procedures [10]. First, this expression is ill-defined when the model distribution cannot be represented by a density. Second, if the likelihood pθ (xi ) of a single example xi is zero, the
dataset likelihood is also zero, and there is nothing to maximize. The typical remedy is to
add a noise term to the model distribution. Virtually all generative models described in the
classical machine learning literature include such a noise component whose purpose is not
to model anything useful, but merely to make MLE work.
Instead of using ad-hoc noise terms to coerce MLE into optimizing a different similarity
criterion between the data distribution and the model distribution, we could as well explicitly optimize a different criterion. Therefore it is crucial to understand how the selection of
a particular criterion will influence the learning process and its final result.
Section 2 reviews known results establishing how many interesting distribution comparison criteria can be expressed in adversarial form, and are amenable to tractable optimization algorithms. Section 3 reviews the statistical properties of two interesting families
of distribution distances, namely the family of the Wasserstein distances and the family
containing the Energy Distances and the Maximum Mean Discrepancies. Although the
Wasserstein distances have far worse statistical properties, experimental evidence shows
that it can deliver better performances in meaningful applicative setups. Section 4 reviews
essential concepts about geodesic geometry in metric spaces. Section 5 shows how different probability distances induce different geodesic geometries in the space of probability

2

measures. Section 6 leverages these geodesic structures to define various flavors of convexity for parametric families of generative models, which can be used to prove that a simple
gradient descent algorithm will either reach or approach the global minimum regardless of
the traditional nonconvexity of the parametrization of the model family. In particular, when
one uses implicit generative models, minimizing the Wasserstein distance with a gradient
descent algorithm offers much better guarantees than minimizing the Energy distance.

2

The adversarial formulation

The adversarial training framework popularized by the Generative Adversarial Networks
(GANs) [20] can be used to minimize a great variety of probability comparison criteria.
Although some of these criteria can also be optimized using simpler algorithms, adversarial
training provides a common template that we can use to compare the criteria themselves.
This section presents the adversarial training framework and reviews the main categories of probability comparison criteria it supports, namely Integral Probability Metrics (IPM) (Section 2.4), f -divergences (Section 2.5), Wasserstein distances (WD) (Section 2.6), and Energy Distances (ED) or Maximum Mean Discrepancy distances (MMD)
(Section 2.7).

2.1

Setup

Although it is intuitively useful to consider that the sample space X is some convex subset
of Rd , it is also useful to spell out more precisely which properties are essential to the development. In the following, we assume that X is a Polish metric space, that is, a complete
and separable space whose topology is defined by a distance function

X ×X
→
R+ ∪ {+∞}
d:
(x, y)
7→
d(x, y)
satisfying the properties of a metric distance:

(0) d(x, x) = 0



(i) x 6= y ⇒ d(x, y) > 0
∀x, y, z ∈ X
(ii) d(x, y) = d(y, x)



(iii) d(x, y) ≤ d(x, z) + d(z, y)

(zero)
(separation)
(symmetry)
(triangular inequality)

(2)

Let U be the Borel σ-algebra generated by all the open sets of X . We use the notation
PX for the set of probability measures µ defined on (X , U), and the notation PXp ⊂ PX for
those satisfying Ex,y∼µ [d(x, y)p ] <∞. This condition is equivalent to Ex∼µ [d(x, x0 )p ] <∞
for an arbitrary origin x0 when d is finite, symmetric, and satisfies the triangular inequality.
We are interested in criteria to compare elements of PX ,

PX × PX
→
R+ ∪ {+∞}
D:
.
(Q, P )
7→
D(Q, P )
Although it is desirable that D also satisfies the properties of a distance (2), this is not always possible. In this contribution, we strive to only reserve the word distance for criteria
3

that satisfy the properties (2) of a metric distance. We use the word pseudodistance1 when
a nonnegative criterion fails to satisfy the separation property (2.i). We use the word divergence for criteria that are not symmetric (2.ii) or fail to satisfy the triangular inequality
(2.iii).
We generally assume in this contribution that the distance d defined on X is finite.
However we allow probability comparison criteria to be infinite. When the distributions
Q, P do not belong to the domain for which a particular criterion D is defined, we take that
D(Q, P )=0 if Q=P and D(Q, P )= + ∞ otherwise.

2.2

Implicit modeling

We are particularly interested in model distributions Pθ that are supported by a low-dimensional
manifold in a large ambient sample space (recall Section 1). Since such distributions do
not typically have a density function, we cannot represent the model family F using a parametric density function. Following the example of Variational Auto-Encoders (VAE) [27]
and Generative Adversarial Networks (GAN) [20], we represent the model distributions by
defining how to produce samples.
Let z be a random variable with known distribution µz defined on a suitable probability
space Z and let Gθ be a measurable function, called the generator, parametrized by θ ∈ Rd ,
Gθ : z ∈ Z 7→ Gθ (z) ∈ X .
The random variable Gθ (Z) ∈ X follows the push-forward distribution2
Gθ (z)#µZ (z) : A ∈ U 7→ µz (G−1
θ (A)) .
By varying the parameter θ of the generator Gθ , we can change this push-forward distribution and hopefully make it close to the data distribution Q according to the criterion of
interest.
This implicit modeling approach is useful in two ways. First, unlike densities, it can
represent distributions confined to a low-dimensional manifold. Second, the ability to easily generate samples is frequently more useful than knowing the numerical value of the
density function (for example in image superresolution or semantic segmentation when
considering the conditional distribution of the output image given the input image). In general, it is computationally difficult to generate samples given an arbitrary high-dimensional
density [37].
Learning algorithms for implicit models must therefore be formulated in terms of two
sampling oracles. The first oracle returns training examples, that is, samples from the data
distribution Q. The second oracle returns generated examples, that is, samples from the
model distribution Pθ = Gθ #µZ . This is particularly easy when the comparison criterion
D(Q, Pθ ) can be expressed in terms of expectations with respect to the distributions Q
or Pθ .
1 Although failing to satisfy the separation property (2.i) can have serious practical consequences, recall that a
pseudodistance always becomes a full fledged distance on the quotient space X /R where R denotes the equivalence relation xRy ⇔ d(x, y)=0. All the theory applies as long as one never distinguishes two points separated
by a zero distance.
2 We use the notation f µ or f (x) µ(x) to denote the probability distribution obtained by applying function
#
#
f or expression f (x) to samples of the distribution µ.

4

2.3

Adversarial training

We are more specifically interested in distribution comparison criteria that can be expressed
in the form
D(Q, P ) =
sup EQ [fQ (x)] − EP [fP (x)] .
(3)
(fQ ,fP )∈Q

The set Q defines which pairs (fQ , fP ) of real-valued critic functions defined on X are considered in this maximization. As discussed in the following subsections, different choices
of Q lead to a broad variety of criteria. This formulation is a mild generalization of the Integral Probability Metrics (IPMs) [36] for which both functions fQ and fP are constrained
to be equal (Section 2.4).
Finding the optimal generator parameter θ∗ then amounts to minimizing a cost function
C(θ) which itself is a supremum,


∆
min C(θ) = max Ex∼Q [fQ (x)] − Ez∼µz [fP (Gθ (z))]
.
(4)
θ

(fQ ,fP )∈Q

Although it is sometimes possible to reformulate this cost function in a manner that does
not involve a supremum (Section 2.7), many algorithms can be derived from the following
variant of the envelope theorem [35].
Theorem 2.1. Let C be the cost function defined in (4) and let θ0 be a specific value of the
generator parameter. Under the following assumptions,

 ∗
∗
(x) − Eµz [fP∗ (Gθ0 (z))],
, fP∗ ) ∈ Q such that C(θ0 ) = EQ fQ
a. there is (fQ
b. the function C is differentiable in θ0 ,
c. the functions hz = θ 7→ fP∗ (Gθ (z)) are µz -almost surely differentiable in θ0 ,
d. and there exists an open neighborhood V of θ0 and a µz -integrable function D(z)
such that ∀θ∈V, |hz (θ) − hz (θ0 )| ≤ D(z)kθ − θ0 k,
we have the equality gradθ C(θ0 ) = −Ez∼µz [ gradθ hz (θ0 ) ] .
This result means that we can compute the gradient of C(θ0 ) without taking into account the way fP∗ changes with θ0 . The most important assumption here is the differentiability of the cost C. Without this assumption, we can only assert that −Ez∼µz [ gradθ hz (θ0 ) ]
belongs to the “local” subgradient
∆

∂ loc C(θ0 ) =



g ∈ Rd : ∀θ ∈ Rd C(θ) ≥ C(θ0 ) + hg, θ−θ0 i + o(kθ−θ0 k)

.

Proof Let λ ∈ R+ and u ∈ Rd be an arbitrary unit vector. From (3),
 ∗

C(θ0 + λu) ≥ Ez∼Q fQ
(x) − Ez∼µz [fP∗ (Gθ0 +λu (z))]
C(θ0 + λu) − C(θ0 ) ≥ − Ez∼µz [hz (θ0 + λu) − hz (θ0 )] .
Dividing this last inequality by λ, taking its limit when λ → 0, recalling that the dominated convergence theorem and assumption (d) allow us to take the limit inside the expectation operator, and
rearranging the result gives
Au ≥ 0 with A : u ∈ Rd 7→ hu, gradθ C(θ0 ) + Ez∼µz [gradθ hz (θ0 )]i .

5

Writing the same for unit vector −u yields inequality −Au ≥ 0. Therefore Au = 0.

Thanks to this result, we can compute an unbiased3 stochastic estimate ĝ(θt ) of the
gradient grad θ C(θt ) by first solving the maximization problem in (4), and then using
the back-propagation algorithm to compute the average gradient on a minibatch z1 . . . zk
sampled from µ,
k
1X
gradθ fP∗ (Gθ (zi )) .
ĝ(θt ) = −
k i=1
Such an unbiased estimate can then be used to perform a stochastic gradient descent update
iteration on the generator parameter
θt+1 = θt − ηt ĝ(θt ) .
Although this algorithmic idea can be made to work relatively reliably [3, 22], serious
conceptual and practical issues remain:
Remark 2.2. In order to obtain an unbiased gradient estimate ĝ(θt ), we need to solve the
maximization problem in (4) for the true distributions rather than for a particular subset of
examples. On the one hand, we can use the standard machine learning toolbox to avoid
overfitting the maximization problem. On the other hand, this toolbox essentially works
by restricting the family Q in ways that can change the meaning of the comparison criteria
itself [5, 34].
Remark 2.3. In practice, solving the maximization problem (4) during each iteration of the
stochastic gradient algorithm is computationally too costly. Instead, practical algorithms
interleave two kinds of stochastic iterations: gradient ascent steps on (fQ , fP ), and gradient
descent steps on θ, with a much smaller effective stepsize. Such algorithms belong to the
general class of stochastic algorithms with two time scales [9, 29]. Their convergence
properties form a delicate topic, clearly beyond the purpose of this contribution.

2.4

Integral probability metrics

Integral probability metrics (IPMs) [36] have the form
D(Q, P ) =

sup EQ [f (X)] − EP [f (X)]

.

f ∈Q

Note that the surrounding absolute value can be eliminated by requiring that Q also contains
the opposite of every one of its functions.
D(Q, P ) = sup EQ [f (X)] − EP [f (X)]
f ∈Q

(5)

where Q satisfies ∀f ∈ Q , − f ∈ Q .
3 Stochastic gradient descent often relies on unbiased gradient estimates (for a more general condition, see [10,
Assumption 4.3]). This is not a given: estimating the Wasserstein distance (14) and its gradients on small minibatches gives severely biased estimates [7]. This is in fact very obvious for minibatches of size one. Theorem 2.1
therefore provides an imperfect but useful alternative.

6

Therefore an IPM is a special case of (3) where the critic functions fQ and fP are
constrained to be identical, and where Q is again constrained to contain the opposite of
every critic function. Whereas expression (3) does not guarantee that D(Q, P ) is finite and
is a distance, an IPM is always a pseudodistance.
Proposition 2.4. Any integral probability metric D, (5) is a pseudodistance.
Proof To establish the triangular inequality (2.iii), we can write, for all Q, P, R ∈ PX ,
D(Q, P ) + D(P, R)

=

sup
f1 , f2 ∈Q

≥

EQ [f1 (X)] − EP [f1 (X)] + EP [f2 (X)] − ER [f2 (X)]

sup
f1 =f2 ∈Q

=

EQ [f1 (X)] − EP [f1 (X)] + EP [f2 (X)] − ER [f2 (X)]

sup EQ [f (X)] − ER [f (X)] = D(Q, R) .

f ∈Q

The other properties of a pseudodistance are trivial consequences of (5).

The most fundamental IPM is the Total Variation (TV) distance.
∆

DT V (Q, P ) = sup |P (A) − Q(A)| =
A∈U

sup

EQ [f (x)] − EP [f (x)] ,

(6)

f ∈C(X ,[0,1])

where C(X , [0, 1]) is the space of continuous functions from X to [0, 1].

2.5 f -Divergences
Many classical criteria belong to the family of f -divergences

Z 
q(x)
∆
Df (Q, P ) =
f
p(x) dµ(x)
p(x)

(7)

where p and q are respectively the densities of P and Q relative to measure µ and where f
∗
is a continuous convex function defined on R+
such that f (1) = 0.
Expression (7) trivially satisfies (2.0). It is always nonnegative because we can pick a
subderivative u ∈ ∂f (1) and use the inequality f (t) ≥ u(t − 1). This also shows that the
separation property (2.i) is satisfied when this inequality is strict for all t 6= 1.
Proposition 2.5 ([38, 39] (informal)). Usually,4
Df (Q, P ) =

EQ [g(x)] − EP [f ∗ (g(x))] .

sup
g bounded, measurable
g(X )⊂dom(f ∗)

where f ∗ denotes the convex conjugate of f.
Table 1 provides examples of f -divergences and provides both the function f and the
corresponding conjugate function f ∗ that appears in the variational formulation. In particular, as argued in [39], this analysis clarifies the probability comparison criteria associated
with the early GAN variants [20].
4 The statement holds when there is an M >0 such that µ{x : |f (q(x)/p(x))|>M }=0 Restricting µ to
exclude such subsets and taking the limit M → ∞ may not work because lim sup 6= sup lim in general. Yet,
in practice, the result can be verified by elementary calculus for the usual choices of f, such as those shown in
Table 1.

7

Table 1: Various f -divergences and the corresponding f and f ∗ .
f (t)
dom(f ∗ )
1
Total variation (6)
2 |t − 1|
Kullback-Leibler (1)
t log(t)
Reverse Kullback-Leibler
− log(t)
GAN’s Jensen Shannon [20] t log(t) − (t + 1) log(t + 1)

[− 12 , 12 ]
R
R−
R−

f ∗ (u)

u
exp(u − 1)
−1 − log(−u)
− log(1 − exp(u))

t
1

0
P0 P1/4 P1/2

P1

P2

θ

Figure 1: Let distribution Pθ be supported by the segment {(θ, t) t ∈ [0, 1]} in R2 . According to both the TV distance (6) and the f -divergences (7), the sequence of distributions
(P1/i ) does not converge to P0 . However this sequence converges to P0 according to either
the Wasserstein distances (8) or the Energy distance (15).
Despite the elegance of this framework, these comparison criteria are not very attractive
when the distributions are supported by low-dimensional manifolds that may not overlap.
The following simple example shows how this can be a problem [3].
Example 2.6. Let U be the uniform distribution on the real segment [0, 1] and consider the
distributions Pθ = (θ, x)#U (x) defined on R2 . Because P0 and Pθ have disjoint support for
θ 6= 0, neither the total variation distance DT V (P0 , Pθ ) nor the f -divergence Df (P0 , Pθ )
depend on the exact value of θ. Therefore, according to the topologies induced by these
criteria on PX , the sequence of distributions (P1/i ) does not converge to P0 (Figure 1).
The fundamental problem here is that neither the total variation distance (6) nor the
f -divergences (7) depend on the distance d(x, y) defined on the sample space X . The
minimization of such a criterion appears more effective for adjusting the probability values
than for matching the distribution supports.

2.6

Wasserstein distance

For any p ≥ 1, the p-Wasserstein distance (WD) is the p-th root of
∀Q, P ∈ PXp

∆

Wp (Q, P )p =

inf
π∈Π(Q,P )

E(x,y)∼π [ d(x, y)p ] ,

(8)

where Π(Q, P ) represents the set of all measures π defined on X × X with marginals
x#π(x, y) and y #π(x, y) respectively equal to Q and P . Intuitively, d(x, y)p represents the
8

cost of transporting a grain of probability from point x to point y, and the joint distributions π ∈ Π(Q, P ) represent transport plans.
Since d(x, y) ≤ d(x, x0 ) + d(x0 , y) ≤ 2 max{d(x, x0 ), d(x0 , y)},
∀ Q, P ∈ PXp

Wp (Q, P )p ≤ Ex∼Q [d(x, y)p ] < ∞ .

(9)

y∼P

Example 2.7. Let Pθ be defined as in Example 2.6. Since it is easy to see that the optimal transport plan from P0 to Pθ is π ∗ = ((0, t), (θ, t))#U (t), the Wassertein distance
Wp (P0 , Pθ ) = |θ| converges to zero when θ tends to zero. Therefore, according to the
topology induced by the Wasserstein distance on PX , the sequence of distributions (P1/i )
converges to P0 (Figure 1).
Thanks to the Kantorovich duality theory, the Wasserstein distance is easily expressed
in the variational form (3). We summarize below the essential results useful for this work
and we direct the reader to [55, Chapters 4 and 5] for a full exposition.
Theorem 2.8 ([55, Theorem 4.1]). Let X , Y be two Polish metric spaces and c : X ×
Y → R+ ∪ {+∞} be a nonnegative continuous cost function. Let Π(Q, P ) be the set
of probablity measures on X × Y with marginals Q ∈ PX and P ∈ PY . There is a
π ∗ ∈ Π(Q, P ) that minimizes E(x,y)∼π [c(x, y)] over all π ∈ Π(Q, P ).
Definition 2.9. Let X , Y be two Polish metric spaces and c : X ×Y → R+ ∪{+∞} be a
nonnegative continuous cost function. The pair of functions f : X → R and g : Y → R is
c-conjugate when
∀x ∈ X f (x) = inf g(y) + c(x, y) and ∀y ∈ Y g(y) = sup f (x) − c(x, y) . (10)
y∈Y

x∈X

Theorem 2.10 (Kantorovich duality [55, Theorem 5.10]). Let X and Y be two Polish
metric spaces and c : X ×Y → R+ ∪ {+∞} be a nonnegative continuous cost function.
For all Q ∈ PX and P ∈ PY , let Π(Q, P ) be the set of probability distributions defined
on X × Y with marginal distributions Q and P . Let Qc be the set of all pairs (fQ , fP )
of respectively Q and P -integrable functions satisfying the property ∀x ∈ X y ∈ Y,
fQ (x) − fP (y) ≤ c(x, y).
i) We have the duality
min

E(x,y)∼π [c(x, y)] =

π∈Π(Q,P )

sup

Ex∼Q [fQ (x)] − Ey∼P [fP (y)] .

(fQ ,fP )∈Qc

ii) Further assuming that Ex∼Q y∼P [c(x, y)] < ∞,
a) Both (11) and (12) have solutions with finite cost.
∗
b) The solution (fQ
, f p∗ ) of (12) is a c-conjugate pair.

9

(11)
(12)

Corollary 2.11 ([55, Particular case 5.16]). Under the same conditions as Theorem 2.10.ii,
when X = Y and when the cost function c is a distance, that is, satisfies (2), the dual
optimization problem (12) can be rewritten as
max EQ [f (x)] − EP [f (x)] ,

f ∈Lip1

where Lip1 is the set of real-valued 1-Lipschitz continuous functions on X .
Thanks to Theorem 2.10, we can write the p-th power of the p-Wasserstein distance in
variational form
∀Q, P ∈ PXp

Wp (Q, P )p =

sup

EQ [fQ (x)] − EP [fP (x)] ,

(13)

(fQ ,fP )∈Qc

where Qc is defined as in Theorem 2.10 for the cost c(x, y) = d(x, y)p . Thanks to Corollary 2.11, we can also obtain a simplified expression in IPM form for the 1-Wasserstein
distance.
∀Q, P ∈ PX1

W1 (Q, P ) = sup EQ [f (x)] − EP [f (x)] .

(14)

f ∈Lip1

Let us conclude this presentation of the Wassertein distance by mentioning that the definition (8) immediately implies several distance properties: zero when both distributions are
equal (2.0), strictly positive when they are different (2.i), and symmetric (2.ii). Property 2.4
gives the triangular inequality (2.iii) for the case p = 1. In the general case, the triangular
inequality can also be established using the Minkowsky inequality [55, Chapter 6].

2.7

Energy Distance and Maximum Mean Discrepancy

The Energy Distance (ED) [53] between the probability distributions Q and P defined on
the Euclidean space Rd is the square root5 of
∆

E(Q, P )2 = 2Ex∼Q [kx − yk] − E x∼Q [kx − x0 k] − E y∼P [ky − y 0 k] ,
x0∼Q

y∼P

(15)

y 0∼P

where, as usual, k · k denotes the Euclidean distance.
Let q̂ and p̂ represent the characteristic functions of the distribution Q and P respectively. Thanks to a neat Fourier transform argument [53, 52],
1
E(Q, P ) =
cd
2

Z
Rd

|q̂(t) − p̂(t)|2
dt
ktkd+1

d+1

π 2
with cd =
.
Γ( d+1
2 )

(16)

Since there is a one-to-one mapping between distributions and characteristic functions,
this relation establishes an isomorphism between the space of probability distributions
equipped with the ED distance and the space of the characteristic functions equipped with
5 We

take the square root because this is the quantity that behaves like a distance.

10

the weighted L2 norm given in the right-hand side of (16). As a consequence, E(Q, P )
satisfies the properties (2) of a distance.
Since the squared ED is expressed with a simple combination of expectations, it is easy
to design a stochastic minimization algorithm that relies only on two oracles producing
samples from each distribution [11, 7]. This makes the energy distance a computationally
attractive criterion for training the implicit models discussed in Section 2.2.
Generalized ED It is therefore natural to ask whether we can meaningfully generalize (15) by replacing the Euclidean distance kx − yk with a symmetric function d(x, y).
Ed (Q, P )2 = 2Ex∼Q [d(x, y)] − E x∼Q [d(x, x0 )] − E y∼P [d(y, y 0 )] .

(17)

y 0∼P

x0∼Q

y∼P

The right-hand side of this expression is well defined when Q, P ∈ PX1 . It is obviously
symmetric (2.ii) and trivially zero (2.0) when both distributions are equal. The first part
of the following theorem gives the necessary and sufficient conditions on d(x, y) to ensure that the right-hand side of (17) is nonnegative and therefore can be the square of
Ed (Q, P ) ∈ R+ . We shall see later that the triangular inequality (2.iii) comes for free with
this condition (Corollary 2.19). The second part of the theorem gives the necessary and
sufficient condition for satisfying the separation property (2.i).
Theorem 2.12 ([57]). The right-hand side of definition (17) is:
i) nonnegative for all P, Q in PX1 if and only if the symmetric function d is a negative definite kernel, that is,
∀n ∈ N ∀x1 . . . xn ∈ X ∀c1 . . . cn ∈ R
n
n X
n
X
X
d(xi , xj )ci cj ≤ 0 . (18)
ci = 0 =⇒
i=1 j=1

i=1

ii) strictly positive for all P 6= Q in PX1 if and only if the function d is a strongly negative definite kernel, that is, a negative definite kernel such that, for any probability measure µ ∈ PX1 and any µ-integrable real-valued function h such that
Eµ [h(x)] = 0,
Ex∼µ [ d(x, y)h(x)h(y) ] = 0 =⇒ h(x) = 0 µ-almost everywhere.
y∼µ

Remark 2.13. The definition of a strongly negative kernel is best explained by considering
how its meaning would change if we were only considering probability measures µ with
finite support {x1 . . . xn }. This amounts to requiring that (18) is an equality only if all the
ci s are zero. However, this weaker property is not sufficient to ensure that the separation
property (2.i) holds.
Remark 2.14. The relation (16) therefore means that the Euclidean distance on Rd is a
strongly negative definite kernel. In fact, it can be shown that d(x, y) = kx − ykβ is a
11

strongly negative definite kernel for 0 < β < 2 [52]. When β = 2, it is easy to see that
Ed (Q, P ) is simply the distance between the distribution means and therefore cannot satisfy
the separation property (2.i).
Proof of Theorem 2.12 Let E(Q, P ) be the right-hand side of (17) and let S(µ, h) be the quantity
Ex,y∼µ [ d(x, y)h(x)h(y) ] that appears in clause (ii). Observe:
a) Let Q, P ∈ PX1 have respective density functions q(x) and p(x) with respect to measure
µ = (Q + P )/2. Function h = q − p then satisfies Eµ [h] =0, and



E(Q, P ) = Ex∼µ q(x)p(y) + q(y)p(x) − q(x)q(y) − p(x)p(y) d(x, y) = −S(µ, h) .
y∼µ

b) With µ ∈ PX1 , any h such that µ{h=0} < 1 (ie., non-µ-almost-surely-zero) and Eµ [h] =0 can
be written as a difference of two nonnegative functions h=q̃−p̃ such that Eµ [q̃] =Eµ [p̃] =ρ−1 >
0. Then, Q = ρ q̃ µ and P = ρ p̃ µ belong to PX1 , and
E(Q, P ) = −ρ S(µ, h) .
We can then prove the theorem:
i) From these observations, if E(Q, P ) ≥ 0 for all P, Q, then S(µ, h) ≤ 0 for all µ and h
such that Eµ [h(x)] = 0, implying (18). Conversely, assume there are Q, P ∈ PX1 such that
E(Q, P ) < 0. Using the weak law of large numbers [26] (see also Theorem 3.3 later in
this document,) we can find finite support distributions Qn , Pn such that E(Qn , Pn ) < 0.
Proceeding as in observation (a) then contradicts (18) because µ = (Qn + Pn )/2 has also
finite support.
ii) By contraposition, suppose there is µ and h such that µ{h=0}<1, Eµ [h(x)] = 0, and
S(µ, h) = 0. Observation (b) gives P 6= Q such that E(Q, P ) = 0. Conversely, suppose E(Q, P ) = 0. Observation (a) gives µ and h = q − p such that S(µ, h) = 0. Since h
must be zero, Q = P .

Requiring that d be a negative definite kernel is a quite strong assumption. For instance,
a classical result by Schoenberg [45] establishes that a squared distance is a negative definite kernel if and only if the whole metric space induced by this distance is isometric to a
subset of a Hilbert space and therefore has a Euclidean geometry:
Theorem 2.15 (Schoenberg, [45]). The metric space (X , d) is isometric to a subset of a
Hilbert space if and only if d2 is a negative definite kernel.
Requiring d to be negative definite (not necessarily a squared distance anymore) has
a similar impact on the geometry of the space PX1 equipped with the Energy Distance
(Theorem 2.17). Let x0 be an arbitrary origin point and define the symmetric triangular
gap kernel Kd as
∆

Kd (x, y) =

1
2

(d(x, x0 ) + d(y, x0 ) − d(x, y)) .

(19)

Proposition 2.16. The function d is a negative definite kernel if and only if Kd is a positive
definite kernel, that is,
n X
n
X
∀n ∈ N ∀x1 . . . xn ∈ X ∀c1 . . . cn ∈ R
ci cj Kd (xi , xj ) ≥ 0 .
i=1 j=1

12

Proof The proposition directly results from the identity
2

n X
n
X

ci cj Kd (xi , xj ) = −

n X
n
X

ci cj d(xi , xj ) ,

i=0 j=0

i=1 j=1

where x0 is the chosen origin point and c0 = −

Pn

i=1

ci .

Positive definite kernels in the machine learning literature have been extensively studied
in the context of the so-called kernel trick [46]. In particular, it is well known that the theory
of the Reproducing Kernel Hilbert Spaces (RKHS) [4, 1] establishes that there is a unique
Hilbert space H, called the RKHS, that contains all the functions
Φx : y ∈ X 7→ Kd (x, y)
and satisfies the reproducing property
∀x ∈ X ∀f ∈ H

hf, Φx i = f (x) .

(20)

We can then relate Ed (Q, P ) to the RKHS norm.
Theorem 2.17 ([47] [40, Chapter 21]). Let d be a negative definite kernel and let H be the
RKHS associated with the corresponding positive definite triangular gap kernel (19). We
have then
∀Q, P ∈ PX1 Ed (Q, P ) = k Ex∼Q [Φx ] − Ey∼P [Φy ] kH .
Proof We can write directly
Ed (Q, P )2

=



Ex,x0 ∼Q d(x, y) + d(x0 , y 0 ) − d(x, x0 ) − d(y, y 0 )
y,y 0 ∼P

=



Ex,x0 ∼Q Kd (x, x0 ) + Kd (y, y 0 ) − Kd (x, y) − Kd (x0 , y 0 )

=

hEQ [Φx ], EQ [Φx ]i + hEP [Φy ], EP [Φy ]i − 2 hEQ [Φx ], EP [Φy ]i

=

kEx∼Q [Φx ] − Ey∼P [Φy ] k2H ,

y,y 0 ∼P

where the first equality results from (19) and where the second equality results from the identities
hΦx , Φy i = Kd (x, y) and Ex,y [hΦx , Φy i] = hEx [Φx ], Ey [Φy ]i.

Remark 2.18. In the context of this theorem, the relation (16) is simply an analytic expression of the RKHS norm associated with the triangular gap kernel of the Euclidean distance.
Corollary 2.19. If d is a negative definite kernel, then Ed is a pseudodistance, that is, it
satisfies all the properties (2) of a distance except maybe the separation property (2.i).
Corollary 2.20. The following three conditions are then equivalent:
i) Ed satisfies all the properties (2) of a distance.
ii) d is a strongly negative definite kernel.
iii) the map P ∈ PX1 7→ EP [Φx ] ∈ H is injective (characteristic kernel [21].)

13

Maximum Mean Discrepancy
Ed (Q, P )

Following [21], we can then write Ed as an IPM:

=
=

kEQ [Φx ] − EP [Φx ] kH
sup hf, EP [Φx ] − EQ [Φx ]i
kf kH ≤1

=

sup EP [hf, Φx i] − EQ [hf, Φx i]
kf kH ≤1

=

sup EP [f (x)] − EQ [f (x)] .

(21)

kf kH ≤1

This last expression (21) is also called the Maximum Mean Discrepancy (MMD) associated
with the positive definite kernel Kd [21]. Conversely, for any positive definite kernel K,
the reader will easily prove that the symmetric function
dK (x, y) = kΦx − Φy k2H = K(x, x) + K(y, y) − 2K(x, y) ,
is a negative definite kernel, that dKd = d, and that
k EQ [Φx ] − EP [Φx ] k2H = EdK (Q, P )2 .

(22)

Therefore the ED and MMD formulations are essentially equivalent [47]. Note however
that the negative definite kernel dK defined above may not satisfy the triangular inequality
(its square root does.)
Remark 2.21. Because this equivalence was not immediately recognized, many important
concepts have been rediscovered with subtle technical variations. For instance, the notion
of characteristic kernel [21] depends subtly on the chosen domain for the map P 7→ EP [Φx ]
that we want injective. Corollary 2.20 gives a simple necessary and sufficient condition
when this domain is PX1 (with respect to the distance d). Choosing a different domain leads
to complications [51].

3

Energy Distance vs. 1-Wasserstein Distance

The dual formulation of the 1-Wasserstein (14) and the MMD formulation of the Energy
Distance (21) only differ by the use of a different family of critic functions: for all Q, P ∈
PX1 ,
W1 (Q, P ) = sup EQ [f (x)] − EP [f (x)] ,
f ∈Lip1

Ed (Q, P ) =

sup EP [f (x)] − EQ [f (x)] .
kf kH ≤1

At first sight, requiring that the functions f are 1-Lipschitz or are contained in the RKHS
unit ball seem to be two slightly different ways to enforce a smoothness constraint. Nevertheless, a closer comparison reveals very important differences.

14

3.1

Three quantitative properties

Although both the WD [55, Theorem 6.9] and the ED/MMD [49, Theorem 3.2] metrize the
weak convergence topology, they may be quantitatively very different and therefore hard
to compare in practical situations. The following upper bound provides a clarification.
Proposition 3.1. Let X be equipped with a distance d that is also a negative definite kernel.
Let the 1-Wasserstein distance W1 and the Energy Distance Ed be defined as in (8) and (17).
Ed (Q, P )2 ≤ 2W1 (Q, P ) .
This inequality is tight. It is indeed easy to see that it becomes an equality when both
P and Q are Dirac distributions.
The proof relies on an elementary geometrical lemma:
Lemma 3.2. Let A, B, C, D be four points in X forming a quadrilateral. The perimeter length d(A, B) + d(B, C) + d(C, D) + d(D, A) is longer than the diagonal lenghts
d(A, C) + d(B, D).
Proof of the lemma Summing the following triangular inequalities yields the result.
d(A, C) ≤ d(A, B) + d(B, C)

d(A, C) ≤ d(C, D) + d(D, A)

d(B, D) ≤ d(B, C) + d(C, D)

d(B, D) ≤ d(D, A) + d(A, B)

Proof of proposition 3.1 Let (x, y) and (x0 , y 0 ) be two independent samples of the optimal transport
plan π with marginals Q and P . Since they are independent,


2 Ex∼Q [d(x, y)] = E (x,y)∼π d(x, y 0 ) + d(x0 , y) .
(x0 ,y 0 )∼π

y∼P

Applying the lemma and rearranging
2Ex∼Q [d(x, y)] ≤ E
y∼P

(x,y)∼π
(x0 ,y 0 )∼π



d(x, y) + d(y, y 0 ) + d(y 0 , x0 ) + d(x0 , x)







= W1 (Q, P ) + E y∼P d(y, y 0 ) + W1 (Q, P ) + E x∼Q d(x, x0 ) .
y 0∼P

x0∼Q

Moving the remaining expectations to the left-hand side gives the result.

In contrast, the following results not only show that Ed can be very significantly smaller
than the 1-Wasserstein distance, but also show that this happens in the particularly important situation where one approximates a distribution with a finite sample.
Theorem 3.3. Let Q, P ∈ PX1 be two probability distributions
Pnon X . Let x1 . . . xn be n
independent Q-distributed random variables, and let Qn = n1 i=1 δxi be the corresponding empirical probability distribution. Let Ed be defined as in (17) with a kernel satisfying
d(x, x) = 0 for all x in X . Then,


Ex1 ...xn ∼Q Ed (Qn , P )2 = Ed (Q, P )2 + n1 Ex,x0 ∼Q [d(x, x0 )] ,
and


Ex1 ...xn ∼Q Ed (Qn , Q)2 =

1
n

Ex,x0 ∼Q [d(x, x0 )] = O(n−1 ) .

15

Therefore the effect of replacing Q by its empirical approximation disappears quickly,
like O(1/n), when n grows. This result is not very surprising when one notices that
Ed (Qn , P ) is a V-statistic [56, 48]. However it gives a precise equality with a particularly
direct proof.
Proof Using the following equalities in the definition (17) gives the first result.
"
#


n
1X
Ex1 ...xn ∼Q Ex∼Qn [d(x, y)] = Ex1 ...xn ∼Q
Ey∼P [d(xi , y)]
n i=1
y∼P
1X
E
[d(x, y)] = Ex∼Q [d(x, y)] .
=
n i x∼Q
y∼P
y∼P


#
"
X

1
0 
d(xi , xj ) 
= Ex1 ...xn ∼Q  2
Ex1 ...xn ∼Q E x∼Qn d(x, x )
n
x0∼Qn
i6=j


1
1 X
Ex∼Q [d(x, y)] = 1 −
Ex∼Q [d(x, y)] .
= 2
n
n
y∼Q
y∼Q
i6=j

Taking Q = P then gives the second result.

Comparable results for the 1-Wasserstein distance describe a convergence speed that
quickly becomes considerably slower with the dimension d > 2 of the sample space X
[50, 16, 18].
Theorem 3.4 ([18]). Let X be Rd , d > 2, equipped with the usual Euclidean distance. Let
Q ∈ PR2d and let Qn be defined as in Theorem 3.3. Then,
Ex1 ...xn ∼Q [ W1 (Qn , Q) ] = O(n−1/d ) .
The following example, inspired by [5], illustrates this slow rate and its consequences.
Example 3.5. Let Q be a uniform distribution supported by the unit sphere in Rd equipped
with the Euclidean distance. Let x1 . . . xn be n points sampled independently from this
distribution and let Qn be the corresponding empirical distribution. Let x be an additional
point
sampled from Q. It is well known6 that mini kx − xi k remains arbitrarily close to
√
2, say, greater than 1.2, with arbitrarily high probability when d  log(n). Therefore,
W1 (Qn , Q) ≥ 1.2

when n  exp(d).

In contrast, observe
W1 (Q, δ0 ) = W1 (Qn , δ0 ) = 1 .
In other words, as long as n  exp(d), a Dirac distribution in zero is closer to the empirical
distribution than the actual distribution [5].
Theorem 3.3 and Example 3.5 therefore show that Ed (Qn , Q) can be much smaller than
W1 (Qn , Q). They also reveal that the statistical properties of the 1-Wasserstein distance
are very discouraging. Since the argument of Example 3.5 naturally extends to the pWasserstein distance for all p ≥ 1, the problem seems shared by all Wasserstein distances.
6 The curious reader can pick an expression of F (t) = P {kx − x k < t} in [23], then derive an asymptotic
i
d
bound for P {mini kx − xi k < t} = 1 − (1 − Fd (t))n .

16

Remark 3.6. In the more realistic case where the 1-Lipschitz critic is constrained to belong
to a parametric
family with sufficient regularity, the bound of theorem 3.4 can be improved
p
to O( log(n)/n) with a potentially large constant [5]. On the other hand, constraining
the critic too severely might prevent it from distinguishing distributions that differ in meaningful ways.

3.2

WD and ED/MMD in practice

Why should we consider the Wasserstein Distance when the Energy Distance and Maximum Mean Discrepancy offer better statistical properties (Section 3.1) and more direct
learning algorithms [17, 33, 11] ?
The most impressive achievement associated with the implicit modeling approach certainly is the generation of photo-realistic random images that resemble the images provided
as training data [15, 41, 25]. In apparent contradiction with the statistical results of the previous section, and with a couple notable exceptions discussed later in this section, the visual
quality of the images generated using models trained by directly minimizing the MMD [17]
usually lags behind those obtained with the WD [3, 22, 25] and with the original Generative
Adversarial Network formulation7 [41].
Before discussing the two exceptions, it is worth recalling that the visual quality of the
generated images is a peculiar way to benchmark generative models. This is an incomplete
criterion because it does not ensure that the model generates images that cover all the space
covered by the training data. This is an interesting criterion because common statistical
metrics, such as estimates of the negative log-likelihood, are generally unable to indicate
which models generate the better-looking images [54]. This is a finicky criterion because,
despite efforts to quantify visual quality with well-defined scores [44], the evaluation of the
image quality fundamentally remains a beauty contest. Figure 2 nevertheless shows a clear
difference.
A few authors report good image generation results by using the ED/MMD criterion in
a manner that substantially changes its properties:
• The AE+GMMN approach [33] improves the pure MMD approach by training an
implicit model that does not directly generate images but targets the compact representation computed by a pretrained auto-encoder network. This changes a highdimensional image generation problem into a comparatively low-dimensional code
generation problem with a good notion of distance. There is independent evidence
that low-dimensional implicit models work relatively well with ED/MMD [11].
• The CramérGAN approach [7] minimizes the Energy Distance8 computed on the
representations produced by an adversarially trained 1-Lipschitz continuous transformation layer Tφ (x). The resulting optimization problem


min
max E(Tφ #Q, Tφ #Pθ ) ,
θ

Tφ ∈Lip1

7 Note
8 See

that it is then important to use the log(D) trick succinctly discussed in the original GAN paper [20].
[53] for the relation between Energy Distance and Cramér distance.

17

A sample of 64 training examples

Generated by the ED trained model

Generated by the WD trained model

Figure 2: Comparing images generated by a same implicit model trained with different
criteria. The top square shows a sample of 64 training examples represening bedroom
pictures. The bottom left square shows the images generated by a model trained with ED
using the algorithm of [11]. The bottom right square shows images generated by a model
trained using the WGAN-GP approach [22].

18

can then be re-expressed using the IPM form of the energy distance


min D(Q, P ) = max
max Ex∼Q [f (Tφ (x))] − Ex∼Pθ [f (Tφ (x))] .
Tφ ∈Lip1 kf kH ≤1

θ

The cost D(Q, P ) above is a new IPM that relies on critic functions of the form
f ◦ Tφ , where f belongs to the RKHS unit ball, and Tφ is 1-Lipschitz continuous.
Such hybrid critic functions still have smoothness properties comparable to that of
the Lipschitz-continuous critics of the 1-Wasserstein distance. However, since these
critic functions do not usually form a RKHS ball, the resulting IPM criterion no
longer belongs to the ED/MMD family.
• The same hybrid approach gives comparable results in GMMN-C [32] where the authors replace autoencoder of GMMN+AE with an adversarially trained transformer
layer.
On the positive side, such hybrid approaches may lead to more efficient training algorithms than those described in Section 2.3. The precise parametric structure of the transformation layer also provides the means to match what WGAN models achieve by selecting a
precise parametric structure for the critic. Yet, in order to understand these subtle effects, it
remains useful to clarify the similarities and differences between pure ED/MMD training
and pure WD training.

4

Length spaces

This section gives a concise review of the elementary metric geometry concepts useful for
the rest of our analysis. Readers can safely skip this section if they are already familiar
with metric geometry textbooks such as [12].
Rectifiable curves A continuous mapping γ : t ∈ [a, b] ⊂ R 7→ γt ∈ X defines a curve
connecting γa and γb . A curve is said to be rectifiable when its length
∆

L(γ, a, b) = sup

sup

n
X

n>1 a=t0 <t1 <···<tn =b
i=1

d(γti−1 , γt )

(23)

is finite. Intuitively, thanks to the triangular inequality, dividing the curve into n segments [γt−1 , γt ] and summing their sizes yields a quantity that is greater than d(γa , γb ) but
smaller than the curvilinear length of the curve. By construction, L(γ, a, b) ≥ d(γa , γb )
and L(γ, a, c) = L(γ, a, b) + L(γ, b, c) for all a ≤ b ≤ c.
Constant speed curves Together with the continuity of γ, this additivity property implies that the function t ∈ [a, b] 7→ L(γ, a, t) is nondecreasing and continuous [12, Prop. 2.3.4].
Thanks to the intermediate value theorem, when a curve is rectifiable, for all s ∈ [0, 1],
there is ts ∈ [a, b] such that L(γ, a, ts ) = s L(γ, a, b). Therefore, we can construct a new
curve γ̄ : s ∈ [0, 1] 7→ γ̄s = γts that visits the same points in the same order as curve
19

x

x

x

y

y

y

Figure 3: Consider R2 equipped with the L1 distance. Left: all points z in the gray area
are such that d(x, z) + d(z, y) = d(x, y). Center: all minimal geodesics connecting x
and y live in the gray area. Right: but not all curves that live in the gray area are minimal
geodesics.
γ and satisfies the property ∀s ∈ [0, 1], L(γ̄, 0, s) = sL(γ̄, 0, 1). Such a curve is called a
constant speed curve.
It is easy to check that the distance induced by d,

Length spaces

dˆ : (x, y) ∈ X 2 7→

L(γ, 0, 1) ∈ R∗+ ∪ {∞} ,

inf

(24)

γ:[a,b]→X
s.t. γa = x γb = y

indeed satisfies all the properties (2) of a distance. It is also easy to check that the distance
induced by dˆ coincides with dˆ [12, Prop. 2.3.12]. For this reason, a distance that satisfies
dˆ = d is called an intrinsic distance. A Polish metric space equipped with an intrinsic
distance is called an intrinsic Polish space. A metric space X equipped with an intrinsic
distance d is called a length space.
Minimal geodesics A curve γ : [a, b] → X that achieves the infimum in (24) is called a
shortest path or a minimal geodesic connecting γa and γb .
When the distance d is intrinsic, the length of a minimal geodesic γ satisfies the relation
ˆ a , γb ) = d(γa , γb ). When such a curve exists between any two points x, y
L(γ, a, b) = d(γ
such that d(x, y) < ∞, the distance d is called strictly intrinsic. A Polish space equipped
with a strictly intrinsic distance is called a strictly intrinsic Polish space.
Conversely, a rectifiable curve γ : [a, b] → X of length d(γa , γb ) is a minimal geodesic
because no curve joining γa and γb can be shorter. If there is such a curve between any two
points x, y such that d(x, y) < ∞, then d is a strictly intrinsic distance.
Characterizing minimal geodesics Let γ : [a, b] → X be a minimal geodesic in a
length space (X , d). Using the triangular inequality and (23),
∀a ≤ t ≤ b

d(γa , γb ) ≤ d(γa , γt ) + d(γt , γb ) ≤ L(γ, a, b) = d(γa , γb ) .
20

(25)

This makes clear that every minimal geodesic in a length space is made of points γt for
which the triangular inequality is an equality. However, as shown in Figure 3, this is not
sufficient to ensure that a curve is a minimal geodesic. One has to consider two intermediate
points:
Theorem 4.1. Let γ : [a, b] → X be a curve joining two points γa , γb such that d(γa , γb ) <
∞. This curve is a minimal geodesic of length d(γa , γb ) if and only if ∀ a ≤ t ≤ t0 ≤
b, d(γa , γt ) + d(γt , γt0 ) + d(γt0 , γb ) = d(γa , γb ) .
Corollary 4.2. Let γ : [0, 1] → X be a curve joining two points γ0 , γ1 ∈ X such that
d(γ0 , γ1 ) < ∞. The following three assertions are equivalent:
a) The curve γ is a constant speed minimal geodesic of length d(γ0 , γ1 ).
b) ∀ t, t0 ∈ [0, 1], d(γt , γt0 ) = |t − t0 | d(γ0 , γ1 ) .
c) ∀ t, t0 ∈ [0, 1], d(γt , γt0 ) ≤ |t − t0 | d(γ0 , γ1 ) .
Proof The necessity (⇒) is easily proven by rewriting (25) with two points t and t0 instead of just
one. The sufficiency (⇐) is proven by induction. Let
hn =

sup
a=t0 ≤t1 ≤···≤tn ≤b

n
X

d(γti−1 , γti ) + d(γtn , γb ) .

i=1

The hypothesis implies that h2 = d(γa , γb ). We now assuming that the induction hypothesis hn =
d(γa , γb ) is true for some n ≥ 2. For all partition a = t0 ≤ t1 . . . tn ≤ b, using twice the triangular
inequality and the induction hypothesis,
d(γa , γb ) ≤ d(γa , γtn ) + d(γtn , γb ) ≤

n
X

d(γti−1 , γti ) + d(γtn , γb ) ≤ hn = d(γa , γb ) .

i=1

Therefore
n+1
X

Pn

i=1

d(γti−1 , γti ) = d(γa , γtn ). Then, for any tn+1 ∈ [tn , b],

d(γti−1 , γti ) + d(γtn+1 , γb ) = d(γa , γtn ) + d(γtn , γtn+1 ) + d(γtn+1 , γb ) = d(γa , γb ) .

i=1

Since this is true for all partitions, hn+1 = d(γa , γb ). We just have proved by induction that hn =
d(γa , γb ) for all n. Therefore L(γ, a, b) = supn hn = d(γa , γb ).

5

Minimal geodesics in probability space

We now assume that X is a strictly intrinsic Polish space and we also assume that its
distance d is never infinite. Therefore any pair of points in X is connected by at least one
minimal geodesic. When the space PX of probability distributions is equipped with one of
the probability distances discussed in section 2, it often becomes a length space itself and
inherits some of the geometrical properties of X . Since this process depends critically on
how the probability distance compares different distributions, understanding the geodesic
structure of PX reveals fundamental differences between probability distances.
This approach is in fact quite different from the celebrated work of Amari on Information Geometry [2]. We seek here to understand the geometry of the space of all probability measures equipped with different distances. Information Geometry characterizes the
21

Riemannian geometry of a parametric family of probability measures under the KullbackLeibler distance. This difference is obviously related to the contrast between relying on
good distances versus relying on good model families discussed in Section 1. Since we
are particularly interested in relatively simple models that have a physical or causal interpretation but cannot truly represent the actual data distribution, we cannot restrict our
geometrical insights to what happens within the model family.

5.1

Mixture geodesics

For any two distributions P0 , P1 ∈ PX , the mixture distributions
∀t ∈ [0, 1] Pt = (1−t)P0 + tP1

(26)

form a curve in the space of distributions PX .
Theorem 5.1. Let PX be equipped with a distance D that belongs to the IPM family (5).
Any mixture curve (26) joining two distributions P0 , P1 ∈ PX such that D(P0 , P1 ) < ∞ is
a constant speed minimal geodesic, making D a strictly intrinsic distance.
Proof The proof relies on Corollary 4.2: for all t, t0 ∈ [0, 1],

D(Pt , Pt0 ) = sup E(1−t)P0 +tP1 [f (x)] − E(1−t0 )P0 +t0 P1 [f (x)]
f ∈Q

= sup
f ∈Q



−(t−t0 )EP0 [f (x)] + (t−t0 )EP1 [(] f (x))

= |t−t0 | sup { EP0 [f (x)] − EP1 [f (x)]} .
f ∈Q

where the last equality relies on the fact that if f ∈ Q, then −f ∈ Q. By Corollary 4.2, the
mixture curve is a constant speed minimal geodesic. Since this is true for any P0 , P1 ∈ PX such that
D(P0 , P1 ) < ∞, the distance D is strictly intrinsic.

Remark 5.2. Although Theorem 5.1 makes (PX , D) a length space, it does not alone make
it a strictly intrinsic Polish space. One also needs to establish the completeness and separability9 properties of a Polish space. Fortunately, these properties are true for both (PX1 , W1 )
and (PX1 , Ed ) when the ground space is Polish.10
Since both the 1-Wasserstein distance W1 and the Energy Distance or MMD Ed belong
to the IPM family, PX equipped with either distance is a strictly intrinsic Polish space.
Any two probability measures are connected by at least one minimal geodesic, the mixture
geodesic. We shall see later that the 1-Wasserstein distance admits many more minimal
geodesics. However, in the case of ED/MMD distances, mixture geodesics are the only
minimal geodesics.
9 For instance the set of probability measures on R equipped with the total variation distance (6) is not separable
because any dense subset needs one element in each of the disjoint balls Bx = { P ∈PR : DT V (P, δx )<1/2 }.
10 For the Wasserstein distance, see [55, Theorem 6.18]. For the Energy distance, both properties can be derived
from Theorem 2.17 after recaling that ΦX ⊂ H is both complete and separable because it is isometric to X which
is Polish.

22

Theorem 5.3. Let K be a characteristic kernel and let PX be equipped with the MMD
distance EdK . Then any two probability measures P0 , P1 ∈ PX such that EdK (P0 , P1 ) <
∞ are joined by exactly one constant speed minimal geodesic, the mixture geodesic (26).
Note that EdK is also the ED for the strongly negative definite kernel dK .
Proof Theorem 5.1 already shows that any two measures P0 , P1 ∈ PX are connected by the mixture
geodesic Pt . We only need to show that it is unique. For any t ∈ [0, 1], the measure Pt belongs to
the set

P ∈ PX : EdK (P0 , P ) = tD and EdK (P, P1 ) = (1−t)D ⊂ PX
(27)
where D = EdK (P0 , P1 ). Thanks to Theorem 2.17, EPt [Φx ] must belong to the set

Ψ ∈ H : kEP0 [Φx ] − ΨkH = tD and kΨ − EP1 [Φx ] kH = (1−t)D ⊂ H .

(28)

with D = kEP0 [Φx ] − EP1 [Φx ] kH . Since there is only one point Ψ that satisfies these conditions
in H, and since Corollary 2.20 says that the map P 7→ EP [Φx ] is injective, there can only be one P
satisfying (27) and this must be Pt . Therefore the mixture geodesic is the only one.

5.2

Displacement geodesics

Displacement geodesics in the Euclidean case Let us first assume that X is a Euclidean
space and PX is equipped with the p-Wasserstein distance Wp . Let P0 , P1 ∈ PXp be two
distributions with optimal transport plan π. The displacement curve joining P0 to P1 is
formed by the distributions

∀t ∈ [0, 1] Pt = (1−t)x + ty #π(x, y) .
(29)
Intuitively, whenever the optimal transport plan specifies that a grain of probability mass
must be transported from x to y in X , we follow the shortest path connecting x and y, that
is, in a Euclidean space, a straight line, but we drop the grain after performing a fraction t
of the journey.
Proposition 5.4. Let X be a Euclidean space and let PX be equipped with the p-Wasserstein
distance (8) for some p ≥ 1. Any displacement curve (29) joining two distributions P0 , P1
such that Wp (P0 , P1 ) < ∞ is a constant speed minimal geodesic, making Wp a strictly
intrinsic distance.
Proof Let π01 be the optimal transport plan between P0 and P1 . For all t, t0 ∈ [0, 1], define a
tentative transport plan πtt0 between Pt and Pt0 as

πtt0 = (1−t)x + ty, (1−t0 )x + t0 y #π01 (x, y) ∈ Π(Pt , Pt0 ) .
Then
Wp (Pt , Pt0 )p ≤ E(x,y)∼πtt0 [ kx − ykp ]


= E(x,y)∼π k(1−t)x + ty − (1−t0 )x − t0 ykp
= |t − t0 |p E(x,y)∼π [ kx − yk ] = |t − t0 |p Wp (P0 , P1 )p .

23

By Corollary 4.2, the displacement curve is a constant speed minimal geodesic. Since this is true for
any P0 , P1 ∈ PX such that Wp (P0 , P1 ) < ∞, the distance Wp is strictly intrinsic.

When p > 1, it is a well-known fact that the displacement geodesics are the only
geodesics of PX equipped with the Wp distance.
Proposition 5.5. The displacement geodesics (29) are the only constant speed minimal
geodesics of PX equipped with the p-Wasserstein distance Wp with p > 1.
This is a good opportunity to introduce a very useful lemma.
Lemma 5.6 (Gluing). Let Xi , i = 1, 2, 3 be Polish metric spaces. Let probability measures
µ12 ∈ PX1 ×X2 and µ23 ∈ PX2 ×X3 have the same marginal distribution µ2 on X2 . Then
there exists µ ∈ PX1 ×X2 ×X3 such that (x, y)#µ(x, y, z) = µ12 and (y, z)#µ(x, y, z) = µ23 .
Proof notes for Lemma 5.6 At first sight, this is simply P (x, y, z) = P (x|y)P (z|y)P (y) with
µ12 =P (x, y), µ23 =P (y, z). Significant technical difficulties arise when P (y) = 0. This is where
one needs the topological properties of a Polish space [8].
Proof of Proposition 5.5 Let t ∈ [0, 1] 7→ Pt be a constant speed minimal geodesic. Any point Pt
must satisfy the equality
Wp (P0 , Pt ) + Wp (Pt , P1 ) = Wp (P0 , P1 )
Let π0 and π1 be the optimal transport plans associated with Wp (P0 , Pt ) and Wp (Pt , P1 ) and construct π3 ∈ PX 3 by gluing them. Then we must have
1/p
1/p
E(x,y,z)∼π3 [ kx − ykp ]
+ E(x,y,z)∼π3 [ ky − zkp ]
= Wp (P0 , P1 ) ≤

E(x,y,z)∼π3 [ kx − zkp ]

1

p

.

Thanks to the properties of the Minkowski’s inequality, this can only happen for p > 1 if there exists
λ ∈ [0, 1] such that, π3 -almost surely, kx−yk=λkx−zk and ky−zk=(1−λ)kx−zk. This constant
can only be t because WP (P0 , Pt ) = tWp (P0 , P1 ) on a constant speed minimal geodesic. Therefore
y = tx + (1−t)y, π3 -almost surely. Therefore Pt = y #π(x, y, z) describes a displacement curve as
defined in (29).

Note however that the displacement geodesics are not the only minimal geodesics of the
1-Wasserstein distance W1 . Since W1 is an IPM (14), we know that the mixture geodesics
are also minimal geodesics (Theorem 5.1). There are in fact many more geodesics. Intuitively, whenever the optimal transport plan from P0 to P1 transports a grain of probability
from x to y, we can drop the grain after a fraction t of the journey (displacement geodesics),
we can randomly decide whether to transport the grain as planned (mixture geodesics), we
can also smear the grain of probability along the shortest path connecting x to y, and we
can do all of the above using different t in different parts of the space.

24

Displacement geodesics in the general case The rest of this section reformulates these
results to the more general situation where X is a strictly intrinsic Polish space. Rather
than following the random curve approach described in [55, Chapter 7], we chose a more
elementary approach because we also want to characterize the many geodesics of W1 . Our
definition is equivalent for p>1 and subtly weaker for p=1.
The main difficulties are that we may no longer have a single shortest path connecting
two points x, y ∈ X , and that we may not be able to use the push-forward formulation
(29) because the function that returns the point located at position t along a constant speed
minimal geodesic joining x to y may not satisfy the necessary measurability requirements.
Definition 5.7 (Displacement geodesic). Let X be a strictly intrinsic Polish metric space
and let PXp be equipped with the p-Wasserstein distance Wp . The curve t ∈ [0, 1] 7→ Pt ∈
PXp is called a displacement geodesic if, for all 0≤t≤t0 ≤1, there is a distribution π4 ∈ PX 4
such that
i) The four marginals of π4 are respectively equal to P0 , Pt , Pt0 , P1 .
ii) The pairwise marginal (x, z)#π4 (x, u, v, z) is an optimal transport plan
Wp (P0 , P1 )p = E(x,u,v,z)∼π4 [d(x, z)p ] .
iii) The following relations hold π4 (x, u, v, z)-almost surely:
d(x, u) = t d(x, z) ,

d(u, v) = (t0 − t) d(x, z) ,

d(v, z) = (1−t0 ) d(x, z) .

Proposition 5.8. Definition 5.7 indeed implies that Pt is a constant speed minimal geodesic
of length Wp (P0 , P1 ). Furthermore, for all 0 ≤ t ≤ t0 ≤ 1, all the pairwise marginals of
π4 are optimal transport plans between their marginals.
Proof For all 0 ≤ t ≤ t0 ≤ 1, we have
Wp (Pt , Pt0 )p ≤ E(x,u,v,z)∼π4 [d(u, v)p ]
= (t−t0 )p E(x,u,v,z)∼π4 [d(x, z)p ] = (t−t0 )p Wp (P0 , P1 )p .
By Corollary 4.2, the curve Pt is a constant speed minimal geodesic. We can then write
1/p
t0 Wp (P0 , P1 ) = Wp (P0 , Pt0 ) ≤ E(x,u,v,z)∼π4 [d(x, v)p ]
1/p
≤ E(x,u,v,z)∼π4 [(d(x, u) + d(u, v))p ]
1/p
1/p
≤ E(x,u,v,z)∼π4 [d(x, u)p ]
+ E(x,u,v,z)∼π4 [d(u, v)p ]
1/p
1/p
≤ t E(x,u,v,z)∼π4 [d(x, z)p ]
+ (t0 −t) E(x,u,v,z)∼π4 [d(x, z)p ]
= t0 Wp (P0 , P1 ) ,
where the third inequality is Minkowski’s inequality. Since both ends of this chain of inequalities
are equal, these inequalities must be equalities, implying that (x, v)#π4 is an optimal transport plan
between P0 and Pt0 . We can do likewise for all pairwise marginals of π4 .

The proposition above does not establish that a displacement geodesic always exists.
As far as we know, this cannot be established without making an additional assumption
such as the local compacity of the intrinsic Polish space X . Since it is often easy to directly
define a displacement geodesic as shown in (29), we omit the lengthy general proof.
25

Theorem 5.9. Let X be a strictly intrinsic Polish metric space and let P0 , P1 be two distributions of PXp equipped with the p-Wasserstein with p > 1. The only constant speed
minimal geodesics of length Wp (P0 , P1 ) joining P0 and P1 are the displacement geodesics.
Proof Let Pt be a constant speed minimal geodesic of length Wp (P0 , P1 ). By Theorem 4.1, for all
0 ≤ t ≤ t0 ≤ 1,
Wp (P0 , Pt ) + Wp (Pt , Pt0 ) + Wp (Pt0 , P1 ) = Wp (P0 , P1 ) .
Let π4 be constructed by gluing optimal transport plans associated with the three distances appearing
on the left hand side of the above equality. We can then write
1/p
Wp (P0 , P1 ) ≤ E(x,u,v,z)∼π4 [d(x, z)p ]
1/p
≤ E(x,u,v,z)∼π4 [(d(x, u) + d(u, v) + d(v, z))p ]
1/p
1/p
≤ E(x,u,v,z)∼π4 [d(x, u)p ]
+ E(x,u,v,z)∼π4 [d(u, v)p ]
1/p
+ E(x,u,v,z)∼π4 [d(v, z)p ]
= Wp (P0 , Pt ) + Wp (Pt , Pt0 ) + Wp (Pt0 , P1 ) = Wp (P0 , P1 ) .
Since this chain of inequalities has the same value in both ends, all these inequalities must be equalities. The first one means that π4 is an optimal transport plan for Wp (P0 , P1 ). The second one
means that (d(x, u) + d(u, v) + d(v, z) = d(x, z), π4 -almost surely. When p > 1, the third one,
Minkowski’s inequality can only be an inequality if there are scalars λ1 +λ2 +λ3 =1 such that, π4 almost surely, d(x, u) = λ1 d(x, z), d(x, u) = λ2 d(x, z), and d(v, z) = λ3 d(x, z). Since Pt must
satisfy Corollary 4.2, these scalars can only be λ1 = t, λ2 = t0 −t, and λ3 = 1−t0 .

Minimal geodesics for the 1-Wasserstein distance We can characterize the many minimal geodesics of the 1-Wasserstein distance using a comparable strategy.
Theorem 5.10. Let X be a strictly intrinsic Polish space and let PX1 be equipped with the
distance W1 . A curve t ∈ [a, b] 7→ Pt ∈ PX1 joining Pa and Pb is a minimal geodesic of
length W1 (Pa , Pb ) if and only if, for all a ≤ t ≤ t0 ≤ b, there is a distribution π4 ∈ PX 4
such that
i) The four marginals of π4 are respectively equal to Pa , Pt , Pt0 , Pb .
ii) The pairwise marginal (x, z)#π4 (x, u, v, z) is an optimal transport plan
Wp (Pa , Pb ) = E(x,u,v,z)∼π4 [d(x, z)] .
iii) The following relation holds π4 (x, u, v, z)-almost surely:
d(x, u) + d(u, v) + d(v, z) = d(x, z) .
It is interesting to compare this condition to Theorem 4.1. Instead of telling us that two
successive triangular inequalities in the probability space (PX1 , W1 ) must be an equality,
this result tells us that the same holds almost-surely in the sample space (X , d). In particular, this means that x, u, v, and z must be aligned along a geodesic of X . In the case of a
mixture geodesic, u and v coincide with x or z. In the case of a displacement geodesic, u
26

and v must be located at precise positions along a constant speed geodesic joining x to z.
But there are many other ways to fulfil these conditions.
Proof When Pt is a minimal geodesic, Theorem 4.1 states
∀a ≤ t ≤ t0 ≤ b

W1 (Pa , Pt ) + W1 (Pt , Pt0 ) + W1 (Pt0 , Pb ) = W1 (Pa , Pb ) .

Let π4 be constructed by gluing optimal transport plans associated with the three distances appearing
on the left hand side of the above equality. We can then write
E(x,u,v,z)∼π4 [d(x, z)] ≤ E(x,u,v,z)∼π4 [d(x, u) + d(u, v) + d(v, z)]
= W1 (Pa , Pb ) ≤ E(x,u,v,z)∼π4 [d(x, z)] .
Since this chain of equalities has the same value on both ends, all these inequalities must be equalities.
The first one means that d(x, u) + d(u, v) + d(v, z) = d(x, z), π4 -almost surely. The second one
means that (x, z)#π4 is an optimal transport plan.
Conversely, assume Pt satisfies the conditions listed in the proposition. We can then write, for
all a ≤ t ≤ t0 ≤ b,
W1 (Pa , Pb ) = E(x,u,v,z)∼π4 [d(x, z)]
= E(x,u,v,z)∼π4 [d(x, u) + d(u, v) + d(v, z)]
= W1 (Pa , Pt ) + W1 (Pt , Pt0 ) + W1 (Pt0 , Pb ) ,
and we conclude using Theorem 4.1.

6

Unsupervised learning and geodesic structures

We have seen in the previous section that the geometry of the space PX of probability distributions changes considerably with our choice of a probability distance. Critical aspects
of these possible geometries can be understood from the characterization of the shortest
paths between any two distributions:
• With the Energy Distance Ed or the Maximum Mean Discrepancy EdK , the sole shortest path is the mixture geodesic (Theorem 5.3.)
• With the p-Wasserstein distance Wp , for p > 1, the sole shortest paths are displacement geodesics (Theorem 5.9.)
• With the 1-Wasserstein distance W1 , there are many shortest paths, including the
mixture geodesic, all the displacement geodesics, and all kinds of hybrid curves (Theorem 5.10.)
The purpose of this section is to investigate the consequences of these geometrical
differences on unsupervised learning problems. In the following discussion, Q ∈ PX
represents the data distribution which is only known through the training examples, and
F ⊂ PX represent the family of parametric models Pθ ∈ PX considered by our learning
algorithm.
Minimal geodesics in length spaces can sometimes be compared to line segments in Euclidean spaces because both represent shortest paths between two points. This association
27

provides the means to extend the familiar Euclidean notion of convexity to length spaces.
This section investigates the geometry of implicit modeling learning problems through the
lens of this generalized notion of convexity.

6.1

Convexity à-la-carte

We now assume that PX is a strictly intrinsic Polish space equipped with a distance D. Let
C be a family of smooth constant speed curves in PX . Although these curves need not be
minimal geodesics, the focus of this section is limited to three families of curves defined in
Section 5:
• the family Cg (D) of all minimal geodesics in (PX , D),
• the family Cd (Wp ) of the displacement geodesics in (PXp , Wp ),
• the family Cm of the mixture curves in PX .
Definition 6.1. Let PX be a strictly intrinsic Polish space. A closed subset F ⊂ PX is
called convex with respect to the family of curves C when C contains a curve t ∈ [0, 1] 7→
Pt X connecting P0 and P1 whose graph is contained in F, that is, Pt ∈ F for all t ∈ [0, 1].
Definition 6.2. Let PX be a strictly intrinsic Polish space. A real-valued function f defined
on PX is called convex with respect to the family of constant speed curves C when, for every
curve t ∈ [0, 1] 7→ Pt ∈ PX in C, the function t ∈ [0, 1] 7→ f (Pt ) ∈ R is convex.
For brevity we also say that F or f is geodesically convex when C = Cg (D), mixture
convex when C = Cm , and displacement convex when C = Cd (Wp ).
Theorem 6.3 (Convex optimization à-la-carte). Let PX be a strictly intrinsic Polish space
equipped with a distance D. Let the closed subset F ⊂ PX and the cost function f : X 7→
R be both convex with respect to a same family C of constant speed curves. Then, for all
M ≥ minF (f ),
i) the level set L(f, F, M ) = {P ∈ F : f (P ) ≤ M } is connected,
ii) for all P0 ∈ F such that f (P0 ) > M and all  > 0, there exists P ∈ F such that
D(P, P0 ) = O() and f (P ) ≤ f (P0 ) − (f (P0 )−M ).
This result essentially means that it is possible to optimize the cost function f over F
with a descent algorithm. Result (i) means that all minima are global minima, and result
(ii) means that any neighborhood of a suboptimal distribution P0 contains a distribution P
with a sufficiently smaller cost to ensure that the descent will continue.
Proof (i): Let P0 , P1 ∈ L(f, F, M ). Since they both belong to F, C contains a curve t ∈ [0, 1] 7→
Pt ∈ F joining P0 and P1 . For all t ∈ [0, 1], we know that Pt ∈ F and, since t 7→ f (Pt ) is a convex
function, we can write f (Pt ) ≤ (1 − t)f (P0 ) + tf (P1 ) ≤ M . Therefore Pt ∈ L(f, F, M ). Since
this holds for all P0 , P1 , L(f, F, M ) is connected.
(ii): Let P1 ∈ L(f, F, M ). Since F is convex with respect to C, C contains a constant speed
curve t ∈ [0, 1] 7→ Pt ∈ F joining P0 and P1 . Since this is a constant speed curve, d(P0 , P ) ≤
D(P0 , P1 ) , and since t 7→ f (Pt ) is convex, f (P ) ≤ (1 − )f (P0 ) + f (P1 ), implies f (P ≤
f (P0 ) − (f (P0 ) − M ) .

One particularly striking aspect of this result is that it does not depend on the parametrization of the family F. Whether the cost function C(θ) = f (Gθ #µz ) is convex or not is
28

irrelevant: as long as the family F and the cost function f are convex with respect to a
well-chosen set of curves, the level sets of the cost function C(θ) will be connected, and
there will be a nonincreasing path connecting any starting point θ0 to a global optimum θ∗ .
It is therefore important to understand how the definition of C makes it easy or hard to
ensure that both the model family F and the training criterion f are convex with respect to
C.

6.2

The convexity of implicit model families

We are particularly interested in the case of implicit models (Section 2.2) in which the distributions Pθ are expressed by pushing the samples z ∈ Z of a known source distribution
µz ∈ PZ through a parametrized generator function Gθ (z) ∈ X . This push-forward operation defines a deterministic coupling between the distributions µz and Pθ because the
function Gθ maps every source sample z ∈ Z to a single point Gθ (z) in X . In contrast, a
stochastic coupling distribution πθ ∈ Π(µz , Pθ ) ⊂ PZ×X would be allowed to distribute
a source sample z ∈ Z to several locations in X , according to the conditional distribution
πθ (x|z).
The deterministic nature of this coupling makes it very hard to achieve mixture convexity using smooth generator functions Gθ .
Example 6.4. Let the distributions P0 , P1 ∈ F associated with parameters θ0 and θ1 have
disjoint supports separated by a distance greater than D>0. Is there a continuous path
t ∈ [0, 1] 7→ θt in parameter space such that Gθt #µz is the mixture Pt = (1−t)P0 + P1 ?
If we assume there is such a path, we can write
µz {Gθ0 (z) ∈ supp(P0 )} = 1
and, for any >0,
µz {Gθ (z) ∈ supp(P1 )} =  > 0 .
Therefore, for all >0, there exists z∈Z such that d(Gθ0 (z), Gθ (z))≥D. Clearly such
a generator function is not compatible with the smoothness requirements of an efficient
learning algorithm.
In contrast, keeping the source sample z constant, a small change of the parameter θ
causes a small displacement of the generated sample Gθ (z) in the space X . Therefore we
can expect that such an implicit model family has a particular affinity for displacement
geodesics.
It is difficult to fully assess the consequences of the quasi-impossibility to achieve mixture convexity with implicit models. For instance, although the Energy Distance Ed (Q, Pθ )
is a mixture convex function (see Proposition 6.6 in the next section), we cannot expect that
a family F of implicit models will be mixture convex.
Example 6.5. Let µz be the uniform distribution on {−1, +1}. Let the parameter θ be
constrained to the square [−1, 1]2 ⊂ R2 and let the generator function be
Gθ : z ∈ {−1, 1} 7→ Gθ (z) = zθ .

29

!"#$ %

&$'

(

!" #$% &

#

'%(

)

#
Local minimum

Global minimum

Global minimum

"

"

!

!

$"

$"
Global minimum

$"

Local minimum

!

"

Global minimum

#

$"

!

"

#

Figure 4: Level sets for the problems described in Example 6.5.
The corresponding model family is

F = Pθ = 21 (δθ +δ−θ ) : θ ∈ [−1, 1] × [−1, 1] .
It is easy to see that this model family is displacement convex but not mixture convex.
Figure 4 shows the level sets for both criteria E(Q, Pθ ) and W1 (Q, Pθ ) for the target distribution Q = P(2,2) ∈
/ F. Both criteria have the same global minima in (1, 1) and (−1, −1).
However the energy distance has spurious local minima in (−1, 1) and (1, −1) with a relatively high value of the cost function.
Constructing such an example in R2 is nontrivial. Whether such situations arise commonly in higher dimension is not known. However we empirically observe that the optimization of a MMD criterion on high-dimensional image data often stops with unsatisfactory results (Section 3.2).

6.3

The convexity of distances

Let Q ∈ PX be the target distribution for our learning algorithm. This could be the true data
distribution or the empirical training set distribution. The learning algorithm minimizes the
cost function
∆
min C(θ) = D(Q, Pθ ) .
(30)
Pθ ∈F

The cost function itself is therefore a distance. Since such a distance function is always
convex in a Euclidean space, we can ask whether a distance in a strictly intrinsic Polish
space is geodesically convex. This is not always the case. Figure 5 gives a simple counterexample in R2 equipped with the L1 distance.
Yet we can give a positive answer for the mixture convexity of IPM distances.

30

Figure 5: Geodesic convexity often differs from Euclidean convexity in important ways.
There are many different minimal geodesics connecting any two points in R2 equipped
with the L1 distance (see also Figure 3). The cross-shaped subset of R2 shown in the left
plot is geodesically convex. The center plot shows that the intersection of two geodesically
convex sets is not necessarily convex or even connected. The right plot shows that two
points located inside the unit ball can be connected by a minimal geodesic that does not stay
in the unit ball. This means that the L1 distance itself is not convex because its restriction
to that minimal geodesic is not convex.
Proposition 6.6. Let PX be equipped with a distance D that belongs to the IPM family (5).
Then D is mixture convex.
Proof Let t ∈ [0, 1] 7→ Pt = (1−t)P0 + tP1 be a mixture curve. Theorem 5.1 tells us that such
mixtures are minimal geodesics. For any target distribution Q we can write
D(Q, Pt ) = supf ∈Q { EQ [f (x)] − EPt [f (x)] }



= supf ∈Q (1−t) EQ [f (x)] − EP0 [f (x)] + t EQ [f (x)] − EP1 [f (x)]
≤ (1−t) D(Q, P0 ) + t D(Q, P1 ) .
The same holds for any segment t ∈ [t1 , t2 ] ⊂ [0, 1] because such segments are also mixture curves
up to an affine reparametrization. Therefore t 7→ D(Q, Pt ) is convex.

Therefore, when D is an IPM distance, and when F is a mixture convex family of
generative models, Theorem 6.3 tells us that a simple descent algorithm can find the global
minimum of (30). As discussed in Example 6.4, it is very hard to achieve mixture convexity
with a family of implicit models. But this could be achieved with nonparametric techniques.
However the same does not hold for displacement convexity. For instance, the Wasserstein distance is not displacement convex, even when the sample space distance d is geodesically convex, and even when the sample space is Euclidean.
Example 6.7. Let X be R2 equipped with the Euclidean distance. Let Q be the uniform
distribution on the unit circle, and let P`,θ be the uniform distribution on a line segment of
length 2` centered on the origin (Figure 6, left). The distance W1 (Q, P`,θ ) is independent
on θ and decreases when ` ∈ [0, 1] increases (Figure 6, center). Consider a displacement
geodesic t ∈ [0, 1] 7→ Pt where P0 = P`,θ0 and P1 = P`,θ1 for 0<θ0 <θ1 <π/2. Since the

31

Q

Q

W1 (Q, P`,θ )
1

Pt

0.8

θ

2`

P1

0.6
0.4

P`,θ

0.2

P0
0

0.2 0.4 0.6 0.8

`

Figure 6: Example 6.7 considers a target distribution Q that is uniform on the R2 unit
circle and a displacement geodesic between two line segments centered on the origin and
with identical length (right plot.)
space R2 is Euclidean, displacements occur along straight lines. Therefore the distribution
Pt for 0<t<1 is uniform on a slightly shorter line segment (Figure 6, right), implying
W1 (Q, Pt ) > W1 (Q, P0 ) = W1 (Q, P1 ) .
Therefore the distance function P 7→ W1 (Q, P ) is not displacement convex.
Although this negative result prevents us from invoking Theorem 6.3 for the minimization of the Wasserstein distance, observe that the convexity violation in Example 6.7 is
rather small. Convexity violation examples are in fact rather difficult to construct. The following section shows that we can still obtain interesting guarantees by bounding the size
of the convexity violation.

6.4

Almost-convexity

We consider in this section that the distance d is geodesically convex in X : for any point
x ∈ X and any constant speed geodesic t ∈ [0, 1] 7→ γt ∈ X ,
d(x, γt ) ≤ (1−t) d(x, γ0 ) + t d(x, γ1 ) .
This requirement is of course verified when X is an Euclidean space. This is also trivially
true when X is a Riemannian or Alexandrov space with nonpositive curvature [12].
The following result bounds the convexity violation:
Proposition 6.8. Let X be a strictly intrinsic Polish space equipped with a geodesically
convex distance d and let PX1 be equipped with the 1-Wasserstein distance W1 . For all
Q ∈ PX and all displacement geodesics t ∈ [0, 1] 7→ Pt ,
∀t ∈ [0, 1] W1 (Q, Pt ) ≤ (1−t) W1 (Q, P0 ) + t W1 (Q, P1 ) + 2t(1 − t)K(Q, P0 , P1 )
with K(Q, P0 , P1 ) ≤ 2 min Eu∼Q [d(u, u0 )] .
u0 ∈X

32

π3 (x, y, z)
y ∼ Pt

x ∼ P0
[ 1−t ]

π0

ux ∼ Q

z ∼ P1
[t]

u∼Q

π1

uz ∼ Q

Figure 7: The construction of π ∈ PX 6 in the proof of Proposition 6.8.
Proof The proof starts with the construction of a distribution π ∈ PX 6 illustrated in Figure 7. Thanks
to Proposition 5.8 we can construct a distribution π3 (x, y, z) ∈ PX 3 whose marginals are respectively
P0 , Pt , P1 , whose pairwise marginals are optimal transport plans, and such that, π3 -almost surely,
d(x, y) = t d(x, z) d(y, z) = (1−t) d(x, z) .
We then construct distribution π5 (x, y, z, ux , uz ) by gluing π3 with the optimal transport plans π0
between P0 and Q and π1 between P1 and Q. Finally π(x, y, z, ux , uz , u) is constructed by letting
u be equal to ux with probability 1−t and equal to uz with probability t. The last three marginals of
π are all equal to Q.
Thanks to the convexity of d in X , the following inequalities hold π-almost surely:
d(ux , y) ≤ (1−t) d(ux , x) + t d(ux , z)
≤ (1−t) d(ux , x) + t d(uz , z) + t d(ux , uz )
d(uz , y) ≤ (1−t) d(uz , x) + t d(uz , z)
≤ (1−t) d(ux , x) + t d(uz , z) + (1 − t) d(ux , uz ) .
Therefore
W1 (Q, Pt ) ≤ Eπ [d(u, y)]
= Eπ [(1−t)d(ux , y) + td(uz , y)]
≤ Eπ [(1−t) d(ux , x) + t d(uz , z) + 2t(1 − t) d(ux , uz )]
= (1−t) W1 (Q, P0 ) + t W1 (Q, P1 ) + 2t(1 − t) Eπ [d(ux , uz )] .
For any u0 ∈ X , the constant K in the last term can then be coarsely bounded with
K(Q, P0 , P1 ) = Eπ [d(ux , uz )]
≤ Eπ [d(ux , u0 )] + Eπ [d(u0 , uz )] = 2Eu∼Q [d(u, u0 )] .
Taking the minimum over u0 gives the final result.

When the optimal transport plan from P0 to P1 specifies that a grain of probability
must be transported from x to z, its optimal coupling counterpart in Q moves from ux
33

to uz . Therefore the quantity K(Q, P0 , P1 ) quantifies how much the transport plan from
Pt to Q changes when Pt moves along the geodesic. This idea could be used to define a
Lipschitz-like property such as
∀P0 , P1 ∈ FL ⊂ F

K(Q, P0 , P1 ) ≤ LW1 (P0 , P1 ) .

Clearly such a property does not hold when the transport plan changes very suddenly. This
only happens in the vicinity of distributions Pt than can be coupled with Q using multiple
transport plans.
Unfortunately we have not found an elegant way to leverage this idea into a global
description of the cost landscape. Proposition 6.8 merely bounds K(Q, P0 , P1 ) by the
expected diameter of the distribution Q. We can nevertheless use this bound to describe
some level sets of W1 (Q, Pθ )
Theorem 6.9. Let X be a strictly intrinsic Polish space equipped with a geodesically convex distance d and let PX1 be equipped with the 1-Wasserstein distance W1 . Let F ⊂ PX1
be displacement convex and let Q ∈ PX1 have expected diameter
D = 2 min Eu∼Q [d(u, u0 )] .
u0 ∈X

Then the level set L(Q, F, M ) = {Pθ ∈ F : W1 (Q, Pθ ) ≤ M } is connected if
M > inf W1 (Q, Pθ ) + 2D .
Pθ ∈F

Proof Choose P1 ∈ F such that W1 (Q, P1 ) < M − 2D. For any P0 , P00 ∈ L(Q, F, M ), let
t ∈ [0, 1] 7→ Pt ∈ F be a displacement geodesic joining P0 and P1 without leaving F. Thanks to
Proposition 6.8,
W1 (Q, Pt ) ≤ (1−t) M + t (M − 2D) + 2t(1 − t)D = M − 2t2 D ≤ M .
Therefore this displacement geodesic is contained in L(Q, F, M ) and joins P0 to P1 . We can similarly construct a second displacement geodesic that joins P00 to P1 without leaving L(Q, F, M ).
Therefore there is a continuous path connecting P0 to P00 without leaving L(Q, F, M ).

This result means that optimizing the Wasserstein distance with a descent algorithm
will not stop before finding a generative model P ∈ F whose distance W1 (Q, P ) to the
target distribution is within 2D of the global minimum. Beyond that point, the algorithm
could meet local minima and stop progressing. Because we use a rather coarse bound on
the constant K(Q, P0 , P1 ), we believe that it is possible to give much better suboptimality
guarantee in particular cases.
Note that this result does not depend on the parametrization of Gθ and therefore applies
to the level sets of potentially very nonconvex neural network parametrizations. Previous
results on the connexity of such level sets [6, 19] are very tied to a specific parametric form.
The fact that we can give such a result in an abstract setup is rather surprising. We hope
that further developments will clarify how much our approach can help these efforts.
Finally, comparing this result with Example 3.5 also reveals a fascinating possibility: a
simple descent algorithm might in fact be unable to find that the Dirac distribution at the
center of the sphere is a global minimum. Therefore the effective statistical performance
of the learning process may be subtantially better than what Theorem 3.4 suggests. Further
research is necessary to check whether such a phenomenon occurs in practice.
34

7

Conclusion

This work illustrates how the geometrical study of probability distances provides useful
—but still incomplete— insights on the practical performance of implicit modeling approaches using different distances. In addition, using a technique that differs substantially
from previous works, we also obtain surprising global optimization results that remain valid
when the parametrization is nonconvex.

Acknowledgments
We would like to thank Joan Bruna, Marco Cuturi, Arthur Gretton, Yann Ollivier, and
Arthur Szlam for stimulating discussions and also for pointing out numerous related works.

References
[1] M. A. Aizerman, É. M. Braverman, and L. I. Rozonoér. Theoretical foundations of
the potential function method in pattern recognition learning. Automation and Remote
Control, 25:821–837, 1964.
[2] Shun-ichi Amari and Hiroshi Nagaoka. Methods of information geometry, volume
191. American Mathematical Society, 2007.
[3] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In Proceedings of the 34nd International Conference on Machine
Learning, ICML 2017, Sydney, Australia, 7-9 August, 2017, 2017.
[4] N. Aronszajn. Theory of reproducing kernels. Transactions of the American Mathematical Society, 68:337–404, 1950.
[5] Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (gans). arXiv preprint
arXiv:1703.00573, 2017.
[6] Antonio Auffinger and Gérard Ben Arous. Complexity of random smooth functions
of many variables. Annals of Probability, 41(6):4214–4247, 2013.
[7] Marc G Bellemare, Ivo Danihelka, Will Dabney, Shakir Mohamed, Balaji Lakshminarayanan, Stephan Hoyer, and Rémi Munos. The Cramer distance as a solution to
biased Wasserstein gradients. arXiv preprint arXiv:1705.10743, 2017.
[8] Patrizia Berti, Luca Pratelli, Pietro Rigo, et al. Gluing lemmas and skorohod representations. Electronic Communications in Probability, 20, 2015.
[9] Vivek S Borkar. Stochastic approximation with two time scales. Systems & Control
Letters, 29(5):291–294, 1997.

35

[10] Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for largescale machine learning. CoRR, abs/1606.04838, 2016.
[11] Diane Bouchacourt, Pawan K Mudigonda, and Sebastian Nowozin. DISCO nets:
DISsimilarity COefficients Networks. In Advances in Neural Information Processing
Systems 29, pages 352–360, 2016.
[12] Dmitri Burago, Yuri Burago, and Sergei Ivanov. A Course in Metric Geometry. volume 33 of AMS Graduate Studies in Mathematics. American Mathematical Society,
2001.
[13] Edward Challis and David Barber. Affine independent variational inference. In
F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in
Neural Information Processing Systems 25, pages 2186–2194. Curran Associates,
Inc., 2012.
[14] Harald Cramér. Mathematical Methods of Statistics. Princeton University Press,
1946.
[15] Emily Denton, Soumith Chintala, Arthur Szlam, and Rob Fergus. Deep generative
image models using a laplacian pyramid of adversarial networks. In C. Cortes, N. D.
Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural
Information Processing Systems 28, pages 1486–1494. Curran Associates, Inc., 2015.
[16] Steffen Dereich, Michael Scheutzow, and Reik Schottstedt. Constructive quantization: approximation by empirical measures. Annales de l’I.H.P. Probabilités et statistiques, 49(4):1183–1203, 2013.
[17] Gintare Karolina Dziugaite, Daniel M. Roy, and Zoubin Ghahramani. Training generative neural networks via maximum mean discrepancy optimization. In Proceedings
of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI 2015,
pages 258–267, 2015.
[18] Nicolas Fournier and Arnaud Guillin. On the rate of convergence in Wasserstein distance of the empirical measure. Probability Theory and Related Fields, 162(3):707–
738, Aug 2015.
[19] C Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network
optimization. arXiv preprint arXiv:1611.01540, 2016.
[20] Ian J. 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 27, pages 2672–2680. Curran
Associates, Inc., 2014.
[21] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and
Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research,
13:723–773, 2012.

36

[22] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and
Aaron Courville. Improved training of Wasserstein GANs. arXiv preprint
arXiv:1704.00028, 2017.
[23] J. M. Hammersley. The distribution of distance in a hypersphere. The Annals of
Mathematical Statistics, 21(3):447–452, 1950.
[24] T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, Second Edition. Springer Series in Statistics. Springer Verlag, New York, 2009.
[25] Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of
gans for improved quality, stability, and variation. arXiv preprint arXiv:1710.10196,
2017.
[26] Aleksandr Y. Khinchin. Sur la loi des grandes nombres.
l’Académie des Sciences, 1929.

Comptes Rendus de

[27] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. CoRR,
abs/1312.6114, 2013.
[28] Murat Kocaoglu, Christopher Snyder, Alexandros G. Dimakis, and Sriram Vishwanath. Causalgan: Learning causal implicit generative models with adversarial
training. arXiv preprint arXiv:1709.02023, 2017.
[29] Vijay R Konda and John N Tsitsiklis. Convergence rate of linear two-time-scale
stochastic approximation. Annals of applied probability, pages 796–819, 2004.
[30] Tejas D Kulkarni, Pushmeet Kohli, Joshua B Tenenbaum, and Vikash Mansinghka.
Picture: A probabilistic programming language for scene perception. In Proceedings
of the IEEE conference on Computer Vision And Pattern Recognition, CVPR 2015,
pages 4390–4399, 2015.
[31] Mun Wai Lee and Ramakant Nevatia. Dynamic human pose estimation using Markov
Chain Monte Carlo approach. In 7th IEEE Workshop on Applications of Computer
Vision / IEEE Workshop on Motion and Video Computing (WACV/MOTION 2005),
pages 168–175, 2005.
[32] Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos. Mmd gan: Towards deeper understanding of moment matching network. arXiv
preprint arXiv:1705.08584, 2017.
[33] Yujia Li, Kevin Swersky, and Richard Zemel. Generative moment matching networks.
In Proceedings of the 32Nd International Conference on International Conference on
Machine Learning - Volume 37, ICML’15, pages 1718–1727, 2015.
[34] Shuang Liu, Olivier Bousquet, and Kamalika Chaudhuri. Approximation and convergence properties of generative adversarial learning. arXiv preprint arXiv:1705.08991,
2017. to appear in NIPS 2017.

37

[35] Paul Milgrom and Ilya Segal. Envelope theorems for arbitrary choice sets. Econometrica, 70(2):583–601, 2002.
[36] Alfred Müller. Integral probability metrics and their generating classes of functions.
Advances in Applied Probability, 29(2):429–443, 1997.
[37] Radford M. Neal. Annealed importance sampling.
11(2):125–139, Apr 2001.

Statistics and Computing,

[38] XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory, 56(11):5847–5861, 2010.
[39] Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-GAN: Training generative
neural samplers using variational divergence minimization. In Advances in Neural
Information Processing Systems 29, pages 271–279. 2016.
[40] Svetlozar T Rachev, Lev Klebanov, Stoyan V Stoyanov, and Frank Fabozzi. The
methods of distances in the theory of probability and statistics. Springer, 2013.
[41] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation
learning with deep convolutional generative adversarial networks. arXiv preprint
arXiv:1511.06434, 2015.
[42] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In Proceedings of the
31th International Conference on Machine Learning, ICML 2014, pages 1278–1286,
2014.
[43] Lukasz Romaszko, Christopher KI Williams, Pol Moreno, and Pushmeet Kohli.
Vision-as-inverse-graphics: Obtaining a rich 3d explanation of a scene from a single image. In Proceedings of the IEEE Conference on Computer Vision and Pattern
Recognition, CVPR 2017, pages 851–859, 2017.
[44] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and
Xi Chen. Improved techniques for training GANs. In Advances in Neural Information
Processing Systems 29, pages 2234–2242, 2016.
[45] Isaac J. Schoenberg. Metric spaces and positive definite functions. Transactions of
the American Mathematical Society, 44:522–536, 1938.
[46] Bernhard Schölkopf and Alexander J. Smola. Learning with Kernels. MIT Press,
Cambridge, MA, 2002.
[47] Dino Sejdinovic, Bharath Sriperumbudur, Arthur Gretton, and Kenji Fukumizu.
Equivalence of distance-based and rkhs-based statistics in hypothesis testing. The
Annals of Statistics, 41(5):2263–2291, 2013.
[48] Robert J. Serfling. Approximation theorems of mathematical statistics. John Wiley &
Sons, New York; Chichester, 1980.
38

[49] Bharath Sriperumbudur. On the optimal estimation of probability measures in weak
and strong topologies. Bernoulli, 22(3):1839–1893, 08 2016.
[50] Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf,
Gert RG Lanckriet, et al. On the empirical estimation of integral probability metrics.
Electronic Journal of Statistics, 6:1550–1599, 2012.
[51] Bharath K Sriperumbudur, Kenji Fukumizu, and Gert RG Lanckriet. Universality,
characteristic kernels and rkhs embedding of measures. Journal of Machine Learning
Research, 12(Jul):2389–2410, 2011.
[52] Gábor J Székely and Maria L Rizzo. Energy statistics: A class of statistics based on
distances. Journal of statistical planning and inference, 143(8):1249–1272, 2013.
[53] J. Gábor Székely. E-statistics: The energy of statistical samples. Technical Report
02-16, Bowling Green State University, Department of Mathematics and Statistics,
2002.
[54] Lucas Theis, Aaron van den Oord, and Matthias Bethge. A note on the evaluation of
generative models. In International Conference on Learning Representations, 2016.
[55] Cédric Villani. Optimal Transport: Old and New. Grundlehren der mathematischen
Wissenschaften. Springer, Berlin, 2009.
[56] Richard von Mises. On the asymptotic distribution of differentiable statistical functions. The Annals of Mathematical Statistics, 18(3):309–348, 1947.
[57] A. A. Zinger, Ashot V. Kakosyan, and Lev B. Klebanov. A characterization of distributions by mean values of statistics and certain probabilistic metrics. Journal of
Soviet Mathematics, 4(59):914–920, 1992. Translated from Problemy Ustoichivosti
Stokhasticheskikh Modelei-Trudi seminara, 1989, pp 47-55.

39

