PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Two-Sample Testing with Analytic Representations of Probability Measures

Kacper Chwialkowski, Aaditya Ramdas, Dino Sejdinovic, Arthur Gretton

arXiv:1506.04725v1stat.ML

TL;DR

The paper addresses the challenge of fast, nonparametric two-sample testing when conventional distribution representations are costly or prior linear-time characteristic-function tests lack broad consistency. It introduces two tests based on analytic representations evaluated at randomly chosen locations, and reports better power/computation tradeoffs across challenging real-world and artificial problems. The approach has scope limitations because one unsmoothed distance can fail to distinguish many measures, and an experiment omits quadratic-time testing at very large sample size.

  • Problem

    Nonparametric two-sample tests must compare distributions represented by infinite-dimensional objects, while prior linear-time characteristic-function tests can fail consistency.

  • Method

    The paper constructs linear-time tests from smoothed empirical characteristic functions and analytic mean embeddings, using finite random evaluations of these representations.

  • Results

    The tests provide better power/computation tradeoffs than competing characteristic-function, sub-quadratic MMD, and quadratic-time MMD methods across challenging real-world and artificial problems.

  • Takeaways & Limitations

    Analytic representations make finite random evaluations sufficient for almost-sure distributional discrimination while retaining linear-time computation.

  • Takeaways & Limitations

    The distance dϕ,J(P, Q) can fail to distinguish a large class of measures, and quadratic-time MMD was not run for experiments with sample size 10000.

Abstract

from arXiv · show

We propose a class of nonparametric two-sample tests with a cost linear in the sample size. Two tests are given, both based on an ensemble of distances between analytic functions representing each of the distributions. The first test uses smoothed empirical characteristic functions to represent the distributions, the second uses distribution embeddings in a reproducing kernel Hilbert space. Analyticity implies that differences in the distributions may be detected almost surely at a finite number of randomly chosen locations/frequencies. The new tests are consistent against a larger class of alternatives than the previous linear-time tests based on the (non-smoothed) empirical characteristic functions, while being much faster than the current state-of-the-art quadratic-time kernel-based or energy distance-based tests. Experiments on artificial benchmarks and on challenging real-world testing problems demonstrate that our tests give a better power/time tradeoff than competing approaches, and in some cases, better outright power than even the most expensive quadratic-time tests. This performance advantage is retained even in high dimensions, and in cases where the difference in distributions is not observable with low order statistics.

1 Introduction

The paper develops linear-time two-sample tests using finite evaluations of analytic representations, addressing the consistency limitations and computational costs of earlier approaches. Experiments report better power/computation tradeoffs across real-world and artificial testing problems.

  • Motivation: Traditional two-sample tests compare infinite-dimensional distribution representations, making distances between distributions computationally challenging.Examples include density functions, cumulative distribution functions, characteristic functions, and RKHS mean embeddings.
  • Limitations of prior methods: Multiple-frequency characteristic-function tests retain linear sample complexity but can fail consistency when tested frequencies fall where distinct characteristic functions agree.This motivates representations whose differences can be detected from finitely many random evaluations.
  • Proposed representations: The paper introduces smoothed characteristic-function and analytic mean-embedding distances that almost surely distinguish distributions from a single randomly chosen frequency or point.Evaluating more locations can generally increase test power without requiring the full infinite-dimensional representation.
  • Statistical tests: The resulting tests use empirical differences between analytic representations and offer linear-time computation with constant memory requirements.The analytic mean-embedding test is almost surely consistent for all distributions, while the smoothed characteristic-function test is almost surely consistent for distributions with integrable characteristic functions.
  • Experiments: Experiments show better power/computation tradeoffs than characteristic-function, sub-quadratic MMD, and quadratic-time MMD competitors on real-world, high-dimensional, and subtle artificial problems.The reported advantage includes challenging multivariate settings and cases where distributional differences are difficult to detect.

2 Analytic embeddings and distances

The paper constructs randomized distances by evaluating analytic representations of probability measures at finitely many random points. Smoothing characteristic functions or using analytic RKHS embeddings restores almost-sure discrimination while enabling linear-time testing.

  • Randomized analytic representations: Evaluating analytic representations at any J > 0 randomly selected points is almost surely injective, yielding a randomized metrization of probability measures.This metrization underlies the paper’s linear-time nonparametric two-sample tests.
  • Randomized analytic representations: Finite-dimensional MMD approximations reduce the cost of empirical estimation, which otherwise requires quadratic-time U-statistics and averages.The approximation samples frequencies from the density F^-1κ.
  • Smoothed characteristic functions: Unsmooth characteristic-function distances can fail to distinguish an uncountable class of distinct probability measures, violating the metric coincidence axiom.The paper therefore treats the original construction as a random pseudometric rather than a random metric.
  • Smoothed characteristic functions: For analytic integrable kernels with strictly positive inverse Fourier transforms, smoothed characteristic-function distances are random metrics for distributions with integrable characteristic functions.Analyticity also makes the smoothed characteristic functions analytic.
  • Smoothed characteristic functions: Smoothing spreads localized characteristic-function differences across frequency space, making them easier to detect at a small number of random points.The paper links this mechanism to improved test power over unsmoothed characteristic functions.
  • Analytic mean embeddings: For analytic, integrable, characteristic kernels, randomized mean-embedding distances are random metrics for all probability measures, without requiring integrable characteristic functions.The resulting tests have linear time complexity and constant memory requirements.

3 Hypothesis Tests Based on Distances Between Analytic Functions

The paper constructs two linear-time two-sample tests from distances between analytic representations, using analytic mean embeddings and smooth characteristic functions. Hotelling’s T^2 calibration yields asymptotic chi-squared statistics, while analytic representations support detection from finitely many randomly selected points.

  • Test construction: Two linear-time tests use analytic mean embeddings and smooth characteristic functions to compare distributions.The smooth-characteristic-function estimator is rewritten as an expectation so it can be estimated in linear time.
  • Comparison with alternatives: Analytic mean embeddings and smooth characteristic functions provide randomized finite-point representations, while competing empirical-characteristic-function tests do not perform smoothing.The paper contrasts these methods with block MMD, subsampled MMD, and quadratic-time MMD alternatives.
  • Analytic mean embedding test: The embedding test forms kernel differences at selected test points and uses their empirical mean and covariance in a Hotelling’s T^2 statistic.The covariance matrix requires inversion of a J × J matrix, with J typically less than 10 in the experiments.
  • Analytic mean embedding test: The embedding statistic is asymptotically χ2 with J degrees of freedom, and its rejection probability approaches one when the underlying distance is positive.The test rejects when the statistic exceeds the 1−α quantile of χ2_J.
  • Smooth characteristic-function test: The smooth-characteristic-function statistic is asymptotically χ2 with 2J degrees of freedom, with rejection probability approaching one under a positive distance.Its vector of differences contains real and imaginary components evaluated at the selected frequencies.

4 Experiments

The experiments compare the proposed Smooth CF and Mean Embedding tests with competing methods across real, synthetic, and high-dimensional settings. The proposed tests generally offer strong power–computation tradeoffs, with Mean Embedding best in the redundant-dimension experiments and random-distance tests best in the Blobs timing comparison.

  • Experimental setup: The experiments compare Smooth CF and Mean Embedding against Block MMD, CF, MMD(√n), and quadratic-time MMD.The comparison spans artificial benchmarks and real-world datasets.
  • Validation: Type I error is assessed at the design level α = 0.05, with results averaged over 4000 runs and shown with 95% confidence intervals.The appendix also displays a 99% Wald interval around the design test size.
  • Real-world datasets: In the Higgs experiment, tests evaluate distinguishing background from Higgs-producing processes using four-dimensional jet angular-momentum distributions.The angular-momentum features carry little discriminating information relative to other features, making the task challenging.
  • Real-world datasets: In the amplitude-modulated music experiment, one-thousand-dimensional signals receive Gaussian noise with variance ranging from 1 to 4.0.Mean Embedding and Smooth CF are reported as more robust to moderate noise contamination than the other tests.
  • High-dimensional data: The Mean Embedding test gives the best performance on both high-dimensional datasets, especially when the distributions differ in variance.The dimensions range from 50 to 1000 for Dataset I and from 50 to 2500 for Dataset II.
  • Synthetic benchmarks: On the Blobs dataset, quadratic-time MMD reaches power one at n = 1400 and has the best sample-size power, whereas random-distance tests have the best power/computation tradeoff.The Blobs task encodes distributional differences at a smaller lengthscale than the overall data.

Proof of Proposition 1

The proposition establishes that an uncountable family of distinct characteristic functions can remain identical outside a sufficiently large interval. Distinct members differ near their defining boundary points, supporting the later random-evaluation argument.

  • For some I = I(ϵ), an interval [−I, I] captures measure 1 − (1 − ϵ)^(1/J).
  • The family contains uncountably many characteristic functions that agree on the complement of [−I, I].
  • For w1 > w2 > 1/I, fw1 and fw2 differ in a neighborhood of 1/w1.

Proof of Theorem 2

The proof of Theorem 2 shows that analytic mean embeddings yield a random metric when evaluated at finitely many random points. Injectivity separates distinct measures, while analyticity makes accidental agreement occur with probability zero.

  • A bounded analytic kernel has an RKHS whose functions are analytic.
  • A nonzero analytic function vanishes only on a set of Lebesgue measure zero under an absolutely continuous measure.
  • Evaluating an injective map into analytic functions at J independently sampled points produces an almost surely injective random representation.
  • The resulting distance is symmetric, satisfies the triangle inequality almost surely, and is positive almost surely whenever P ≠ Q.
  • For a characteristic kernel, the mean-embedding map is injective; analyticity then proves that dΛ,J(P, Q)^2 = dµ,J(P, Q)^2 is a random metric.

Proof of Theorem 1

The proof of Theorem 1 establishes that smooth characteristic functions are analytic and uniquely identify distributions under the stated kernel and integrability conditions. Their finite random evaluations therefore define an almost surely valid distance.

  • Under the stated assumptions, the smooth characteristic function φP is analytic.
  • The smooth characteristic function φP belongs to the RKHS associated with the analytic kernel.
  • The mapping P → φP is injective because the inverse Fourier transform preserves equality and the kernel transform is strictly positive.
  • Analyticity and injectivity imply that finite random evaluations yield dΛ,J(P, Q)^2 = dφ,J(P, Q)^2 as a random metric.

Proof of Lemma 3

The proof applies Fubini’s theorem to exchange the order of integration, relying on finiteness of the resulting iterated integral.

  • Fubini’s theorem is used to obtain the required integral identity.The proof explicitly invokes Fubini’s theorem.
  • The interchange is justified because the iterated integral is finite.The finiteness condition is attributed to Theorem 8.8(b).
  • The argument therefore depends on an integrability condition supporting the application of Fubini’s theorem.

Proof of Proposition 2

The proof establishes asymptotic chi-squared behavior for the statistic built from random evaluations, while excluding measure-zero degeneracies and showing convergence of the covariance estimates.

  • For almost all random evaluation points, S_n converges to a χ2 distribution with J degrees of freedom.The proof works on the product probability space of the random evaluation points and observations.
  • The vectors Z_i are formed from kernel differences evaluated at the random points T_1(ω),…,T_J(ω).Each coordinate is k(X_i,T_j(ω))−k(Y_i,T_j(ω)).
  • The multivariate central limit theorem yields Gaussian convergence with covariance matrix Σ_ω.
  • The resulting statistic has an asymptotic χ2 distribution with J degrees of freedom by the CLT and Slutsky’s theorem.
  • The sample covariance and its inverse converge to their population counterparts under the stated continuity and positive-definiteness conditions.
  • Degenerate cases, including coincident evaluation points or vanishing limiting quantities, occur only on a measure-zero set.

C.1 Quadratic-time MMD test

Quadratic-time MMD estimates the squared distance between mean embeddings, but calibrating its null distribution is computationally expensive and depends on unknown kernel eigenvalues.

  • MMD compares distributions through the RKHS norm of the difference between their mean embeddings.The test uses an empirical estimator of the squared population MMD.
  • The unbiased MMD estimator is built from pairwise kernel terms summarized by h(x,x′,y,y′).
  • The MMD test rejects when its empirical statistic exceeds the null quantile r_α.
  • The null distribution is an infinite weighted sum of chi-squared variables whose weights are eigenvalues relative to the unknown distribution P.
  • Bootstrap or permutation calibration costs O(b_n n^2), while the gamma approximation lacks consistency guarantees.The permutation count b_n is usually at least in the hundreds.

C.2 Sub-quadratic time MMD test

Sub-quadratic MMD variants interpolate between linear-time and quadratic-time computation through block size, while parameter selection uses repeated p-value evaluations and scale-specific choices.

  • The block MMD statistic averages quadratic-time statistics computed within data blocks.
  • Block size controls computation from linear-time MMD with B=2 to full MMD with one block of size n.Keeping B constant as n grows preserves consistency in the described setting.
  • The block-based variance can be estimated directly or from the empirical variance of statistics computed within blocks.
  • Parameter selection evaluates p-values across data scalings, choosing the scaling with the smallest median and using outliers as a tie-breaker.The example selects 2^0.0 for B-test, 2^-8.0 for Smoothed CF, and 2^-10.0 for CF.
  • With constant block size, the block statistic satisfies a central-limit-theorem approximation using the corresponding exact block variance.
Loading 1506.04725v1…