On the empirical estimation of integral probability metrics

Given two probability measures, P and Q defined on a measurable space, S, the integral probability metric (IPM) is defined as γF(P,Q)=\ ∫Sf\,dP-∫Sf\,dQ\,:\,f\, where F is a class of real-valued bounded measurable functions on S. By appropriately choosing F, various popular distances between P and Q, including the Kantorovich metric, Fortet-Mourier metric, dual-bounded Lipschitz distance (also called the Dudley metric), total variation distance, and kernel distance, can be obtained. In this paper, we consider the problem of estimating γF from finite random samples drawn i.i.d. from P and Q. Although the above mentioned distances cannot be computed in closed form for every P and Q, we show their empirical estimators to be easily computable, and strongly consistent (except for the total-variation distance). We further analyze their rates of convergence. Based on these results, we discuss the advantages of certain choices of F (and therefore the corresponding IPMs) over others—in particular, the kernel distance is shown to have three favorable properties compared with the other mentioned distances: it is computationally cheaper, the empirical estimate converges at a faster rate to the population value, and the rate of convergence is independent of the dimension d of the space (for S=Rᵈ). We also provide a novel interpretation of IPMs and their empirical estimators by relating them to the problem of binary classification: while the IPM between class-conditional distributions is the negative of the optimal risk associated with a binary classifier, the smoothness of an appropriate binary classifier (e.g., support vector machine, Lipschitz classifier, etc.) is inversely related to the empirical estimator of the IPM between these class-conditional distributions.