A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911606540075008 |
|---|---|
| author | Chatalic, Antoine Letizia, Marco Schreuder, Nicolas Rosasco, Lorenzo |
| author_facet | Chatalic, Antoine Letizia, Marco Schreuder, Nicolas Rosasco, Lorenzo |
| contents | Two-sample hypothesis testing-determining whether two sets of data are drawn from the same distribution-is a fundamental problem in statistics and machine learning with broad scientific applications. In the context of nonparametric testing, maximum mean discrepancy (MMD) has gained popularity as a test statistic due to its flexibility and strong theoretical foundations. However, its use in large-scale scenarios is plagued by high computational costs. In this work, we use a Nyström approximation of the MMD to design a computationally efficient and practical testing algorithm while preserving statistical guarantees. Our main result is a finite-sample bound on the power of the proposed test for distributions that are sufficiently separated with respect to the MMD. The derived separation rate matches the known minimax optimal rate in this setting. We support our findings with a series of numerical experiments, emphasizing applicability to realistic scientific data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_13570 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations Chatalic, Antoine Letizia, Marco Schreuder, Nicolas Rosasco, Lorenzo Machine Learning Statistics Theory Methodology Two-sample hypothesis testing-determining whether two sets of data are drawn from the same distribution-is a fundamental problem in statistics and machine learning with broad scientific applications. In the context of nonparametric testing, maximum mean discrepancy (MMD) has gained popularity as a test statistic due to its flexibility and strong theoretical foundations. However, its use in large-scale scenarios is plagued by high computational costs. In this work, we use a Nyström approximation of the MMD to design a computationally efficient and practical testing algorithm while preserving statistical guarantees. Our main result is a finite-sample bound on the power of the proposed test for distributions that are sufficiently separated with respect to the MMD. The derived separation rate matches the known minimax optimal rate in this setting. We support our findings with a series of numerical experiments, emphasizing applicability to realistic scientific data. |
| title | A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations |
| topic | Machine Learning Statistics Theory Methodology |
| url | https://arxiv.org/abs/2502.13570 |