PaperlayerView exact revision on arXiv

Source-linked AI summary

On Wasserstein Two Sample Testing and Related Families of Nonparametric Tests

Aaditya Ramdas, Nicolas Garcia, Marco Cuturi

arXiv:1509.02237v2math.STstat.ML

TL;DR

Nonparametric two-sample testing seeks distributional differences without parametric assumptions, but its many univariate and multivariate methods are often treated separately. The paper uses Wasserstein distance to connect these families, including Energy distance, MMD, CDF/quantile-based tests, and ROC/ODC methods, and constructs a distribution-free Wasserstein test. Its scope is limited because several other test classes are not covered.

  • Problem

    Nonparametric two-sample testing compares distributions without parametric assumptions, yet its diverse univariate and multivariate test families require connections across methods.

  • Method

    The paper organizes these tests around Wasserstein distance, using entropy smoothing and distribution-function representations to connect distance, kernel, classical univariate, and ROC/ODC approaches.

  • Results

    The paper establishes connections from Wasserstein testing to Energy distance, kernel MMD, KS and PP/QQ methods, and ROC/ODC curves, including a distribution-free Wasserstein test.

  • Takeaways & Limitations

    Wasserstein distance provides a common perspective for relating several seemingly distinct nonparametric two-sample tests across univariate and multivariate settings.

  • Takeaways & Limitations

    The paper does not cover all nonparametric two-sample tests, including rank-based and several graphical or neighborhood-based families.

Abstract

from arXiv · show

Nonparametric two sample or homogeneity testing is a decision theoretic problem that involves identifying differences between two random variables without making parametric assumptions about their underlying distributions. The literature is old and rich, with a wide variety of statistics having being intelligently designed and analyzed, both for the unidimensional and the multivariate setting. Our contribution is to tie together many of these tests, drawing connections between seemingly very different statistics. In this work, our central object is the Wasserstein distance, as we form a chain of connections from univariate methods like the Kolmogorov-Smirnov test, PP/QQ plots and ROC/ODC curves, to multivariate tests involving energy statistics and kernel based maximum mean discrepancy. Some connections proceed through the construction of a \textit{smoothed} Wasserstein distance, and others through the pursuit of a "distribution-free" Wasserstein test. Some observations in this chain are implicit in the literature, while others seem to have not been noticed thus far. Given nonparametric two sample testing's classical and continued importance, we aim to provide useful connections for theorists and practitioners familiar with one subset of methods but not others.

1 Introduction

The paper studies nonparametric two-sample testing through the Wasserstein distance, connecting univariate and multivariate test families. It develops links among CDF-, quantile-, characteristic-function-, distance-, and kernel-based perspectives while acknowledging incomplete coverage of the broader literature.

  • The paper aims to inform readers familiar with some test families by tying together seemingly distinct methods, but it does not cover all nonparametric two-sample tests.Rank-based, spanning-tree, nearest-neighbor, and cross-match tests are among the omitted classes.
  • The paper restricts attention to nonparametric tests for differences in entire distributions, rather than parametric tests or tests targeting only particular moments.The setting covers two d-dimensional distributions without parametric assumptions.
  • Entropy smoothing connects multivariate Wasserstein distance to Energy distance and, through distance-kernel relationships, to kernel MMD.Varying the regularization weight interpolates between Wasserstein and Energy distance.
  • The paper relates univariate Wasserstein testing to Kolmogorov-Smirnov tests, PP/QQ plots, and Cramer-von-Mises-style comparisons.These connections arise from comparing distribution representations such as CDFs and quantile functions.
  • A distribution-free univariate Wasserstein test is developed through connections with ROC/ODC curves.The paper also provides a limiting-distribution analysis for this construction.

2 Nonparametric Two Sample Testing

This section formulates nonparametric two-sample testing for empirical samples and frames tests through statistics, thresholds, power, and null distributions. It organizes comparisons around CDFs, quantile functions, and characteristic functions, while noting dimensional limits for classical CDF-based tests.

  • The setup uses independent samples from probability measures P and Q, with empirical measures P_n and Q_m formed from the observations.A test maps the combined sample data to a binary decision, or to [0,1] when randomized.
  • Tests compute a scalar statistic and reject the null when its normalized value crosses a threshold calibrated to a prespecified false-positive rate α.The threshold is chosen so the asymptotic type-I error is at most α.
  • The Neyman-Pearson framework evaluates a test through its power, while classical consistency requires power to approach one under fixed alternatives.The paper notes that general high-dimensional consistency conditions remain largely open.
  • Distribution comparisons are organized through cumulative distribution functions, characteristic functions, and quantile functions.Many statistics compare empirical estimates of these distribution-characterizing quantities.
  • In one dimension, Wasserstein distance compares quantile functions, whereas Kolmogorov-Smirnov compares empirical CDFs.Classical CDF-based tests become less common in higher dimensions partly because multivariate empirical CDF estimation suffers from the curse of dimensionality.
  • Kernel and distance-based tests provide popular alternatives, with Gaussian MMD linked to characteristic-function differences and Energy distance linked to projected CDF differences.

3 Entropy Smoothed Wasserstein Distances

This section presents Wasserstein distance as a distribution-comparison tool, then develops its computational and statistical limitations and its connections to entropy-regularized transport, Energy Distance, and MMD.

  • 3.1 Wasserstein Distance: The p-Wasserstein distance compares probability measures on R^d using a metric and applies equally to empirical measures and densities when they exist.Its definition uses joint measures with prescribed marginals P and Q.
  • 3.1 Wasserstein Distance: For uniform empirical measures, computing Wasserstein distance is a transportation problem represented as a linear program over coupling matrices with fixed row and column marginals.The cost matrix contains pairwise sample distances raised to the power p.
  • 3.1 Wasserstein Distance: Wasserstein estimation converges more slowly as dimension increases, and its computation is expensive because optimal transport has at least super-cubic scaling in sample size.For d ≥ 3, the difference scales as n^-1/d; in d = 2, the rate scales as n^-1/2.
  • 3.2 Entropy-Regularized Wasserstein Distance: Entropic regularization defines the Sinkhorn divergence and yields a strongly convex problem with a unique solution represented as a diagonal scaling of the elementwise exponential cost matrix.The regularized objective adds an entropy term weighted by λ.
  • 3.3 Smoothing the Wasserstein Distance to Energy Distance: Energy Distance is zero exactly when P = Q, so thresholding its sample statistic produces a test consistent against fixed alternatives under mild moment conditions.The paper presents this statistic as a distance-based two-sample test closely related to the smoothed Wasserstein construction.
  • 3.4 From Energy Distance to Kernel Maximum Mean Discrepancy: Energy Distance and kernel MMD are strongly connected: each kernel induces a metric, and MMD with that kernel equals Energy Distance with the induced metric.For characteristic kernels, MMD is zero if and only if P = Q; its estimation error is independent of dimension d.

4 Wasserstein Distance and PP or QQ tests

The section connects PP/QQ comparisons and Wasserstein distance through empirical CDFs and quantile functions, emphasizing their asymptotic null distributions and distribution-free behavior. In one dimension, Wasserstein distance is an Lp comparison of quantile functions, making it a QQ-based test statistic.

  • Comparing CDFs and QFs: PP plots compare empirical CDFs, whereas QQ plots compare empirical quantile functions; formal tests analyze corresponding distances between these estimates.The setup assumes, for simplicity, distributions supported on [0, 1] with positive densities, though the authors note broader validity under mild assumptions.
  • Null distributions: The asymptotic null distribution of finite-p distances between empirical CDFs or quantile functions generally depends on the common distribution.For quantile comparisons, this applies to L2 and analogously to finite Lp distances; CDF-based Lp distances face the same distribution-dependence obstacle.
  • Comparing CDFs (PP): The L∞ distance between empirical CDFs has a distribution-free null limit, yielding the two-sample Kolmogorov-Smirnov statistic.Continuity of the common CDF maps [0, 1] onto [0, 1], producing the distribution-free equality used for the KS test.
  • Comparing QFs (QQ): Finite-p quantile-distance tests require bootstrap or permutation methods to control type-I error because their null distributions are distribution dependent.The paper notes that this computational burden may have contributed to these tests being overlooked, despite modern computing making them worthy of further study.
  • Wasserstein interpretation: Wasserstein distance measures horizontal discrepancies by the transport cost required to move mass between distributions and captures weak convergence together with p-th moment convergence.The paper also notes that empirical Wasserstein-based tests are classically consistent, while general high-dimensional consistency conditions remain largely open.
  • Wasserstein is a QQ test: In one dimension, the p-Wasserstein distance equals an Lp distance between quantile functions, so Wasserstein testing is a QQ comparison.For p ∈ [1, ∞), the representation holds for distributions with finite p-moments; the bounded-support p = ∞ case likewise uses the quantile-function difference.

5 A Distribution-Free Wasserstein Test

The paper constructs a distribution-free Wasserstein test by relating empirical ODC curves to uniform distributions under the null. This removes dependence on unknown distribution functions and connects Wasserstein distances to ROC/ODC representations.

  • Test construction: The proposed test replaces a Wasserstein distance whose null distribution depends on unknown F with a distance to U[0, 1] whose null distribution is independent of F.This construction yields a distribution-free Wasserstein test.
  • ROC and ODC curves: ROC curves encode distribution distinguishability, and their area equals P(Y < X) for Y ∼ Q and X ∼ P.The ROC curve is obtained from the ODC curve by reversing the axes, motivating the focus on ODC curves.
  • ODC representation: The ODC curve is the quantile function of the push-forward measure G♯P, while the empirical ODC curve is the quantile function of G_m♯P_n.Thus, the p-Wasserstein distance between these measures equals the corresponding Lp distance between the ODC curve and its empirical version.
  • Distribution-free reduction: Under H0 : P = Q, the empirical ODC curve has a distribution independent of P.The reduction uses transformed samples whose relevant empirical distributions involve uniform random variables.
  • Distribution-free reduction: The Wasserstein distances between the transformed empirical measures and their population counterpart are distribution free under the null.This applies to both W_p and W_∞ distances in the stated construction.
  • Asymptotic analysis: The asymptotic analysis treats the difference between empirical and population ODC curves as elements of D([0, 1]) and uses weak convergence results involving Brownian bridges.Under H0, the result follows by reducing to the uniform distribution.

6 Conclusion

The conclusion presents the Wasserstein distance as a central link among diverse univariate and multivariate two-sample tests. It also states that a comprehensive empirical survey remains outside the paper’s scope.

  • Connections: The Wasserstein statistic connects the Kolmogorov-Smirnov test, graphical QQ plots, ROC/ODC curves, Energy Distance, and kernel MMD.The ROC/ODC connection yields a distribution-free Wasserstein variant, while entropic smoothing links Wasserstein and Energy Distance tests.
  • Connections: Entropic smoothing relates the Wasserstein test to multivariate Energy Distance and, transitively, to kernel Maximum Mean Discrepancy.These connections extend the paper’s univariate and multivariate test framework.
  • Scope: A comprehensive empirical survey is outside the paper’s current scope.The paper instead aims to connect test families through distribution representations and null distributions.

A Proof of Proposition 1

The proof establishes the structure of an optimal one-dimensional transport plan. Monotonicity follows from showing that crossing transport assignments can be rearranged to reduce cost.

  • Existence and monotonicity: An optimal transport plan exists because the transport objective is linear and the feasible set Γ(P, Q) is compact under weak convergence.The proof denotes an optimizer by π∗.
  • Existence and monotonicity: If x1 < x2 for points in the support of π∗, optimality implies y1 ≤ y2.The proof proceeds by contradiction: crossing assignments would violate optimality.
  • Cost comparison: For p > 1, strict convexity of t ↦ t^p yields the strict cost comparison needed to rule out crossing assignments.The p = 1 case follows directly, while the p > 1 argument uses an intermediate convex combination.
  • Cost comparison: Crossing transport is more expensive because exchanging destinations can reduce the transportation cost, contradicting cyclic monotonicity.This is the contradiction that establishes monotone support for the optimal plan.
  • Support characterization: For x ∈ supp(P) and y ∈ supp(Q), support membership in π∗ is characterized by F(x) = G(y).The characterization follows from monotonicity and the marginal constraints defining Γ(P, Q).

B Proof of Lemma 1

The lemma rewrites empirical ODC quantities using transformed uniform samples. Under the null, this representation makes their distribution independent of the original CDFs.

  • Uniform transformation: The proof indexes the order statistics of the Y sample and identifies intervals on which the empirical CDF G_m is constant.These intervals are then expressed through the quantile function F^-1 and transformed uniform variables.
  • Uniform transformation: The interval characterization is converted into an equivalent statement involving the empirical CDF of transformed uniform Y variables.This establishes the correspondence between G_m and the uniform-sample empirical CDF.
Loading 1509.02237v2…