Fast Two-Sample Testing with Analytic Representations of Probability Measures

Abstract

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.

Cited by in corpus (26)

• Large-Scale Kernel Methods for Independence Testing
• Statistical Inference for Generative Models with Maximum Mean Discrepancy
• Nonparametric Detection of Geometric Structures over Networks
• hyppo: A Multivariate Hypothesis Testing Python Package
• Classification Logit Two-sample Testing by Neural Networks
• Two-sample Testing Using Deep Learning
• PEARL: Data Synthesis via Private Embeddings and Adversarial Reconstruction Learning
• Neural Tangent Kernel Maximum Mean Discrepancy
• McKernel: A Library for Approximate Kernel Expansions in Log-linear Time
• Testing and Learning on Distributions with Symmetric Noise Invariance
• Generalized Sliced Distances for Probability Distributions
• Reciprocal Adversarial Learning via Characteristic Functions
• Universal Hypothesis Testing with Kernels: Asymptotically Optimal Tests for Goodness of Fit
• Concept Drift Detection: Dealing with MissingValues via Fuzzy Distance Estimations
• Kernel-Guided Training of Implicit Generative Models with Stability Guarantees
• Testing Goodness of Fit of Conditional Density Models with Kernels
• Calibration tests beyond classification
• Quantization Algorithms for Random Fourier Features
• Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data
• Asymptotically Optimal One- and Two-Sample Testing with Kernels
• Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples
• Exponentially Consistent Kernel Two-Sample Tests
• Two-Sample Test Based on Classification Probability
• A Witness Two-Sample Test
• The AUGUST Two-Sample Test: Powerful, Interpretable, and Fast
• A fast and effective kernel two-sample test for large-scale data