MMD Aggregated Two-Sample Test
- URL: http://arxiv.org/abs/2110.15073v4
- Date: Mon, 21 Aug 2023 15:20:37 GMT
- Title: MMD Aggregated Two-Sample Test
- Authors: Antonin Schrab and Ilmun Kim and M\'elisande Albert and B\'eatrice
Laurent and Benjamin Guedj and Arthur Gretton
- Abstract summary: We propose two novel non-parametric two-sample kernel tests based on the Mean Maximum Discrepancy (MMD)
First, for a fixed kernel, we construct an MMD test using either permutations or a wild bootstrap, two popular numerical procedures to determine the test threshold.
We prove that this test controls the level non-asymptotically, and achieves the minimax rate over Sobolev balls, up to an iterated logarithmic term.
- Score: 31.116276769013204
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We propose two novel nonparametric two-sample kernel tests based on the
Maximum Mean Discrepancy (MMD). First, for a fixed kernel, we construct an MMD
test using either permutations or a wild bootstrap, two popular numerical
procedures to determine the test threshold. We prove that this test controls
the probability of type I error non-asymptotically. Hence, it can be used
reliably even in settings with small sample sizes as it remains
well-calibrated, which differs from previous MMD tests which only guarantee
correct test level asymptotically. When the difference in densities lies in a
Sobolev ball, we prove minimax optimality of our MMD test with a specific
kernel depending on the smoothness parameter of the Sobolev ball. In practice,
this parameter is unknown and, hence, the optimal MMD test with this particular
kernel cannot be used. To overcome this issue, we construct an aggregated test,
called MMDAgg, which is adaptive to the smoothness parameter. The test power is
maximised over the collection of kernels used, without requiring held-out data
for kernel selection (which results in a loss of test power), or arbitrary
kernel choices such as the median heuristic. We prove that MMDAgg still
controls the level non-asymptotically, and achieves the minimax rate over
Sobolev balls, up to an iterated logarithmic term. Our guarantees are not
restricted to a specific type of kernel, but hold for any product of
one-dimensional translation invariant characteristic kernels. We provide a
user-friendly parameter-free implementation of MMDAgg using an adaptive
collection of bandwidths. We demonstrate that MMDAgg significantly outperforms
alternative state-of-the-art MMD-based two-sample tests on synthetic data
satisfying the Sobolev smoothness assumption, and that, on real-world image
data, MMDAgg closely matches the power of tests leveraging the use of models
such as neural networks.
Related papers
- Collaborative non-parametric two-sample testing [55.98760097296213]
The goal is to identify nodes where the null hypothesis $p_v = q_v$ should be rejected.
We propose the non-parametric collaborative two-sample testing (CTST) framework that efficiently leverages the graph structure.
Our methodology integrates elements from f-divergence estimation, Kernel Methods, and Multitask Learning.
arXiv Detail & Related papers (2024-02-08T14:43:56Z) - Risk-Sensitive Diffusion for Perturbation-Robust Optimization [58.68233326265417]
We show that noisy samples incur another objective function, rather than the one with score function, which will wrongly optimize the model.
We introduce risk-sensitive SDE, a type of differential equation (SDE) parameterized by the risk vector.
We prove that zero instability measure is only achievable in the case where noisy samples are caused by Gaussian perturbation.
arXiv Detail & Related papers (2024-02-03T08:41:51Z) - MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without
Data Splitting [28.59390881834003]
We propose novel statistics which maximise the power of a two-sample test based on the Maximum Mean Discrepancy (MMD)
We show how these kernels can be chosen in a data-dependent but permutation-independent way, in a well-calibrated test, avoiding data splitting.
We highlight the applicability of our MMD-FUSE test on both synthetic low-dimensional and real-world high-dimensional data, and compare its performance in terms of power against current state-of-the-art kernel tests.
arXiv Detail & Related papers (2023-06-14T23:13:03Z) - Boosting the Power of Kernel Two-Sample Tests [7.1795069620810805]
We propose a method to boost the power of the kernel test by combining MMD estimates over multiple kernels using their Mahalanobis distance.
The resulting test is universally consistent and, since it is obtained by aggregating over a rejection of kernels/bandwidths, is more powerful in detecting a wide range of alternatives in finite samples.
arXiv Detail & Related papers (2023-02-21T14:14:30Z) - Spectral Regularized Kernel Two-Sample Tests [7.915420897195129]
We show the popular MMD (maximum mean discrepancy) two-sample test to be not optimal in terms of the separation boundary measured in Hellinger distance.
We propose a modification to the MMD test based on spectral regularization and prove the proposed test to be minimax optimal with a smaller separation boundary than that achieved by the MMD test.
Our results hold for the permutation variant of the test where the test threshold is chosen elegantly through the permutation of the samples.
arXiv Detail & Related papers (2022-12-19T00:42:21Z) - A Permutation-free Kernel Two-Sample Test [36.50719125230106]
We propose a new quadratic-time MMD test statistic based on sample-splitting and studentization.
For large sample sizes, our new cross-MMD provides a significant speedup over the MMD, for only a slight loss in power.
arXiv Detail & Related papers (2022-11-27T18:15:52Z) - Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
We introduce two algorithms for black-box optimization based on the Thompson sampling (TS) policy.
To choose an input query, we only need to train an NN and then choose the query by maximizing the trained NN.
Our algorithms sidestep the need to invert the large parameter matrix yet still preserve the validity of the TS policy.
arXiv Detail & Related papers (2022-10-13T09:01:58Z) - Kernel Two-Sample Tests in High Dimension: Interplay Between Moment
Discrepancy and Dimension-and-Sample Orders [1.104121146441257]
We study the behavior of kernel two-sample tests when the dimension and sample sizes both diverge to infinity.
Our findings complement those in the recent interplay and shed new light on the use of kernel two-sample tests for high-dimensional literature and large-scale data.
arXiv Detail & Related papers (2021-12-31T23:12:44Z) - Maximum Mean Discrepancy Test is Aware of Adversarial Attacks [122.51040127438324]
The maximum mean discrepancy (MMD) test could in principle detect any distributional discrepancy between two datasets.
It has been shown that the MMD test is unaware of adversarial attacks.
arXiv Detail & Related papers (2020-10-22T03:42:12Z) - Noisy Adaptive Group Testing using Bayesian Sequential Experimental
Design [63.48989885374238]
When the infection prevalence of a disease is low, Dorfman showed 80 years ago that testing groups of people can prove more efficient than testing people individually.
Our goal in this paper is to propose new group testing algorithms that can operate in a noisy setting.
arXiv Detail & Related papers (2020-04-26T23:41:33Z) - Learning Deep Kernels for Non-Parametric Two-Sample Tests [50.92621794426821]
We propose a class of kernel-based two-sample tests, which aim to determine whether two sets of samples are drawn from the same distribution.
Our tests are constructed from kernels parameterized by deep neural nets, trained to maximize test power.
arXiv Detail & Related papers (2020-02-21T03:54:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.