  A class of distance measures on probabilities -- the integral probability
metrics (IPMs) -- is addressed: these include the Wasserstein distance, Dudley
metric, and Maximum Mean Discrepancy. IPMs have thus far mostly been used in
more abstract settings, for instance as theoretical tools in mass
transportation problems, and in metrizing the weak topology on the set of all
Borel probability measures defined on a metric space. Practical applications of
IPMs are less common, with some exceptions in the kernel machines literature.
The present work contributes a number of novel properties of IPMs, which should
contribute to making IPMs more widely used in practice, for instance in areas
where $\phi$-divergences are currently popular.
  First, to understand the relation between IPMs and $\phi$-divergences, the
necessary and sufficient conditions under which these classes intersect are
derived: the total variation distance is shown to be the only non-trivial
$\phi$-divergence that is also an IPM. This shows that IPMs are essentially
different from $\phi$-divergences. Second, empirical estimates of several IPMs
from finite i.i.d. samples are obtained, and their consistency and convergence
rates are analyzed. These estimators are shown to be easily computable, with
better rates of convergence than estimators of $\phi$-divergences. Third, a
novel interpretation is provided for IPMs by relating them to binary
classification, where it is shown that the IPM between class-conditional
distributions is the negative of the optimal risk associated with a binary
classifier. In addition, the smoothness of an appropriate binary classifier is
proved to be inversely related to the distance between the class-conditional
distributions, measured in terms of an IPM.
