Comparing distributions: \ℓ₁ geometry improves kernel two-sample\n testing

2019/09/19 by Meyer Scetbon, Gaël Varoquaux, Scetbon, M. +1 · 5 citations
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Generative Adversarial Networks and Image Synthesis #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1909.09264

openalex publication_date 2019/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Are two sets of observations drawn from the same distribution? This problem\nis a two-sample test. Kernel methods lead to many appealing properties. Indeed\nstate-of-the-art approaches use the L² distance between kernel-based\ndistribution representatives to derive their test statistics. Here, we show\nthat L^p distances (with p\≥ 1) between these distribution\nrepresentatives give metrics on the space of distributions that are\nwell-behaved to detect differences between distributions as they metrize the\nweak convergence. Moreover, for analytic kernels, we show that the L¹\ngeometry gives improved testing power for scalable computational procedures.\nSpecifically, we derive a finite dimensional approximation of the metric given\nas the \ℓ₁ norm of a vector which captures differences of expectations of\nanalytic functions evaluated at spatial locations or frequencies (i.e,\nfeatures). The features can be chosen to maximize the differences of the\ndistributions and give interpretable indications of how they differs. Using an\n\ℓ₁ norm gives better detection because differences between\nrepresentatives are dense as we use analytic kernels (non-zero almost\neverywhere). The tests are consistent, while much faster than state-of-the-art\nquadratic-time kernel-based tests. Experiments on artificial and real-world\nproblems demonstrate improved power/time tradeoff than the state of the art,\nbased on \ℓ₂ norms, and in some cases, better outright power than even the\nmost expensive quadratic-time tests.\n

Cited by

• Anchor-based Maximum Discrepancy for Relative Similarity Testing
• Learning Kernel Tests Without Data Splitting
• Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach
• Equitable and Optimal Transport with Multiple Agents
• Testing Goodness of Fit of Conditional Density Models with Kernels

Related

• Fast Two-Sample Testing with Analytic Representations of Probability\n Measures
• Boosting the Power of Kernel Two-Sample Tests
• Adaptivity and Computation-Statistics Tradeoffs for Kernel and Distance based High Dimensional Two Sample Testing
• Hypothesis testing using pairwise distances and associated kernels (with Appendix)
• A Kernel Method for the Two-Sample Problem