Timezone: »

 
Spotlight
Quantifying the Empirical Wasserstein Distance to a Set of Measures: Beating the Curse of Dimensionality
Nian Si · Jose Blanchet · Soumyadip Ghosh · Mark Squillante

Tue Dec 08 08:20 PM -- 08:30 PM (PST) @ Orals & Spotlights: Deep Learning/Theory
in Orals & Spotlights Track 13: Deep Learning/Theory »

We consider the problem of estimating the Wasserstein distance between the empirical measure and a set of probability measures whose expectations over a class of functions (hypothesis class) are constrained. If this class is sufficiently rich to characterize a particular distribution (e.g., all Lipschitz functions), then our formulation recovers the Wasserstein distance to such a distribution. We establish a strong duality result that generalizes the celebrated Kantorovich-Rubinstein duality. We also show that our formulation can be used to beat the curse of dimensionality, which is well known to affect the rates of statistical convergence of the empirical Wasserstein distance. In particular, examples of infinite-dimensional hypothesis classes are presented, informed by a complex correlation structure, for which it is shown that the empirical Wasserstein distance to such classes converges to zero at the standard parametric rate. Our formulation provides insights that help clarify why, despite the curse of dimensionality, the Wasserstein distance enjoys favorable empirical performance across a wide range of statistical applications.

Keywords: Bandit Algorithms · Variational Inference · Algorithms · Probabilistic Methods -> MCMC; Probabilistic Methods

Author Information

Nian Si (Stanford University)
Jose Blanchet (Stanford University)
Soumyadip Ghosh (IBM Research)
Mark Squillante (IBM Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors