  The Wasserstein distance between two probability measures on a metric space
is a measure of closeness with applications in statistics, probability, and
machine learning. In this work, we consider the fundamental question of how
quickly the empirical measure obtained from $n$ independent samples from $\mu$
approaches $\mu$ in the Wasserstein distance of any order. We prove sharp
asymptotic and finite-sample results for this rate of convergence for general
measures on general compact metric spaces. Our finite-sample results show the
existence of multi-scale behavior, where measures can exhibit radically
different rates of convergence as $n$ grows.
