Kernel Two-Sample Tests in High Dimension: Interplay Between Moment
Discrepancy and Dimension-and-Sample Orders
- URL: http://arxiv.org/abs/2201.00073v1
- Date: Fri, 31 Dec 2021 23:12:44 GMT
- Title: Kernel Two-Sample Tests in High Dimension: Interplay Between Moment
Discrepancy and Dimension-and-Sample Orders
- Authors: Jian Yan, Xianyang Zhang
- Abstract summary: 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.
- Score: 1.104121146441257
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by the increasing use of kernel-based metrics for high-dimensional
and large-scale data, we study the asymptotic behavior of kernel two-sample
tests when the dimension and sample sizes both diverge to infinity. We focus on
the maximum mean discrepancy (MMD) with the kernel of the form
$k(x,y)=f(\|x-y\|_{2}^{2}/\gamma)$, including MMD with the Gaussian kernel and
the Laplacian kernel, and the energy distance as special cases. We derive
asymptotic expansions of the kernel two-sample statistics, based on which we
establish the central limit theorem (CLT) under both the null hypothesis and
the local and fixed alternatives. The new non-null CLT results allow us to
perform asymptotic exact power analysis, which reveals a delicate interplay
between the moment discrepancy that can be detected by the kernel two-sample
tests and the dimension-and-sample orders. The asymptotic theory is further
corroborated through numerical studies. Our findings complement those in the
recent literature and shed new light on the use of kernel two-sample tests for
high-dimensional and large-scale data.
Related papers
- Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks.
In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
arXiv Detail & Related papers (2024-04-29T15:04:07Z) - 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) - A High-dimensional Convergence Theorem for U-statistics with
Applications to Kernel-based Testing [3.469038201881982]
We prove a convergence theorem for U-statistics of degree two, where the data dimension $d$ is allowed to scale with sample size $n$.
We apply our theory to two popular kernel-based distribution tests, MMD and KSD, whose high-dimensional performance has been challenging to study.
arXiv Detail & Related papers (2023-02-11T12:49:46Z) - Targeted Separation and Convergence with Kernel Discrepancies [66.48817218787006]
kernel-based discrepancy measures are required to (i) separate a target P from other probability measures or (ii) control weak convergence to P.
In this article we derive new sufficient and necessary conditions to ensure (i) and (ii)
For MMDs on separable metric spaces, we characterize those kernels that separate Bochner embeddable measures and introduce simple conditions for separating all measures with unbounded kernels.
arXiv Detail & Related papers (2022-09-26T16:41:16Z) - How do kernel-based sensor fusion algorithms behave under high
dimensional noise? [9.13755431537592]
We study the behavior of two kernel based sensor fusion algorithms, NCCA and alternating diffusion (AD)
We show that if NCCA and AD are directly applied to the noisy point clouds without any sanity check, it may generate artificial information that misleads scientists' interpretation.
On the other hand, we prove that if the bandwidths are selected adequately, both NCCA and AD can be made robust to high dimensional noise when the SNRs are relatively large.
arXiv Detail & Related papers (2021-11-22T01:42:28Z) - MMD Aggregated Two-Sample Test [31.116276769013204]
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.
arXiv Detail & Related papers (2021-10-28T12:47:49Z) - A Note on Optimizing Distributions using Kernel Mean Embeddings [94.96262888797257]
Kernel mean embeddings represent probability measures by their infinite-dimensional mean embeddings in a reproducing kernel Hilbert space.
We show that when the kernel is characteristic, distributions with a kernel sum-of-squares density are dense.
We provide algorithms to optimize such distributions in the finite-sample setting.
arXiv Detail & Related papers (2021-06-18T08:33:45Z) - Isolation Distributional Kernel: A New Tool for Point & Group Anomaly
Detection [76.1522587605852]
Isolation Distributional Kernel (IDK) is a new way to measure the similarity between two distributions.
We demonstrate IDK's efficacy and efficiency as a new tool for kernel based anomaly detection for both point and group anomalies.
arXiv Detail & Related papers (2020-09-24T12:25:43Z) - A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian
Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
This article characterizes the exacts of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples $n$ is all large and comparable.
This analysis also provides accurate estimates of training and test regression errors for large $n,p,N$.
arXiv Detail & Related papers (2020-06-09T02:05:40Z) - 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.