PaperlayerView exact revision on arXiv

Source-linked AI summary

On integral probability metrics, φ-divergences and binary classification

Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, Gert R. G. Lanckriet

arXiv:0901.2698v4cs.IT

TL;DR

The paper addresses the limited practical use of IPMs and their relationship to φ-divergences. It characterizes their intersection, develops empirical estimators with consistency and convergence analyses, and connects IPMs to binary classification. The main results distinguish IPMs from φ-divergences, establish practical estimability for several IPMs, and relate IPMs to optimal classification risk and classifier smoothness.

  • Problem

    IPMs have mainly been used as theoretical tools, while their relation to φ-divergences and their practical estimation from finite samples require characterization.

  • Method

    The paper derives necessary and sufficient intersection conditions, analyzes empirical IPM estimators from i.i.d. samples, and relates IPMs to binary classification.

  • Results

    Total variation is the only non-trivial φ-divergence that is also an IPM, while Wasserstein, Dudley, and MMD estimators are strongly consistent and easy to compute.

  • Takeaways & Limitations

    IPMs are essentially different from φ-divergences and provide practical distance estimators, while also supplying a classification-based interpretation.

Abstract

from arXiv · show

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 $φ$-divergences are currently popular. First, to understand the relation between IPMs and $φ$-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 $φ$-divergence that is also an IPM. This shows that IPMs are essentially different from $φ$-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 $φ$-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.

I. INTRODUCTION

The paper develops practical properties of integral probability metrics (IPMs), comparing them with φ-divergences and relating them to statistical estimation and binary classification. It shows that IPMs are essentially distinct from φ-divergences while offering simple, consistent estimation for several important metrics.

  • I. INTRODUCTION: IPMs include the Wasserstein distance, Dudley metric, total variation distance, Kolmogorov distance, and maximum mean discrepancy, depending on the function class F.The Dudley metric uses bounded Lipschitz functions, Wasserstein distance uses Lipschitz functions, and MMD uses a reproducing kernel Hilbert space.
  • I. INTRODUCTION: IPMs are proposed as practical alternatives for estimating distances between distributions from finite i.i.d. samples, addressing the difficulty of estimating φ-divergences, especially in high dimensions.The paper emphasizes that IPM estimators are not affected by data dimensionality under the stated conditions, whereas φ-divergence estimation can be difficult to implement or arbitrarily slow.
  • I. INTRODUCTION: The paper asks whether IPMs and φ-divergences share non-trivial distance measures and proves that their classes intersect only at total variation distance.The result establishes that the two families are essentially different, apart from the trivial zero pseudometric case discussed in the theorem.
  • I. INTRODUCTION: Empirical estimators for the Wasserstein distance, Dudley metric, and MMD are obtained, with the first two computed by linear programs and MMD in closed form.The paper analyzes consistency and convergence rates using concentration inequalities and empirical process theory, and reports practical viability in simulations.
  • I. INTRODUCTION: Because empirical total variation is not strongly consistent, the paper gives consistently estimable lower bounds for total variation and, through Pinsker’s inequality, KL-divergence.The lower bounds are expressed using the Wasserstein distance, Dudley metric, and MMD.
  • I. INTRODUCTION: The paper interprets IPMs through binary classification, linking them to optimal classification risk and to the smoothness of Lipschitz and bounded Lipschitz classifiers.It states that the IPM between class-conditional distributions is the negative of the optimal risk associated with an appropriate binary classifier.

3) Interpretability of IPMs:

The paper characterizes when IPMs overlap with φ-divergences and connects IPMs to binary classification. It shows that total variation is the only non-trivial overlap, while the unrestricted IPM is mathematically trivial in practice.

  • Interpretability of IPMs: For disjoint supports, φ-divergences become +∞, whereas IPMs vary with the properties of the underlying space.The paper therefore identifies IPMs as a better notion of distance in that setting.
  • Binary classification: IPMs naturally arise in binary classification as the negative optimal risk for classifiers separating class-conditional distributions.The classifier rule is restricted by the function class F; examples include Dudley, Wasserstein, total variation, and MMD restrictions.
  • IPMs and φ-divergences: The unrestricted function class produces γF⋆(P, Q)=0 when P=Q and +∞ otherwise, making the resulting distance useless in practice.This corresponds to F⋆ containing all real-valued measurable functions.
  • IPMs and φ-divergences: Theorem 2 characterizes equality γF(P,Q)=Dφ(P,Q) through necessary and sufficient conditions on the function class F and convex function φ.The result is established over probability measures absolutely continuous with respect to a σ-finite measure λ.
  • IPMs and φ-divergences: When the φ-divergence parameters satisfy β=α, equality is possible only for constant functions, so every pair of probability measures has distance zero.The corresponding φ-divergence has the form φ(u)=α(u−1) for u≥0.
  • IPMs and φ-divergences: Total variation distance is the only non-trivial IPM that is also a φ-divergence.The theorem’s other case yields a zero pseudometric from constant functions.

III. NON-PARAMETRIC ESTIMATION OF IPMS

The paper develops practical empirical estimators for the Wasserstein distance, Dudley metric, and MMD from finite i.i.d. samples. Wasserstein and Dudley estimators reduce to linear programs, while the MMD estimator has a closed form.

  • Motivation: The estimators target distances that are otherwise difficult to compute exactly, particularly outside settings with closed-form Wasserstein expressions.The paper notes that closed-form Wasserstein computation is not straightforward for all distributions and domains.
  • Estimator construction: Wasserstein and Dudley metrics can be estimated by solving linear programs.The estimators arise from constrained optimization over empirical function values.
  • Estimator construction: The MMD estimator is available in closed form and is the unique solution to the empirical optimization problem.The derivation uses the reproducing property of the RKHS and the Cauchy–Schwarz inequality.
  • Estimator construction: Finite-sample estimation is formulated using empirical distributions Pm and Qn, with function classes for Wasserstein distance, Dudley metric, and MMD.The corresponding classes are FW, Fβ, and Fk.
  • Computational properties: The estimator computations depend on the samples and the metric ρ or kernel k, making their complexity independent of dimension when ρ or k is known.The same dependence allows the estimators to extend to arbitrary domains where ρ or k is defined.

B. Consistency and rate of convergence

The paper establishes consistency and convergence-rate guarantees for empirical IPM estimators. Wasserstein and Dudley rates depend on dimension, whereas bounded-kernel MMD achieves a dimension-independent parametric rate.

  • Consistency: Wasserstein and Dudley estimators are strongly consistent on totally bounded metric spaces.Their estimates converge almost surely to the corresponding population distances as sample sizes grow.
  • General analysis: The general deviation analysis bounds empirical IPM error using Rademacher complexities.The framework applies to any function class with finite envelope and supplies rates for Wasserstein, Dudley, and MMD estimators.
  • Rates and assumptions: MMD estimation has rate OP,Q(m^-1/2 + n^-1/2) under a measurable space and bounded-kernel assumption.The estimator is also strongly consistent by the Borel–Cantelli lemma.
  • Rates and assumptions: Wasserstein and Dudley convergence rates depend on the data dimension d, so higher-dimensional estimation requires more samples for useful estimates.Their rates are independent of the choice of ℓs metric within the stated range.
  • Rates and assumptions: Bounded convex domains yield faster rates for Wasserstein estimation than bounded domains without the convexity assumption.The comparison is stated for bounded subsets of (Rd, ||·||s).
  • Overall findings: Overall, Wasserstein, Dudley, and MMD estimators exhibit good convergence behavior irrespective of the underlying distributions, unlike φ-divergence estimation.The paper presents this as a conclusion of the consistency and rate results.

C. Simulation results

The paper uses simulations to assess the practical performance of empirical estimators for Wasserstein distance, Dudley metric, and MMD. The simulations use examples where the population distances can be computed exactly.

  • Simulation setup: Simulations are used to demonstrate the practical performance of the empirical estimators.The experiments follow the theoretical consistency and convergence-rate analysis.
  • Simulation setup: The simulation examples are chosen so Wasserstein distance, Dudley metric, and MMD can be computed exactly for evaluating estimator performance.This provides reference population values for the empirical estimates.
  • Simulation setup: The Wasserstein simulations consider product measures defined on the Borel σ-algebra of Rd.This specifies the distributional setting used for the Wasserstein examples.

1) Estimator of

The paper evaluates empirical estimators for the Wasserstein distance, MMD, Dudley metric, and β using finite i.i.d. samples, comparing estimates with population values across sample sizes and dimensions.

  • Wasserstein distance: Wasserstein estimates improve with increasing sample size and correctly estimate W(P, Q), but large dimensions introduce substantial bias at fixed sample size.The experiments use linear programs and show that more samples are needed as dimensionality increases.
  • MMD: For the MMD exponential-distribution example, γk(P, Q) equals 0.2481 for d = 1 and 0.3892 for d = 5.These are population values shown as thin dotted lines in the corresponding figures.
  • MMD: MMD estimates improve with increasing sample size and correctly estimate γk(P, Q), while fixed-sample estimates are biased at large dimensions.For Gaussian examples with the chosen kernel, the population value is γk(P, Q) = 5−d/4(2 −2e−d/10)1/2.
  • Dudley metric: The Dudley-metric estimator correctly estimates β(P, Q) in the discrete-distribution experiment using samples and a linear program.The experiment draws N i.i.d. samples, with m = n = N/2, and solves the linear program in (21).

D. Non-parametric estimation of total variation distance

The paper studies empirical estimation of total variation distance and shows that the unrestricted empirical estimator is not strongly consistent, motivating consistently estimable lower bounds.

  • Empirical estimation: The empirical total-variation estimator is not strongly consistent for all probability distributions.For absolutely continuous P, the empirical measure can remain at total variation distance 2 from P.
  • Scope boundary: For unrestricted total-variation estimation, strong consistency requires restricting the set of probability measures.For suitable restricted distribution classes, total variation can be estimated by a strongly consistent estimator.
  • Consistent alternatives: Restricting the function class can yield a consistent IPM estimator bounded above by total variation distance.Examples include the Dudley metric from Fβ and the Kolmogorov distance from indicator functions of half-lines.
  • Lower bounds: The paper provides lower bounds on total variation in terms of Wasserstein distance, Dudley metric, and MMD, all of which can be consistently estimated.These bounds also yield lower bounds on KL-divergence through Pinsker’s inequality.
  • Lower bounds: The Wasserstein–Dudley lower bound is tighter than the simple bound T V (P, Q) ≥ β(P, Q) for P ≠ Q.The difference satisfies W(P,Q)−β(P,Q) ≥ β(P, Q), with equality only when P = Q.

IV. INTERPRETABILITY OF IPMS: RELATION TO BINARY CLASSIFICATION

The paper interprets IPMs through binary classification, relating distances between class-conditional distributions to classification risk and classifier smoothness.

  • IV. INTERPRETABILITY OF IPMS: RELATION TO BINARY CLASSIFICATION: IPMs are related to binary classification through optimal risks and through the smoothness of appropriate classifiers.The section specifically considers β, W, total variation, and γk.
  • IV. INTERPRETABILITY OF IPMS: RELATION TO BINARY CLASSIFICATION: The classification interpretation treats the discriminant-function class as the key restriction connecting an IPM to an optimal risk.The paper later identifies γF(P, Q) with the negative of an optimal loss risk for restricted discriminants.
  • IV. INTERPRETABILITY OF IPMS: RELATION TO BINARY CLASSIFICATION: The section connects Wasserstein and β distances to the margins of Lipschitz and bounded-Lipschitz classifiers, respectively.The stated significance is a relation between classifier smoothness and distance between class-conditional distributions.

A. Interpretation of β, W, T V and γk as the optimal risk of a binary classification problem

The paper formalizes IPMs as negative optimal risks for binary classifiers whose discriminant functions belong to a symmetric function class, connecting this view to earlier φ-divergence results.

  • A. Interpretation of β, W, T V and γk as the optimal risk of a binary classification problem: P and Q serve as the class-conditional distributions, while ε denotes the prior probability of class +1.The classifier uses a real-valued discriminant whose sign determines the classification decision.
  • A. Interpretation of β, W, T V and γk as the optimal risk of a binary classification problem: Earlier work links selected loss functions to φ-divergences, including hinge loss to total variation and logistic loss to χ2-divergence.The paper presents the IPM result as an analogous relation between losses, restricted classifiers, and distances.
  • A. Interpretation of β, W, T V and γk as the optimal risk of a binary classification problem: γF(P, Q) is the negative of the optimal L-risk for classifying P and Q when discriminant functions are restricted to F.This interpretation applies to total variation, Dudley metric, Wasserstein distance, and MMD through their corresponding function classes.
  • A. Interpretation of β, W, T V and γk as the optimal risk of a binary classification problem: The empirical classification problem uses finite i.i.d. labeled samples and reduces to estimating γF(Pm, Qn).When F is symmetric around zero, the sign of a function solving the empirical IPM optimization gives the classifier.

B. Wasserstein distance and Dudley metric: Relation to Lipschitz and bounded Lipschitz classifiers

The paper formulates Lipschitz and bounded Lipschitz classifiers as large-margin optimization problems and relates their margins and smoothness to Wasserstein distance and the Dudley metric.

  • Lipschitz classifier: The Lipschitz classifier minimizes its Lipschitz norm subject to unit-margin constraints on a separable training sequence.The resulting function classifies the training sequence correctly, with smaller Lipschitz norm corresponding to a smoother classifier.
  • Bounded Lipschitz classifier: The bounded Lipschitz classifier is obtained by replacing the Lipschitz norm with the bounded Lipschitz norm in the same optimization program.
  • Distance–classifier relations: Theorem 18 relates Wasserstein distance and the Dudley metric to the margins of Lipschitz and bounded Lipschitz classifiers.
  • Distance–classifier relations: 2 bounds the Lipschitz classifier’s smoothness norm below by an inverse Wasserstein-distance quantity.Thus, smaller Wasserstein distance requires a less smooth, more complex Lipschitz classifier.

C. Maximum mean discrepancy: Relation to Parzen window classifier and support vector machine

The paper interprets maximum mean discrepancy through kernel-based classification, connecting it to Parzen window rules, RKHS mean-function geometry, and SVM smoothness.

  • Parzen window classifier: The empirical MMD maximizer yields a classification function whose sign gives a Parzen window classification rule.The paper identifies this rule explicitly with the classification function of a Parzen window classifier.
  • RKHS interpretation: The MMD γk(Pm,Qn) is the RKHS distance between the class mean functions μ+ and μ−.
  • RKHS interpretation: Under equal RKHS norms of the class means, the classifier can be written as a nearest-neighbor rule in RKHS feature space.It assigns x the label of whichever mean function is closer to k(·,x).
  • Comparison with Parzen classification: The MMD-based rule generalizes classical Parzen classification because its domain and kernel need not be translation invariant, and its kernel is positive definite.
  • Relation to SVM: The paper relates MMD to SVM through classifier margins and interprets IPMs using binary classification risk and classifier smoothness.

APPENDIX A PROOF OF LEMMA 3

This appendix proves consistency-related bounds for empirical IPM estimates by controlling empirical-process deviations with symmetrization and concentration inequalities.

  • Consistency: Uniform deviations for the two distributions converge almost surely to zero, yielding consistency of the empirical estimator.
  • Error decomposition: The empirical IPM estimation error is bounded by the sum of the uniform deviations for the two sampled distributions.
  • Concentration argument: The proof bounds uniform deviations using symmetrization and McDiarmid’s inequality.The two-sample analysis applies the concentration argument separately to the empirical processes for P and Q.

APPENDIX D PROOF OF LEMMA 15

This appendix develops a convex-analytic proof using boundary attainment, extension lemmas, concentration, and symmetrization results collected for later arguments.

  • Convexity argument: A convex-function argument shows that an optimizer on a convex set lies on the relevant boundary when the function is nonconstant.
  • Auxiliary results: The appendix collects auxiliary results used to prove results in Section III.
  • Extension lemmas: Lipschitz functions on finite subsets can be extended to the whole space without increasing their Lipschitz constant.The extension can also be explicitly constructed.
  • Extension lemmas: Bounded Lipschitz functions can likewise be extended from a subset to the whole space while preserving the bounded Lipschitz norm.
  • Empirical-process tools: The appendix states McDiarmid’s inequality and the Rademacher symmetrization lemma as tools for empirical-process bounds.
Loading 0901.2698v4…