Schrab, Antonin;
Kim, Ilmun;
Guedj, Benjamin;
Gretton, Arthur;
(2022)
Efficient Aggregated Kernel Tests using Incomplete U-statistics.
In:
NeurIPS Proceedings: Advances in Neural Information Processing Systems 35 (NeurIPS 2022).
NeurIPS
Preview |
Text
2643_efficient_aggregated_kernel_te.pdf - Accepted Version Download (1MB) | Preview |
Abstract
We propose a series of computationally efficient, nonparametric tests for the two-sample, independence and goodness-of-fit problems, using the Maximum Mean Discrepancy (MMD), Hilbert Schmidt Independence Criterion (HSIC), and Kernel Stein Discrepancy (KSD), respectively. Our test statistics are incomplete U -statistics, with a computational cost that interpolates between linear time in the number of samples, and quadratic time, as associated with classical U -statistic tests. The three proposed tests aggregate over several kernel bandwidths to detect departures from the null on various scales: we call the resulting tests MMDAggInc, HSICAggInc and KSDAggInc. This procedure provides a solution to the fundamental kernel selection problem as we can aggregate a large number of kernels with several bandwidths without incurring a significant loss of test power. For the test thresholds, we derive a quantile bound for wild bootstrapped incomplete U -statistics, which is of independent interest. We derive non-asymptotic uniform separation rates for MMDAggInc and HSICAggInc, and quantify exactly the trade-off between computational efficiency and the attainable rates: this result is novel for tests based on incomplete U -statistics, to our knowledge. We further show that in the quadratic-time case, the wild bootstrap incurs no penalty to test power over more widespread permutation-based approaches, since both attain the same minimax optimal rates (which in turn match the rates that use oracle quantiles). We support our claims with numerical experiments on the trade-off between computational efficiency and test power. In all three testing frameworks, our proposed linear-time tests outperform the current linear-time state-of-the-art tests (or at least match their test power).
| Type: | Proceedings paper |
|---|---|
| Title: | Efficient Aggregated Kernel Tests using Incomplete U-statistics |
| Event: | Thirty-Sixth Conference on Neural Information Processing Systems |
| Dates: | 28 Nov 2022 - 9 Dec 2022 |
| ISBN-13: | 9781713871088 |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://proceedings.neurips.cc/paper_files/paper/2... |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Life Sciences > Gatsby Computational Neurosci Unit |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10166322 |
Archive Staff Only
 |
View Item |
