mlsanityData to 14 Oct 2026

Efficient Aggregated Kernel Tests using Incomplete U-statistics

arXiv 2206.09194 ↗First posted 18 Jun 2022stat.ML cs.LG math.STcited by 27

Not on the map. Why?

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.

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

31 of 95 references.

References · 31

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Density estimation using Real NVPcited by 2,042
  3. 2018Glow: Generative Flow with Invertible 1x1 Convolutionscited by 1,545
  4. 2016A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluationcited by 236
  5. 2016A Kernel Test of Goodness of Fitcited by 143
  6. 2017Measuring Sample Quality with Kernelscited by 119
  7. 2016Generative Models and Model Criticism via Optimized Maximum Mean Discrepancycited by 100
  8. 2013Exact post-selection inference, with application to the lassocited by 91
  9. 2021MMD Aggregated Two-Sample Testcited by 75
  10. 2014Optimal Inference After Model Selectioncited by 67
  11. 2016Interpretable Distribution Features with Maximum Testing Powercited by 63
  12. 2015Fast Two-Sample Testing with Analytic Representations of Probability Measurescited by 53
19 more
  1. 2017A Linear-Time Kernel Goodness-of-Fit Testcited by 41
  2. 2016Large-Scale Kernel Methods for Independence Testingcited by 32
  3. 2014A Wild Bootstrap for Degenerate Kernel Testscited by 29
  4. 2018Random Feature Stein Discrepanciescited by 23
  5. 2021A Witness Two-Sample Testcited by 23
  6. 2019On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alternativescited by 21
  7. 2022KSD Aggregated Goodness-of-fit Testcited by 21
  8. 2017On the Optimality of Kernel-Embedding Based Goodness-of-Fit Testscited by 19
  9. 2020Learning Kernel Tests Without Data Splittingcited by 19
  10. 2014FastMMD: Ensemble of Circular Discrepancy for Efficient Two-Sample Testcited by 17
  11. 2021Composite Goodness-of-fit Tests with Kernelscited by 16
  12. 2016Post Selection Inference with Kernelscited by 13
  13. 2016An Adaptive Test of Independence with Analytic Kernel Embeddingscited by 13
  14. 2018Post Selection Inference with Incomplete Maximum Mean Discrepancy Estimatorcited by 11
  15. 2015A simpler condition for consistency of a kernel independence testcited by 10
  16. 2019Kernel Stein Tests for Multiple Model Comparisoncited by 9
  17. 2019More Powerful Selective Kernel Tests for Feature Selectioncited by 6
  18. 2020Optimal rates for independence testing via U-statistic permutation testscited by 5
  19. 2020Post-selection inference with HSIC-Lassocited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 4; 2025: 11; 2026: 2.

27 papers.

Sort:

By area:

  1. 2023MMD-FUSE: Learning and Combining Kernels for Two-Sample Testing Without Data Splittingcited by 33
  2. 2024Practical Kernel Tests of Conditional Independencecited by 15
  3. 2022Subspace Recovery from Heterogeneous Data with Non-isotropic Noisecited by 14
  4. 2023Compress Then Test: Powerful Kernel Testing in Near-linear Timecited by 14
  5. 2025A Practical Introduction to Kernel Discrepancies: MMD, HSIC & KSDcited by 13
  6. 2023A Bias-Variance-Covariance Decomposition of Kernel Scores for Generative Modelscited by 8
  7. 2023Variable Selection for Kernel Two-Sample Testscited by 7
  8. 2024Robust Kernel Hypothesis Testing under Data Corruptioncited by 7
  9. 2025A Scalable Nystrom-Based Kernel Two-Sample Test with Permutationscited by 6
  10. 2025DUAL: Learning Diverse Kernels for Aggregated Two-sample and Independence Testingcited by 6
  11. 2023Nystr"om M-Hilbert-Schmidt Independence Criterioncited by 5
  12. 2025A Unified View of Optimal Kernel Hypothesis Testingcited by 5
15 more
  1. 2024Statistical and Computational Guarantees of Kernel Max-Sliced Wasserstein Distancescited by 4
  2. 2024Nystr"om Kernel Stein Discrepancycited by 4
  3. 2023A Semi-Bayesian Nonparametric Estimator of the Maximum Mean Discrepancy Measure: Applications in Goodness-of-Fit Testing and Generative Adversarial Networkscited by 3
  4. 2022A general framework for the analysis of kernel-based testscited by 2
  5. 2025Optimal Online Change Detection via Random Fourier Featurescited by 2
  6. 2026Regularized f-Divergence Kernel Testscited by 2
  7. 2025Prior shift estimation for positive unlabeled data through the lens of kernel embeddingcited by 1
  8. 2025Beyond Basic A/B testing: Improving Statistical Efficiency for Business Growthcited by 1
  9. 2025Anchor-based Maximum Discrepancy for Relative Similarity Testingcited by 1
  10. 2025Kernel-Based Evaluation of Conditional Biological Sequence Modelscited by 1
  11. 2022Discussion of `Multiscale Fisher's Independence Test for Multivariate Dependence'cited by 0
  12. 2023Partial identification of kernel based two sample tests with mismeasured datacited by 0
  13. 2025Kernel Quantile Embeddings and Associated Probability Metricscited by 0
  14. 2025Are Two Datasets Close Enough With Statistical Significance? A Kernel Distributional Closeness Testing Approachcited by 0
  15. 2026USAD: Uncertainty-aware Statistical Adversarial Detectioncited by 0