\section{Introduction}

In machine learning, the Kullback-Leibler (KL) divergence is perhaps the most common way of assessing how well a probabilistic model explains observed data. Among the reasons for its popularity is that it is directly related to maximum likelihood estimation and is easily optimized. However, the KL divergence suffers from a significant limitation: it does not take into account how close two outcomes might be, but only their relative probability. This closeness can matter a great deal: in image modelling, for example, perceptual similarity is key \citep{rubner2000earth,gao2016distributionally}. Put another way, the KL divergence cannot reward a model that ``gets it almost right''.

To address this limitation, researchers have turned to the Wasserstein metric, which does incorporate the underlying geometry between outcomes. The Wasserstein metric can be applied to distributions with non-overlapping supports, and has good out-of-sample performance \citep{esfahani2015data}. Yet, practical applications of the Wasserstein distance, especially in deep learning, remain tentative. In this paper we provide a clue as to why that might be: estimating the Wasserstein metric from samples yields biased gradients, and may actually lead to the wrong minimum. This precludes using stochastic gradient descent (SGD) and SGD-like methods, whose fundamental mode of operation is sample-based, when optimizing for this metric.



As a replacement we propose the Cram\'er distance \citep{szekely02estatistics, rizzo2016energy}, also known as the continuous ranked probability score in the probabilistic forecasting literature \citep{gneiting07strictly}. The Cram\'er distance, like the Wasserstein metric, respects the underlying geometry but also has unbiased sample gradients. To underscore our theoretical findings, we demonstrate a significant quantitative difference between the two metrics when employed in typical machine learning scenarios: categorical distribution estimation, regression, and finally image generation.

\section{Probability Divergences and Metrics}

In this section we provide the notation to mathematically distinguish the Wasserstein metric (and later, the Cram\'er distance) from the Kullback-Leibler divergence and probability distances such as the total variation. 
The experimentally-minded reader may choose to skip to Section \ref{sec:impact_wasserstein_bias}, where we show that minimizing the sample Wasserstein loss leads to significant degradation in performance.

Let $P$ be a probability distribution over $\mathbb{R}$. When $P$ is continuous, we will assume it has density $\mu_P$. The expectation of a function $f : \mathbb{R} \to \mathbb{R}$ with respect to $P$ is
\begin{equation*}
\expect_{x \sim P} f(x) := \int_{-\infty}^\infty f(x) P(\textrm{d} x) = \left \{
\begin{array}{ll}
\int f(x) \mu_P(x) \textrm{d} x & \text{if $P$ is continuous, and} \vspace{0.5em}\\
\sum f(x) P(x) & \text{if $P$ is discrete}.
\end{array} \right .
\end{equation*}
We will suppose all expectations and integrals under consideration are finite. We will often associate $P$ to a random variable $X$, such that for a subset of the reals $A \subseteq \mathbb{R}$, we have $\Pr \{ X \in A \} = P(A)$. The (cumulative) distribution function of $P$ is then
\begin{equation*}
F_P(x) := \Pr \{ X \le x \} = \int_{-\infty}^x P(dx) .
\end{equation*}
Finally, the inverse distribution function of $P$, defined over the interval $(0, 1]$, is
\begin{equation*}
F^{-1}_P(u) := \inf \{ x : F_P(x) = u \}.
\end{equation*}
\subsection{Divergences and Metrics}

Consider two probability distributions $P$ and $Q$ over $\mathbb{R}$. A \emph{divergence} $\mathbf{d}$ is a mapping $(P, Q) \mapsto \mathbb{R}^+$ with $\mathbf{d}(P, Q) = 0$ if and only if $P = Q$ almost everywhere. A popular choice is the Kullback-Leibler (KL) divergence
\begin{equation*}
\textrm{KL}(P \, \| \, Q) := \int_{-\infty}^\infty \log \frac{P(\textrm{d} x)}{Q(\textrm{d} x)} P(\textrm{d} x),
\end{equation*}
with $\textrm{KL}(P \, \| \, Q) = \infty$ if $P$ is not absolutely continuous w.r.t. $Q$. The KL divergence, also called relative entropy, measures the amount of information needed to encode the  change in probability from $Q$ to $P$ \citep{cover91elements}.

A \emph{probability metric} is a divergence which is also symmetric ($\mathbf{d}(P, Q) = \mathbf{d}(Q, P)$) and respects the triangle inequality: for any distribution $R$, $\mathbf{d}(P, Q) \le \mathbf{d}(P, R) + \mathbf{d}(R, Q)$. We will use the term \emph{probability distance} to mean a symmetric divergence satisfying the relaxed triangle inequality $\mathbf{d}(P, Q) \le c \left [ \mathbf{d}(P, R) + \mathbf{d}(R, Q) \right ]$ for some $c \ge 1$.

We will first study the $p$-Wasserstein metrics $w_p$ \citep{dudley2002real}.
For $1 \le p < \infty$, a practical definition is through the inverse distribution functions of $P$ and $Q$:
\begin{equation}
w_p(P, Q) := \left ( \int_0^1 \big |F^{-1}_P(u) - F^{-1}_Q(u)\big |^p \textrm{d} u \right )^{1/p}.\label{eqn:primal_wasserstein}
\end{equation}
We will sometimes find it convenient to deal with the $p^\mathit{th}$ power of the metric, which we will denote by $w_p^p$; note that $w_p^p$ is not a metric proper, but is a probability distance.

We will be chiefly concerned with the 1-Wasserstein metric, which is most commonly used in practice. 
The 1-Wasserstein metric has a dual form which is theoretically convenient and which we mention here for completeness. %
Define $\mathbb{F}_\infty$ to be the class of $1$-Lipschitz functions. Then
\begin{equation}\label{eqn:ipm_wasserstein}
w_1(P, Q) := \sup_{f \in \mathbb{F}_\infty} \big | \expect_{x \sim P} f(x) - \expect_{x \sim Q} f(x) \big |.
\end{equation}
This is a special case of the celebrated Monge-Kantorovich duality \citep{rachev13methods}, and is the integral probability metric (IPM) with function class $\mathbb{F}_\infty$ \citep{muller97integral}. We invite the curious reader to consult these two sources as a starting point on this rich topic.

\subsection{Properties of a Divergence}

As noted in the introduction, the fundamental difference between the KL divergence and the Wasserstein metric is that the latter is sensitive not only to change in probability but also to the geometry of possible outcomes. %
To capture this notion we now introduce the concept of an \emph{ideal divergence}.

Consider a divergence $\mathbf{d}$, and for two random variables $X, Y$ with distributions $P, Q$  write $\mathbf{d}(X, Y) := \mathbf{d}(P, Q)$. We say that $\mathbf{d}$ is \emph{scale sensitive} (of order $\beta$), i.e. it has property \textbf{(S)}, if there exists a $\beta > 0$ such that for all $X$, $Y$, and a real value $c > 0$,
\begin{equation}
\mathbf{d}(cX, cY) \le |c|^\beta \mathbf{d}(X, Y). \tag{\textbf{S}}
\end{equation}
A divergence $\mathbf{d}$ has property \textbf{(I)}, i.e. it is \emph{sum invariant}, if whenever $A$ is independent from $X$, $Y$
\begin{equation}
\mathbf{d}(A + X, A + Y) \le \mathbf{d}(X, Y). \tag{\textbf{I}}
\end{equation}
Following \citet{zolotarev76metric}, an ideal divergence $\mathbf{d}$ is one that possesses both (S) and (I).\footnote{Properties (S) and (I) are called \emph{regularity} and \emph{homogeneity} by \citeauthor{zolotarev76metric}; we believe our choice of terms is more machine learning-friendly.}

We can illustrate the sensitivity of ideal divergences to the value of outcomes by considering Dirac functions $\delta_x$ at different values of $x$. If $\mathbf{d}$ is scale sensitive of order $\beta = 1$ then the divergence $\mathbf{d}(\delta_0, \delta_{1/2})$ can be no more than half the divergence $\mathbf{d}(\delta_0, \delta_1)$. If $\mathbf{d}$ is \emph{sum invariant}, then the divergence of $\delta_0$ to $\delta_{1}$ is equal to the divergence of the same distributions shifted by a constant $c$, i.e. of $\delta_{c}$ to $\delta_{1 + c}$. 
As a concrete example of the importance of these properties, \citet{bellemare17distributional} recently demonstrated the importance of ideal metrics in reinforcement learning, specifically their role in providing the contraction property for a distributional form of the Bellman update.

In machine learning we often view the divergence $\mathbf{d}$ as a loss function. Specifically, let $Q_\theta$ be some distribution parametrized by $\theta$, and consider the loss $\theta \mapsto \mathbf{d}(P, Q_\theta)$. We are interested in minimizing this loss, that is finding $\theta^* := \argmin_\theta \mathbf{d}(P, Q_\theta)$. We now describe a third property based on this loss, which we call \emph{unbiased sample gradients}.

Let $\mathbf{X}_m := X_1, X_2, \dots, X_m$ be independent samples from $P$ and define the empirical distribution $\hat P_m := \hat P_m(\mathbf{X}_m) := \tfrac{1}{m} \sum_{i=1}^m \delta_{X_i}$ (note that $\hat P_m$ is a random quantity). From this, define the \emph{sample loss} $\theta \mapsto \mathbf{d}(\hat P_m, Q_\theta)$. We say that $\mathbf{d}$ has unbiased sample gradients when the expected gradient of the sample loss equals the gradient of the true loss for all $P$ and $m$:
\begin{equation}
\expect_{\mathbf{X}_m \sim P} {\nabla_\theta} \mathbf{d}(\hat P_m, Q_\theta) = {\nabla_\theta} \mathbf{d}(P, Q_\theta) \tag{\textbf{U}} .
\label{eqn:unbiased_sample_gradients}
\end{equation}

The notion of unbiased sample gradients is ubiquitous in machine learning and in particular in deep learning. Specifically, if a divergence $\mathbf{d}$ does not possess (U) then minimizing it with stochastic gradient descent may not converge, or it may converge to the wrong minimum. Conversely, if $\mathbf{d}$ possesses (U) then we can guarantee that the distribution which minimizes the expected sample loss
is $Q = P$.
In the probabilistic forecasting literature, this makes $\mathbf{d}$ a \emph{proper scoring rule} \citep{gneiting07strictly}.

We now characterize the KL divergence and the Wasserstein metric in terms of these properties. As it turns out, neither simultaneously possesses both (U) and (S).

\begin{prop}\label{prop:kl_prop}
The KL divergence has unbiased sample gradients (U), but is not scale sensitive (S).
\end{prop}
\begin{prop}\label{prop:wasserstein_prop}
The Wasserstein metric is ideal (I, S), but does not have unbiased sample gradients.
\end{prop}
We will provide a proof of the bias in the sample Wasserstein gradients just below; the proof of the rest and later results are provided in the appendix.


\section{Bias in the Sample Gradient Estimates of the Wasserstein Distance}


In this section we give theoretical evidence of serious issues with gradients of the sample Wasserstein loss. We will consider a simple Bernoulli distribution $P$ with parameter $\theta^*\in (0,1)$, which we would like to estimate from samples. Our model is $Q_\theta$, a Bernoulli distribution with parameter $\theta$. We study the behaviour of stochastic gradient descent w.r.t. $\theta$ over the sample Wasserstein loss, specifically using the $p^{th}$ power of the metric (as is commonly done to avoid fractional exponents).
Our results build on the example given by \citet{bellemare17distributional}, whose result is for $\theta^* = \tfrac{1}{2}$ and $m=1$.





Consider the estimate $\nabla_\theta w^p_p(\hat P_m, Q_\theta)$ of the gradient $\nabla_\theta w^p_p(P, Q_\theta)$.
We now show that even in this simplest of settings, this estimate is biased, and we exhibit a lower bound on the bias for any value of $m$.
Hence the Wasserstein metric does not have property (U). 
More worrisome still, we show that the minimum of the expected empirical Wasserstein loss $\theta\mapsto \expect\nolimits_{\mathbf{X}_m} \big[ w^p_p(\hat P_m, Q_\theta)\big]$ is not the minimum of the Wasserstein loss $\theta\mapsto w^p_p(P, Q_\theta)$.
We then conclude that minimizing the sample Wasserstein loss by stochastic gradient descent may in general fail to converge to the minimum of the true loss.

\begin{thm}\label{thm:wasserstein_bias}
Let $\hat P_m=\frac 1m\sum_{i=1}^m \delta_{X_i}$ be the empirical distribution derived from $m$ independent samples $\mathbf{X}_m = X_1,\dots, X_m$ drawn from a Bernoulli distribution $P$. Then for all $1 \le p < \infty$,
\begin{itemize}[leftmargin=4ex,topsep=0pt,itemsep=-1ex,partopsep=1ex,parsep=1ex]
\item {\bf Non-vanishing minimax bias} of the sample gradient. For any $m \ge 1$ there exists a pair of Bernoulli distributions $P$, $Q_\theta$ for which
\begin{equation*}
\Big| \expect_{\mathbf{X}_m \sim P} \big[ {\nabla_\theta} w^p_p(\hat P_m, Q_\theta)\big] - {\nabla_\theta} w^p_p(P, Q_\theta) \Big| \ge 2e^{-2};
\end{equation*}

\item {\bf Wrong minimum} of the sample Wasserstein loss. The minimum of the expected sample loss $\tilde\theta = \argmin_\theta \expect\nolimits_{\mathbf{X}_m} \big[ w^p_p(\hat P_m, Q_\theta)\big]$ is in general different from the minimum of the true Wasserstein loss $\theta^*=\argmin_\theta w^p_p(P, Q_\theta)$.

\item {\bf Deterministic solutions} to stochastic problems. For any $m \ge 1$, there exists a distribution $P$ with nonzero entropy whose sample loss is minimized by a 
distribution $Q_{\tilde \theta}$ with zero entropy.
\end{itemize}
\end{thm}
Taken as a whole, Theorem \ref{thm:wasserstein_bias} states that we cannot in general minimize the Wasserstein loss using naive stochastic gradient descent methods. Although our result does not imply the lack of a stochastic optimization procedure for this loss,\footnote{For example, if $P$ has finite support keeping track of the empirical distribution suffices.} we believe our result to be serious cause for concern.
We leave as an open question whether an unbiased optimization procedure exists and is practical.

\subsection*{Wasserstein Bias in the Literature}

Our result is surprising given the prevalence of the Wasserstein metric in empirical studies. We hypothesize that this bias exists in published results and is an underlying cause of learning instability and poor convergence often remedied to by heuristic means. For example,  \citet{frogner15learning} and \citet{montavon2016wasserstein} reported the need for a mixed KL-Wasserstein loss to obtain good empirical results, with the latter explicitly discussing the issue of wrong minima when using Wasserstein gradients.

We remark that our result also applies to the dual \eqnref{ipm_wasserstein}, since the losses are the same. This dual was recently considered by \citet{arjovsky17wasserstein} as an alternative loss to the primal \eqnref{primal_wasserstein}.
The adversarial procedure proposed by the authors is a two time-scale process which first maximizes \eqnref{ipm_wasserstein} w.r.t $f \in \mathbb{F}_\infty$ using $m$ samples, then takes a single stochastic gradient step w.r.t. $\theta$. Interestingly, this approach does seem to provide unbiased gradients as $m \to \infty$. However, the cost of a single gradient is now significantly higher, and for a fixed $m$ we conjecture that the minimax bias remains.

\section{The Cram\'er Distance}\label{sec:cramer_distance}

We are now ready to describe an alternative to the Wasserstein metric, the Cram{\'e}r distance \citep{szekely02estatistics, rizzo2016energy}. As we shall see, the Cram{\'e}r distance has the same appealing properties as the Wasserstein metric, but also provides us with unbiased sample gradients. As a result, we believe this underappreciated distance is strictly superior to the Wasserstein metric for machine learning applications.

\subsection{Definition and Analysis}

Recall that for two distributions $P$ and $Q$ over $\mathbb{R}$, their (cumulative) distribution functions are respectively $F_P$ and $F_Q$. The Cram{\'e}r distance between $P$ and $Q$ is %
\begin{equation*}
l^2_2(P, Q) := \int_{-\infty}^\infty (F_P(x) - F_Q(x))^2 \textrm{d} x .
\end{equation*}
Note that as written, the Cram\'er distance is not a metric proper. However, its square root is, and is a member of the $l_p$ family of metrics
\begin{equation*}
  l_p(P, Q) := \left ( \int_{-\infty}^\infty |F_P(x) - F_Q(x)|^p \textrm{d} x \right )^{1/p} .
\end{equation*}
The $l_p$ and Wasserstein metrics are identical at $p=1$, but are otherwise distinct. Like the Wasserstein metrics, the $l_p$ metrics have dual forms as integral probability metrics \citep[see][for a proof]{dedecker07empirical}:
\begin{equation}
l_p(P, Q) = \sup_{f \in \mathbb{F}_q} \big | \expect_{x \sim P} f(x) - \expect_{x \sim Q} f(x) \big |, \label{eqn:cramer_ipm}
\end{equation}
where $\mathbb{F}_q := \{ f : f \text{ is absolutely continuous}, \big \| \frac{\text{d} f}{\text{d}x} \big \|_q \le 1 \}$ and $q$ is the conjugate exponent of $p$, i.e. $p^{-1} + q^{-1} = 1$.\footnote{This relationship is the reason for the notation $\mathbb{F}_\infty$ in the definition the dual of the 1-Wasserstein \eqnref{ipm_wasserstein}.}
It is this dual form that we use to prove that the Cram\'er distance has property (S).
\begin{thm}\label{thm:cramer_properties}
Consider two random variables $X$, $Y$, a random variable $A$ independent of $X, Y$, and a real value $c > 0$. Then for $1 \le p \le \infty$,
\begin{equation*}
\textbf{(I) } \, l_p(A + X, A + Y) \le l_p(X, Y) \qquad \textbf{(S) } \, l_p(cX, cY) \le |c|^{1/p} l_p(X, Y) .
\end{equation*}
Furthermore, the Cram\'er distance has unbiased sample gradients. That is, given $\mathbf{X}_m := X_1, \dots, X_m$ drawn from a distribution $P$, the empirical distribution $\hat P_m := \tfrac{1}{m} \sum_{i=1}^m \delta_{X_i}$, and a distribution $Q_\theta$,
\begin{equation*}
\expect_{\mathbf{X}_m \sim P} {\nabla_\theta} l^2_2 (\hat P_m, Q_\theta) = {\nabla_\theta} l^2_2(P, Q_\theta),
\end{equation*}
and of all the $l_p^p$ distances, only the Cram\'er ($p = 2$) has this property.
\end{thm}
We conclude that the Cram\'er distance enjoys both the benefits of the Wasserstein metric and the SGD-friendliness of the KL divergence. Given the close similarity of the Wasserstein and $l_p$ metrics, it is truly remarkable that only the Cram\'er distance has unbiased sample gradients.

The \emph{energy distance} \citep{szekely02estatistics} is a natural extension of the Cram{\'e}r distance to the multivariate case. Let $P, Q$ be probability distributions over $\mathbb{R}^d$ and let $X, X'$ and $Y, Y'$ be independent random variables distributed according to $P$ and $Q$, respectively. The energy distance \citep[sometimes called the squared energy distance, see e.g.][]{rizzo2016energy} is
\begin{equation}
\mathcal{E}(P, Q) := \mathcal{E}(X, Y) := 2 \expect \norm{X - Y}_2 - \expect \norm{X - X'}_2 - \expect \norm{Y - Y'}_2. 
\label{eqn:energy_distance}
\end{equation}
\citeauthor{szekely02estatistics} showed that, in the univariate case, $l_2^2(P, Q) = \tfrac{1}{2} \mathcal{E}(P, Q)$. Interestingly enough, the energy distance can also be written in terms of a difference of expectations. For
\begin{equation*}
f^*(x) := \expect \norm{x - Y'}_2 - \expect \norm{x - X'}_2,
\end{equation*}
we find that
\begin{equation}
\mathcal{E}(X, Y) = \expect f^*(X) - \expect f^*(Y).\label{eqn:energy_distance_dual}
\end{equation}
Note that this $f^*$ is \emph{not} the maximizer of the dual \eqnref{cramer_ipm}, since $\frac{1}{2} \mathcal{E}$ is equal to the \emph{squared} $l_2$ metric (i.e. the Cram\'er distance).\footnote{The maximizer of \eqnref{cramer_ipm} is: $g^*(x) = \frac{f^*(x)}{\sqrt{2 (\expect f^*(X) - \expect f^*(Y))}}$ \citep[based on results by][]{gretton2012kernel}. }
Finally, we remark that $\mathcal{E}$ also possesses properties (I), (S), and (U) (proof in the appendix).

\subsection{Comparison to the 1-Wasserstein Metric}\label{sec:impact_wasserstein_bias}

To illustrate how the Cram\'er distance compares to the 1-Wasserstein metric, we consider modelling the discrete distribution $P$ depicted in Figure \ref{fig:dist_comparison_toy_example} (left). Since the trade-offs between metrics are only apparent when using an approximate model, we use an underparametrized discrete distribution $Q_\theta$ which assigns the same probability to $x = 1$ and $x = 10$. That is,
\begin{equation*}
Q_\theta(0) := Q_\theta\{x = 0\} = \frac{1}{1 + 2 e^\theta} \qquad Q_\theta(1) = Q_\theta(10) = \frac{e^{\theta}}{1 + 2 e^{\theta}} .
\end{equation*}
Figure \ref{fig:dist_comparison_toy_example} depicts the distributions minimizing the various divergences under this parametrization. In particular, the Cram\'er solution is relatively close to the 1-Wasserstein solution. Furthermore, the minimizer of the sample Wasserstein loss ($m = 1$) clearly provides a bad solution (most of the mass is on 0). Note that, as implied by Theorem \ref{thm:wasserstein_bias}, the bias shown here would arise even if the distribution could be exactly represented.

\begin{figure*}
\begin{center}
\includegraphics[width=\textwidth]{figures/various-losses-toy.pdf}
\end{center}
\caption{\textbf{Leftmost.} Target distribution. One outcome ($10$) is significantly more distant than the two others ($0$, $1$). \textbf{Rest.}  Distributions minimizing the divergences discussed in this paper, under the constraint $Q(1) = Q(10)$. Both Wasserstein metric and Cram\'er distance underemphasize $Q(0)$ to better match the cumulative distribution function. The sample Wasserstein loss result is for $m=1$. \label{fig:dist_comparison_toy_example}}
\end{figure*}

To further show the impact of the Wasserstein bias we used gradient descent to minimize either the true or sample losses with a fixed step-size ($\alpha = 0.001$). In the stochastic setting, at each step we construct the empirical distribution $\hat P_m$ from $m$ samples (a Dirac when $m=1$), and take a gradient step. As we are interested in finding a solution that accounts for the numerical values of outcomes, we measure the performance of each method in terms of the true 1-Wasserstein loss.

Figure \ref{fig:ordinalregression} (left) plots the resulting training curves in the 1-Wasserstein regime, with the KL and Cram\'er solutions indicated for reference (for completeness, full learning curves are provided in the appendix). We first note that, compared to the KL solution, the Cram\'er solution has significantly smaller Wasserstein distance to the target distribution. Second, for small sample sizes stochastic gradient descent fails to find reasonable solutions, and for $m=1$ even converges to a solution worse than the KL minimizer.
This small experiment highlights the cost incurred from minimizing the sample Wasserstein loss, and shows that increasing the sample size may not be sufficient to guarantee good behaviour.


\begin{figure}%
\begin{center}
\includegraphics[width=1\textwidth]{figures/toy_and_ordinal.pdf}
\caption{\textbf{Left.} Wasserstein distance in terms of SGD updates, minimizing the true or sample Wasserstein losses. Also shown are the distances for the KL and Cram\'er solutions. Results are averaged over $10$ random initializations, with error-bands indicating one standard deviation. \textbf{Center.} Ordinal regression on the Year Prediction MSD dataset. Learning curves report RMSE on test set. \textbf{Right.} The same in terms of sample Wasserstein loss.}
\label{fig:ordinalregression}
\end{center}
\end{figure}


\subsection*{Ordinal Regression}

We next trained a neural network in an ordinal regression task using either of the three divergences. The task we consider is the Year Prediction MSD dataset \citep{ucirepository}. In this task, the model must predict the year a song was written (from 1922 to 2011) given a 90-dimensional feature representation. In our setting, this prediction takes the form of a probability distribution. We measure each method's performance on the test set (Figure~\ref{fig:ordinalregression}) in two ways: root mean squared error (RMSE) -- the metric minimized by \citet{PB} -- and the sample Wasserstein loss. Full details on the experiment may be found in the appendix.

The results show that minimizing the sample Wasserstein loss results in significantly worse performance. By contrast, minimizing the Cram\'er distance yields the lowest RMSE and Wasserstein loss, confirming the practical importance of having unbiased sample gradients. 
Naturally, minimizing for one loss trades off performance with respect to the others, and minimizing the Cram\'er distance results in slightly higher negative log likelihood than when minimizing the KL divergence (Figure \ref{fig:ordinalregression_batch_size} in appendix). We conclude that, in the context of ordinal regression where outcome similarity plays an important role, the Cram\'er distance should be preferred over either KL or the Wasserstein metric.

\section{Cram\'er GAN}\label{sec:cramer_gan}

We now consider the Generative Adversarial Networks (GAN) framework \citep{goodfellow14generative}, in particular issues arising in the Wasserstein GAN \citep{arjovsky17wasserstein},
and propose a better GAN based on the Cram\'er distance. A GAN is composed of a generative model (in our experiments, over images), called the \emph{generator}, and a trainable loss function called a discriminator or \emph{critic}.
In theory, the Wasserstein GAN algorithm requires training the critic until convergence, but this is rarely achievable: we would require a critic that is a very powerful network to approximate the Wasserstein distance well. Simultaneously, training this critic to convergence  would overfit the empirical distribution of the training set, which is undesirable.


Our proposed loss function allows for useful learning with imperfect critics by combining the energy distance with a transformation function $h : \mathbb{R}^d \to \mathbb{R}^k$, where $d$ is the input dimensionality and $k = 256$ in our experiments.
The generator then seeks to minimize the energy distance of the transformed variables $\mathcal{E}(h(X), h(Y))$, where $X$ is a real sample and $Y$ is a generated sample. The critic itself seeks to maximize this same distance by changing the parameters of $h$, subject to a soft constraint \citep[the gradient penalty used by][]{gulrajani2017improved}.
The losses used by the Cram\'er GAN algorithm is summarized in Algorithm~1, with additional design choices detailed in the appendix.

\begin{figure*}
\begin{center}
\begin{minipage}{0.47\textwidth}
\includegraphics[width=\linewidth]{figures/cond_celeba64_wgan.png}
\end{minipage}
\hskip 0.5cm
\begin{minipage}{0.47\textwidth}
\includegraphics[width=\linewidth]{figures/cond_celeba64_cramgan.png}
\end{minipage}
\end{center}
  \caption{Generated right halves of the faces for WGAN-GP (left) and Cram\'er GAN (right). The given left halves are from CelebA 64x64 validation set \citep{liu2015faceattributes}.}
\label{fig:cond_celeba64}
\end{figure*}

\begin{figure*}
\begin{minipage}{0.60\textwidth}
\begin{algorithmic}
  {\hrule height.8pt depth0pt \kern2pt}
  \STATE {\bfseries Algorithm 1:} Cram\'er GAN Losses.
  \vspace{0.1cm}
  {\hrule height.8pt depth0pt \kern2pt}
  \STATE {\bfseries Defaults:} The gradient penalty coefficient $\lambda=10$.
   \STATE Sample $x_r \sim P$ a real sample.
   \STATE Sample $x_g, x'_g \sim Q$ two independent generator samples.
   \STATE Sample $\epsilon \sim \mathrm{Uniform}(0, 1)$ a random number.
   \STATE Interpolate real and generated samples:
   \STATE $\hat{x} = \epsilon x_r + (1 - \epsilon) x_g$
   \STATE Define the critic:
   \STATE $f(x) = \norm{h(x) - h(x'_g)}_2 - \norm{h(x)}_2$
   \STATE Compute the generator loss:
   \STATE $L_\mathit{g} = \norm{h(x_r) - h(x_g)}_2 + \| h(x_r) - h(x'_g) \|_2$
   \STATE $\qquad \quad - \| h(x_g) - h(x'_g) \|_2$
   \STATE Compute the surrogate generator loss:
   \STATE $L_\mathit{surrogate} = f(x_r) - f(x_g)$
   \STATE Compute the critic loss:
   \STATE $L_\mathit{critic} = -L_\mathit{surrogate} + \lambda (\|\nabla_{\hat{x}} f(\hat{x})\|_2 - 1)^2$
\end{algorithmic}
\vspace{0.1cm}
{\hrule height.8pt depth0pt \kern2pt}
\end{minipage}
\hskip 0.05cm
\begin{minipage}{0.38\textwidth}
\includegraphics[width=\linewidth]{figures/plot_cond_edgan_celeba64_wdistance.pdf}
\vspace{-0.5cm}
  \caption{Approximate Wasserstein distances between CelebA test set and each generator. $N_u$ indicates the number critic updates per generator update.}
\label{fig:plot_cond_edgan_celeba64_wdistance}
\end{minipage}
\end{figure*}



\subsection{Cram\'er GAN Experiments}
We now show that, compared to the improved Wasserstein GAN (WGAN-GP) of \citet{gulrajani2017improved}, the Cram\'er GAN leads to more stable learning and increased diversity in the generated samples. In both cases we train generative models that predict the right half of an image given the left half; samples from unconditional models are provided in the appendix (Figure~\ref{fig:uncond_celeba64}). The dataset we use here is the CelebA $64\times64$ dataset \citep{liu2015faceattributes} of celebrity faces.

\textbf{Increased diversity.} In our first experiment, we compare the qualitative diversity of completed faces by showing three sample completions generated by either model given the left half of a validation set image (Figure \ref{fig:cond_celeba64}). We observe that the completions produced by WGAN-GP are almost deterministic. Our findings echo those of \citet{isola2016image}, who observed that \emph{``the generator simply learned to ignore the noise.''} By contrast, the completions produced by Cram\'er GAN are fairly diverse, including different hairstyles, accessories, and backgrounds. This lack of diversity in WGAN-GP is particularly concerning given that the main requirement of a generative model is that it should provide a variety of outputs.
  
Theorem \ref{thm:wasserstein_bias} provides a clue as to what may be happening here. We know that minimizing the sample Wasserstein loss will find the wrong minimum. In particular, when the target distribution has low entropy, the sample Wasserstein minimizer may actually be a deterministic distribution. But a good generative model of images \emph{must} lie in this ``almost deterministic'' regime, since the space of natural images makes up but a fraction of all possible pixel combinations and hence there is little per-pixel entropy. We hypothesize that the increased diversity in the Cram\'er GAN comes exactly from learning these almost deterministic predictions.

\textbf{More stable learning.}
In a second experiment, we varied the number of critic updates ($N_u$) per generator update.
To compare performance between the two architectures, we measured the loss computed by an independent WGAN-GP critic trained on the validation set, following a similar evaluation previously done by \citet{ivogan}.
Figure~\ref{fig:plot_cond_edgan_celeba64_wdistance} shows the independent Wasserstein critic distance between each generator and the test set during the course of training. Echoing our results with the toy experiment and ordinal regression, the plot shows that when a single critic update is used, WGAN-GP performs particularly poorly. We note that additional critic updates also improve Cram\'er GAN. This indicates that it is helpful to keep adapting the $h(x)$ transformation.

\section{Conclusion}
\label{sect:conclusion}
There are many situations in which the KL divergence, which is commonly used as a loss function in machine learning, is not suitable. The desirable alternatives, as we have explored, are the divergences that are ideal and allow for unbiased estimators: they allow geometric information to be incorporated into the optimization problem; because they are scale-sensitive and sum-invariant, they possess the convergence properties we require for efficient learning; and the correctness of their sample gradients means we can deploy them in large-scale optimization problems. Among open questions, we mention deriving an unbiased estimator that minimizes the Wasserstein distance, and variance analysis and reduction of the Cram\'er distance gradient estimate.







