pith. sign in

arxiv: 2502.13570 · v4 · submitted 2025-02-19 · 📊 stat.ML · cs.LG· math.ST· stat.ME· stat.TH

A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations

Antoine Chatalic , Marco Letizia , Nicolas Schreuder , Lorenzo Rosasco This is my paper

Pith reviewed 2026-05-23 02:35 UTC · model grok-4.3

classification 📊 stat.ML cs.LGmath.STstat.MEstat.TH
keywords Nyström approximationmaximum mean discrepancytwo-sample testingkernel methodspermutation testminimax separation ratescalable nonparametric statistics
0
0 comments X

The pith

Nyström approximation of the MMD yields a scalable two-sample test whose power bound matches the minimax optimal separation rate.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a computationally efficient two-sample test by replacing the full kernel matrix in the maximum mean discrepancy statistic with a Nyström low-rank approximation. Permutation testing is retained to obtain valid p-values. The central theoretical result supplies a finite-sample power guarantee that holds whenever the two distributions are separated by at least the known minimax rate with respect to the true MMD. Because the separation threshold is identical to the rate achieved by the exact statistic, the approximation does not degrade statistical performance at the optimal scale. Experiments on realistic data sets confirm that the procedure remains practical for sample sizes where the full MMD is prohibitive.

Core claim

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.

What carries the argument

Nyström low-rank approximation of the MMD statistic inside a permutation test that preserves exact type-I error control.

If this is right

  • The test can be run on data sets whose size makes the full kernel matrix intractable while retaining the optimal detection threshold.
  • Permutation-based calibration continues to deliver exact finite-sample type-I error control under the null.
  • Any kernel for which the MMD is well-defined can be paired with the same Nyström-plus-permutation pipeline.
  • The method directly extends existing MMD software to large-scale scientific applications without altering the theoretical separation rate.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Landmark-selection heuristics that adapt to the observed data scale become necessary to guarantee the error term stays below the separation distance in practice.
  • The same approximation strategy may transfer to related kernel tests such as independence testing or goodness-of-fit without losing minimax rates.
  • Random-feature or sparse-approximation variants could be substituted for Nyström while preserving the power bound if their error terms satisfy the same scaling.
  • The finite-sample analysis supplies a concrete yardstick for choosing the number of landmarks as a function of sample size and kernel bandwidth.

Load-bearing premise

The Nyström approximation error must stay small enough that the approximated statistic still distinguishes distributions separated at the minimax rate.

What would settle it

An experiment in which two distributions separated exactly at the minimax MMD rate are not detected by the test when the number of Nyström landmarks is held fixed below the threshold required by the error bound.

Figures

Figures reproduced from arXiv: 2502.13570 by Antoine Chatalic, Lorenzo Rosasco, Marco Letizia, Nicolas Schreuder.

Figure 1
Figure 1. Figure 1: Correlated Gaussians. Left: power against computation time (ρ2 = 0.63). The number of features ℓ is varied between 14 and 1500. We used CTT with compression levels g = 0, 1, 2, 3, 4. Right: power against ρ2. 10 1 10 0 10 1 Computation time (s) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Power Nyström-uniform (ours) Nyström-AKRLS (ours) RFF CTT 0 20000 40000 60000 80000 n 0.0 0.2 0.4 0.6 0.8 1.0 Power Nyström-uniform (… view at source ↗
Figure 2
Figure 2. Figure 2: Susy. Left: power against computation time (n = 24000). The number of features ℓ is varied between 30 and 1540. We used CTT with compression levels g = 0, 1, 2, 3, 4. Right: power against sample size. 10 1 10 0 10 1 Computation time (s) 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Power Nyström-uniform (ours) Nyström-AKRLS (ours) RFF CTT 0 20000 40000 60000 80000 100000 n 0.0 0.2 0.4 0.6 0.8 1.0 Power Nyström-uniform (… view at source ↗
Figure 3
Figure 3. Figure 3: Higgs. Left: power against computation time (n = 40000). The number of features ℓ is varied between 40 and 1000. We used CTT with compression levels g = 0, 1, 2, 3, 4. Right: power against sample size. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Comparison with exact MMD. 10 2 0.65 0.70 0.75 0.80 0.85 0.90 Power Nyström-uniform (ours) Nyström-AKRLS (ours) RFF (a) Correlated Gaussians, ρ2 = 0.63 10 2 0.60 0.65 0.70 0.75 0.80 0.85 Power Nyström-uniform (ours) Nyström-AKRLS (ours) RFF (b) Susy, n = 24000 10 2 10 3 0.60 0.65 0.70 0.75 0.80 Power Nyström-uniform (ours) Nyström-AKRLS (ours) RFF (c) Higgs, n = 40000 [PITH_FULL_IMAGE:figures/full_fig_p01… view at source ↗
Figure 5
Figure 5. Figure 5: Power against number of features. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Rate of type-I errors against sample size. The number of features [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
read the original abstract

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\"om 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper proposes a Nyström-approximated MMD statistic for scalable two-sample testing, computes p-values via permutations, and states a finite-sample power bound whose separation rate matches the known minimax rate for MMD testing; numerical experiments are mentioned to support applicability to scientific data.

Significance. If the power bound is rigorously established while controlling the Nyström error, the result would be significant: it would deliver a computationally efficient nonparametric test whose statistical power is provably optimal (matching the minimax rate) rather than merely consistent. The permutation mechanism for exact type-I control is a clear strength. The significance is currently limited by the absence of an explicit error-control argument linking the approximation to the claimed rate.

major comments (2)
  1. [Main theoretical result / power bound] Theoretical result on power (the main theorem asserting the minimax-matching separation rate): the bound is stated for the Nyström-approximated statistic, yet no derivation or lemma shows that the approximation bias/variance term is o(separation radius). Without an explicit scaling requirement on the number of landmarks m(n) (or a landmark-selection rule guaranteeing operator-norm error smaller than the separation), the optimality claim cannot be verified.
  2. [Nyström approximation and algorithm] Nyström approximation section (definition of the approximated kernel matrix and landmark selection): the method description does not specify how m is chosen relative to n or how landmarks are sampled to ensure the required approximation quality; this choice is load-bearing for the central power claim.
minor comments (1)
  1. [Abstract] Abstract: the claim of 'a series of numerical experiments' is made without any indication of the sample sizes, landmark counts, or performance metrics used; this should be expanded for clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments, which highlight important aspects of the theoretical analysis. We address each major comment below and will revise the manuscript accordingly to provide the requested explicit error controls.

read point-by-point responses

  1. Referee: [Main theoretical result / power bound] Theoretical result on power (the main theorem asserting the minimax-matching separation rate): the bound is stated for the Nyström-approximated statistic, yet no derivation or lemma shows that the approximation bias/variance term is o(separation radius). Without an explicit scaling requirement on the number of landmarks m(n) (or a landmark-selection rule guaranteeing operator-norm error smaller than the separation), the optimality claim cannot be verified.

    Authors: We agree that an explicit argument is required to show the Nyström error is negligible relative to the separation radius. In the revised manuscript we will insert a new lemma bounding the operator-norm difference between the exact and approximated kernel matrices (and the resulting MMD statistics). The lemma will also state the minimal scaling m(n) (under standard random landmark sampling) that makes the approximation error o(separation radius), thereby confirming that the stated finite-sample power bound continues to hold for the Nyström statistic at the minimax rate. revision: yes

  2. Referee: [Nyström approximation and algorithm] Nyström approximation section (definition of the approximated kernel matrix and landmark selection): the method description does not specify how m is chosen relative to n or how landmarks are sampled to ensure the required approximation quality; this choice is load-bearing for the central power claim.

    Authors: We acknowledge that the current algorithmic description leaves the dependence of m on n and the landmark-sampling procedure implicit. The revision will add a dedicated paragraph (and pseudocode) specifying both the sampling method (uniform random selection of landmarks) and the concrete scaling m(n) derived from the new lemma, so that the approximation quality required by the power bound is explicitly guaranteed. revision: yes

Circularity Check

0 steps flagged

No circularity: power bound derived from standard MMD concentration plus Nyström operator approximation under explicit error control

full rationale

The paper's central result is a finite-sample power bound whose separation rate is shown to match the known minimax rate for exact MMD two-sample testing. This requires proving that the Nyström-induced perturbation remains o(separation radius), which is a standard perturbation argument once landmark count m and sampling method are fixed; the derivation therefore rests on external concentration inequalities and operator-norm bounds rather than redefining the target quantity in terms of itself or importing the optimality claim via self-citation. No step reduces the claimed rate to a fitted parameter or to a prior result whose only justification is the present authors' earlier work.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no concrete free parameters, axioms, or invented entities; the work rests on standard kernel and approximation-theory background whose details are not visible here.

pith-pipeline@v0.9.0 · 5689 in / 1211 out tokens · 35434 ms · 2026-05-23T02:35:18.275437+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. DriftXpress: Faster Drifting Models via Projected RKHS Fields

    cs.LG 2026-05 unverdicted novelty 7.0

    DriftXpress approximates drifting kernels via projected RKHS fields to lower training cost of one-step generative models while matching original FID scores.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Fast Randomized Kernel Ridge Regression with Statistical Guarantees

    Alaoui, Ahmed and Michael W. Mahoney (2015). “Fast Randomized Kernel Ridge Regression with Statistical Guarantees”. In:Advances in Neural Information Processing Systems, pp. 775–783. Alaoui, Ahmed El and Michael W. Mahoney (2014). “Fast Randomized Kernel Methods with Statistical Guarantees”. In:stat1050, p

    work page 2015

  2. [2]

    CaloChallenge 2022: A Community Challenge for Fast Calorimeter Simula- tion

    Amram, Oz et al. (2024). “CaloChallenge 2022: A Community Challenge for Fast Calorimeter Simula- tion”. In: ed. by Claudius Krause, Michele Faucci Giannelli, Gregor Kasieczka, Benjamin Nachman, Dalila Salamani, David Shih, and Anna Zaborowska. arXiv:2410.21611 [physics.ins-det]. Balasubramanian, Krishnakumar, Tong Li, and Ming Yuan (2021). “On the Optimal...

    work page arXiv 2024

  3. [3]

    Searching for Exotic Particles in High- Energy Physics with Deep Learning

    Baldi, Pierre, Peter Sadowski, and Daniel Whiteson (2014). “Searching for Exotic Particles in High- Energy Physics with Deep Learning”. In:Nature Commun.5, p

    work page 2014

  4. [4]

    Searching for Exotic Particles in High-Energy Physics with Deep Learning

    arXiv:1402.4735 [hep-ph]. Baraud, Yannick (2002). “Non-asymptotic minimax rates of testing in signal detection”. In:Bernoulli 8.5, pp. 577 –606. Berlinet, Alain and Christine Thomas-Agnan (2004).Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer.isbn: 978-1-4419-9096-9. Biggs, Felix, Antonin Schrab, and Arthur Gretton (2023).MMD-FUS...

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  5. [5]

    Computational-Statistical Trade-off in Kernel Two-Sample Testing with Random Fourier Features

    Proceedings of Machine Learning Research. PMLR, pp. 3006–3024. Chen, Yifan and Yun Yang (2021). “Fast Statistical Leverage Score Approximation in Kernel Ridge Regression”. In:Proceedings of The 24th International Conference on Artificial Intelligence and Statistics. International Conference on Artificial Intelligence and Statistics. PMLR, pp. 2935–2943. C...

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  6. [6]

    Diestel, Joseph and John Jerry Uhl (1977).Vector Measures

    arXiv:1912.12155 [hep-ph]. Diestel, Joseph and John Jerry Uhl (1977).Vector Measures. Mathematical Surveys and Monographs

    work page arXiv 1912

  7. [7]

    Nystr¨ om Landmark Sampling and Regularized Christoffel Functions

    American Mathematical Soc.isbn: 0-8218-1515-6 978-0-8218-1515-1. 31 Domingo-Enrich, Carles, Raaz Dwivedi, and Lester Mackey (2023).Compress Then Test: Powerful Kernel Testing in Near-linear Time. arXiv:2301.05974 [cs, math, stat].url:http://arxiv. org/abs/2301.05974. Pre-published. Fanuel, Micha¨ el, Joachim Schreurs, and Johan A. K. Suykens (2022). “Nyst...

    work page arXiv 2023

  8. [8]

    Refereeing the Referees: Evaluating Two- Sample Tests for Validating Generators in Precision Sciences

    Grossi, Samuele, Marco Letizia, and Riccardo Torre (2024). “Refereeing the Referees: Evaluating Two- Sample Tests for Validating Generators in Precision Sciences”. In: arXiv:2409.16336 [stat.ML]. Hagrass, Omar, Bharath K. Sriperumbudur, and Bing Li (2023).Spectral Regularized Kernel Two- Sample Tests. arXiv:2212.09201 [cs, math, stat].url:http://arxiv.org...

    work page arXiv 2024

  9. [9]

    Exact Testing with Random Permutations

    Pre-published. Hemerik, Jesse and Jelle Goeman (2018). “Exact Testing with Random Permutations”. In:TEST27.4, pp. 811–825.issn: 1133-0686, 1863-8260. Hoeffding, Wassily (1952). “The large-sample power of tests based on permutations of observations”. In:The Collected Works of Wassily Hoeffding. Springer, pp. 247–271. Huggins, Jonathan and Lester Mackey (20...

    work page 2018

  10. [10]

    Inter- pretable Distribution Features with Maximum Testing Power

    Curran Associates, Inc. Jitkrittum, Wittawat, Zolt´ an Szab´ o, Kacper P Chwialkowski, and Arthur Gretton (2016). “Inter- pretable Distribution Features with Maximum Testing Power”. In:Advances in Neural Information Processing Systems. Vol

    work page 2016

  11. [11]

    F -Divergence Estimation and Two- Sample Homogeneity Test Under Semiparametric Density-Ratio Models

    Curran Associates, Inc. Kalinke, Florian, Zoltan Szabo, and Bharath K. Sriperumbudur (2024).Nystr¨ om Kernel Stein Dis- crepancy. arXiv:2406 . 08401 [cs, math, stat].url:http : / / arxiv . org / abs / 2406 . 08401. Pre-published. Kanamori, Takafumi, Taiji Suzuki, and Masashi Sugiyama (2011). “F -Divergence Estimation and Two- Sample Homogeneity Test Under...

    work page arXiv 2024

  12. [12]

    On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alter- natives

    arXiv:2204.02317 [hep-ph]. Li, Tong and Ming Yuan (2019).On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alternatives. arXiv:1909.03302 [math, stat].url:http://arxiv.org/abs/ 1909.03302. Pre-published. — (2024). “On the Optimality of Gaussian Kernel Based Nonparametric Tests against Smooth Alter- natives”. In:Journal of Machi...

    work page arXiv 2019

  13. [13]

    MMD Aggregated Two-Sample Test

    NIPS’15. Cambridge, MA, USA: MIT Press, pp. 1657–1665. Schrab, Antonin, Ilmun Kim, M´ elisande Albert, B´ eatrice Laurent, Benjamin Guedj, and Arthur Gretton (2023). “MMD Aggregated Two-Sample Test”. In:Journal of Machine Learning Research24.194, pp. 1–81.issn: 1533-7928. Schrab, Antonin, Ilmun Kim, Benjamin Guedj, and Arthur Gretton (2022). “Efficient Ag...

    work page 2023

  14. [14]

    Bayesian Kernel Two-Sample Testing

    Curran Associates, Inc. Zhang, Qinyi, Veit Wild, Sarah Filippi, Seth Flaxman, and Dino Sejdinovic (2022). “Bayesian Kernel Two-Sample Testing”. In:Journal of Computational and Graphical Statistics31.4, pp. 1164–1176. issn: 1061-8600. Zhao, Ji and Deyu Meng (2015). “FastMMD: Ensemble of Circular Discrepancy for Efficient Two- Sample Test”. In:Neural Comput...

    work page 2022