# Efficient Aggregated Kernel Tests using Incomplete U-statistics

arXiv: https://arxiv.org/abs/2206.09194 · HTML: https://mlsanity.com/paper/2206.09194/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 95 references that are in the map.
- First posted on arXiv 18 Jun 2022.

## Builds on (most cited first, 30 of 31)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Density estimation using Real NVP](https://mlsanity.com/paper/1605.08803/) (2016)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [Measuring Sample Quality with Kernels](https://mlsanity.com/paper/1703.01717/) (2017)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [Exact post-selection inference, with application to the lasso](https://mlsanity.com/paper/1311.6238/) (2013)
- [MMD Aggregated Two-Sample Test](https://mlsanity.com/paper/2110.15073/) (2021)
- [Optimal Inference After Model Selection](https://mlsanity.com/paper/1410.2597/) (2014)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Fast Two-Sample Testing with Analytic Representations of Probability Measures](https://mlsanity.com/paper/1506.04725/) (2015)
- [A Linear-Time Kernel Goodness-of-Fit Test](https://mlsanity.com/paper/1705.07673/) (2017)
- [Large-Scale Kernel Methods for Independence Testing](https://mlsanity.com/paper/1606.07892/) (2016)
- [A Wild Bootstrap for Degenerate Kernel Tests](https://mlsanity.com/paper/1408.5404/) (2014)
- [Random Feature Stein Discrepancies](https://mlsanity.com/paper/1806.07788/) (2018)
- [A Witness Two-Sample Test](https://mlsanity.com/paper/2102.05573/) (2021)
- [On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alternatives](https://mlsanity.com/paper/1909.03302/) (2019)
- [KSD Aggregated Goodness-of-fit Test](https://mlsanity.com/paper/2202.00824/) (2022)
- [On the Optimality of Kernel-Embedding Based Goodness-of-Fit Tests](https://mlsanity.com/paper/1709.08148/) (2017)
- [Learning Kernel Tests Without Data Splitting](https://mlsanity.com/paper/2006.02286/) (2020)
- [FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Test](https://mlsanity.com/paper/1405.2664/) (2014)
- [Composite Goodness-of-fit Tests with Kernels](https://mlsanity.com/paper/2111.10275/) (2021)
- [Post Selection Inference with Kernels](https://mlsanity.com/paper/1610.03725/) (2016)
- [An Adaptive Test of Independence with Analytic Kernel Embeddings](https://mlsanity.com/paper/1610.04782/) (2016)
- [Post Selection Inference with Incomplete Maximum Mean Discrepancy Estimator](https://mlsanity.com/paper/1802.06226/) (2018)
- [A simpler condition for consistency of a kernel independence test](https://mlsanity.com/paper/1501.06103/) (2015)
- [Kernel Stein Tests for Multiple Model Comparison](https://mlsanity.com/paper/1910.12252/) (2019)
- [More Powerful Selective Kernel Tests for Feature Selection](https://mlsanity.com/paper/1910.06134/) (2019)
- [Optimal rates for independence testing via U-statistic permutation tests](https://mlsanity.com/paper/2001.05513/) (2020)

## Built on by (most cited first, 27 of 27)

- [MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splitting](https://mlsanity.com/paper/2306.08777/) (2023)
- [Practical Kernel Tests of Conditional Independence](https://mlsanity.com/paper/2402.13196/) (2024)
- [Subspace Recovery from Heterogeneous Data with Non-isotropic Noise](https://mlsanity.com/paper/2210.13497/) (2022)
- [Compress Then Test: Powerful Kernel Testing in Near-linear Time](https://mlsanity.com/paper/2301.05974/) (2023)
- [A Practical Introduction to Kernel Discrepancies: MMD, HSIC & KSD](https://mlsanity.com/paper/2503.04820/) (2025)
- [A Bias-Variance-Covariance Decomposition of Kernel Scores for Generative Models](https://mlsanity.com/paper/2310.05833/) (2023)
- [Variable Selection for Kernel Two-Sample Tests](https://mlsanity.com/paper/2302.07415/) (2023)
- [Robust Kernel Hypothesis Testing under Data Corruption](https://mlsanity.com/paper/2405.19912/) (2024)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [DUAL: Learning Diverse Kernels for Aggregated Two-sample and Independence Testing](https://mlsanity.com/paper/2510.11140/) (2025)
- [Nystr"om M-Hilbert-Schmidt Independence Criterion](https://mlsanity.com/paper/2302.09930/) (2023)
- [A Unified View of Optimal Kernel Hypothesis Testing](https://mlsanity.com/paper/2503.07084/) (2025)
- [Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distances](https://mlsanity.com/paper/2405.15441/) (2024)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [A Semi-Bayesian Nonparametric Estimator of the Maximum Mean Discrepancy Measure: Applications in Goodness-of-Fit Testing and Generative Adversarial Networks](https://mlsanity.com/paper/2303.02637/) (2023)
- [A general framework for the analysis of kernel-based tests](https://mlsanity.com/paper/2209.00124/) (2022)
- [Optimal Online Change Detection via Random Fourier Features](https://mlsanity.com/paper/2505.17789/) (2025)
- [Regularized f-Divergence Kernel Tests](https://mlsanity.com/paper/2601.19755/) (2026)
- [Prior shift estimation for positive unlabeled data through the lens of kernel embedding](https://mlsanity.com/paper/2502.21194/) (2025)
- [Beyond Basic A/B testing: Improving Statistical Efficiency for Business Growth](https://mlsanity.com/paper/2505.08128/) (2025)
- [Anchor-based Maximum Discrepancy for Relative Similarity Testing](https://mlsanity.com/paper/2510.10477/) (2025)
- [Kernel-Based Evaluation of Conditional Biological Sequence Models](https://mlsanity.com/paper/2510.15601/) (2025)
- [Discussion of `Multiscale Fisher's Independence Test for Multivariate Dependence'](https://mlsanity.com/paper/2206.11142/) (2022)
- [Partial identification of kernel based two sample tests with mismeasured data](https://mlsanity.com/paper/2308.03570/) (2023)
- [Kernel Quantile Embeddings and Associated Probability Metrics](https://mlsanity.com/paper/2505.20433/) (2025)
- [Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approach](https://mlsanity.com/paper/2507.12843/) (2025)
- [USAD: Uncertainty-aware Statistical Adversarial Detection](https://mlsanity.com/paper/2606.27832/) (2026)

## Abstract (arXiv)

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 the more widespread permutation-based approach, 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, the linear-time versions of our proposed tests perform at least as well as the current linear-time state-of-the-art tests.