REVIEW 2 major objections 5 minor 1 cited by
Cheap Permutation Testing
T0 review · 2 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read This paper claims that permutation tests can be made nearly free by permuting pre-computed bins of data points: each bin-permuted statistic costs time independent of the sample size, while the test keeps exact level control, power close…
desk verdict The paper has a genuinely promising idea and a lot of careful work, but as written the power theorems do not apply to the algorithm they implement: the proofs analyze a bin-level statistic that is not shown to equal the statistic computed in Alg. 1. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Two devices carry the argument. The first is bin-level sufficient statistics: for a homogeneity quadratic test statistic, the $3s^2$ block sums $\Phi^w_{ij} = \sum_{a\in I_i}\sum_{b\in I_j} \phi_w(X_a, X_b)$ for $w \in \{n_1, n_2, (n_1,n_2)\}$, so every bin-permuted statistic is a quadratic form in these blocks; for an independence V-statistic, the $s^2/2$ aggregated terms $(D_{ii}, D_{i(i+s/2)})$ and $(S_{ij\cdot})$ built from centered kernel products play the same role. These reduce the per-permutation cost from $\Theta(Bn^2)$ to $\Theta(Bs^2)$ with $\Theta(s^2)$ memory, after a one-time $\Theta(c_\phi n^2)$ or $\Theta(c_g n^2)$ precomputation. The second is the quantile comparison method, a two-moment argument that bounds the test statistic's fluctuations around its mean and the permutation threshold's conditional quantile using only $B \geq 1/\alpha - 1$ permutations, and whose refinement needs only variance components; these variance components are exactly what the power theorems evaluate for binned and unbinned U- and V-statistics.
What would settle it
Take a small instance (for example $s=4$, $n_1=n_2=8$) with a fixed kernel $g$, enumerate all $s!$ bin permutations, and compute the full permutation distribution of the statistic produced by Algorithm 1; compare its level-$\alpha$ acceptance region and rejection probability against the distribution of the binned U/V-statistic analyzed in the proofs—any mismatch in rejection probability would show the implemented and analyzed statistics differ. A second check uses $n$ not divisible by $s$ (e.g., $n=10$, $s=4$): simulate the claimed exact $\alpha$ level and the theorem's predicted power threshold to see whether the equal-bin assumption is genuinely load-bearing.
Extended reading notes
Core claim
The central discovery is that a binned permutation test is both cheap and statistically equivalent to the standard test in the senses that matter. For a homogeneity quadratic test statistic or an independence V-statistic, permuting $s$ bins instead of $n$ points yields an exact level-$\alpha$ test, with each permuted statistic computable in $\Theta(s^2)$ elementary operations once $O(n^2)$ sufficient statistics are precomputed. For power, the separation thresholds for cheap tests are $\Theta$ of the standard thresholds—$\gamma_{n_1,n_2,s} = \Theta(\gamma_{n_1,n_2})$ for homogeneity when $s \geq \sqrt[3]{24(1-\alpha^\star)/(\beta\alpha^\star \rho_{n_1n_2})}$, and $\gamma_{n,s} = \Theta(\gamma_n)$ for independence for any $s$—with asymptotic equivalence (ratio tending to $1$) as soon as $s$ grows, and these thresholds feed minimax-optimality results for discrete and H\"older $L_2$ homogeneity and independence. The analysis is carried by a new quantile comparison method that controls permutation-test power using only $B \geq 1/\alpha - 1$ permutations, which also improves the guarantees for standard permutation tests.
Load-bearing premise
The whole edifice rests on clean bin geometry: the analysis assumes $n$ is divisible by $s$, that $s_1 = s n_1/n$ is an integer, and that the binned statistic studied in the proofs is exactly the statistic that the algorithms compute; when one of these fails, the equal-bin and statistic-identity premises of the theorems no longer hold.
Editorial extensions
If this is right
- Independence testing with any fixed bin count—even $s=2$—keeps the standard test's separation rate, so the cheap version can be adopted with no rate loss.
- For homogeneity, a bin count of order $\sqrt[3]{1/(\beta\alpha^\star\rho_{n_1n_2})}$ preserves the rate, and any unboundedly growing $s$ makes the cheap threshold asymptotically equal to the standard one.
- The quantile comparison method lowers the permutation requirement for standard Monte Carlo permutation tests to $B \geq 1/\alpha - 1$, improving on earlier constraints such as $B \geq 8\alpha^{-2}\log(4/\beta)$.
- After precomputing bin sufficient statistics, the entire permutation loop costs $\Theta(Bs^2)$ independent of $n$, so a slow-growing or constant $s$ makes total runtime comparable to evaluating the original statistic once.
- Exactness holds for every sample size and data distribution, matching the standard permutation test's finite-sample validity rather than a large-sample approximation.
Reading between the lines
- The equal-bin assumption ($m = n/s$ and $s_1 = s n_1/n$ integral) is explicit for the independence test but only implicit for homogeneity; if rounding is needed for arbitrary $n$, a direct analysis of unequal bins or a rounding correction would be the natural next step.
- Because the permuted-statistic overhead is independent of $n$, cheap permutation can be stacked on sequential or early-stopping permutation schemes to make the entire testing process cost independent of sample size—a combination the paper notes but does not develop.
- For low-rank feature kernels (e.g., random Fourier features), the cheap scheme's cost drops to $\Theta(Bsr)$ with $\Theta(sr)$ memory, which suggests the approach is especially favorable for high-dimensional kernel testing where $O(n^2)$ memory is prohibitive.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes 'cheap permutation tests': instead of permuting individual datapoints, one partitions the sample into s bins and permutes the bins. For quadratic test statistics (QTS), including homogeneity U-statistics and independence V-statistics, the paper shows that the bin-permuted statistics can be computed in O(B s^2) time after an O(n^2) precomputation, using O(s^2) sufficient statistics. The paper claims that these cheap tests inherit the exact finite-sample level of standard permutation tests and that their power matches standard permutation power up to constants, with the same minimax separation rates. The main theorems (Thms. 1-4) give explicit separation thresholds for cheap and standard tests, and Section 5 derives minimax optimality corollaries. Experiments compare cheap MMD, RFF, WMW, and HSIC tests against their standard and asymptotic counterparts.
Significance. If the power results hold for the implemented algorithms, this is a valuable contribution: it offers exact, finite-sample valid tests whose permutation overhead is independent of n, together with refined power guarantees for standard permutation tests. The exactness argument (Prop. 1) and the computational complexity statements are straightforward and convincing. The power proofs are substantial and introduce a quantile comparison method (Prop. 2) that improves on previous two-moments analyses. The experiments are extensive and the code is publicly available. However, the central power theorems are proven for a bin-level U/V-statistic that is not shown to equal the statistic actually computed by Algs. 1 and 2; this mismatch is load-bearing for the paper's main claim.
major comments (2)
- [App. A.1, Eq. (30); Alg. 1, lines 7-8] The power analysis for cheap homogeneity testing is carried out for the bin-level U-statistic U^{pi,s}_{n1,n2} defined in Eq. (30), not for the statistic T_b computed by Alg. 1. For m = n/s > 1 these objects differ: Eq. (30) averages H_ho,m over ordered quadruples of distinct bins, so it includes only point quadruples whose two Y-points and two Z-points lie in distinct bins, under the normalization (s1)_2(s2)_2; the QTS in Alg. 1, by contrast, is the point-level U-statistic U_{n1,n2} of the permuted point sample, whose normalization is (n1)_2 (n2)_2 and which additionally includes within-bin Y-Y and Z-Z point pairs. The sentence in App. A.1 that the substitutions 'help us to frame' the cheap test as a standard U-statistic test on bins is not a proof of equality, and no distributional identity or stochastic dominance is supplied. Since Prop. 2 requires the auxiliary sequence to be the actual sequence generating the critical value, Theorems 1-4 and Propositions 3-6 currently establish power for a different procedure than the one implemented and benchmarked. This gap is load-bearing for the paper's central claim and must be closed, either by proving that T_b has the same permutation distribution as (30) (up to a term whose effect on the quantile comparison is controlled) or by redefining the algorithm to compute the analyzed statistic and re-running the experiments.
- [App. A.2, Eq. (32); Alg. 2, lines 16-17] The independence power theorems have the same mismatch. Alg. 2's T_b is the point-level independence V-statistic of Def. 3 evaluated on bin-permuted Z-blocks, while the proofs analyze V^{pi,s}_n of Eq. (32), which replaces h_in by the bin-averaged kernel H_in,m. For m > 1 these statistics are not equal: the bin-averaged kernel treats all m^4 point combinations within the four selected bins, including within-bin point pairs, whereas the point-level V-statistic uses the normalization n^4 and the original kernel h_in. Consequently the bounds of Thm. 3, Cor. 2, and Thm. 4 do not apply to the implemented Alg. 2 without an additional equivalence argument.
minor comments (5)
- [Sec. 3.2 / Alg. 1] The homogeneity algorithm assumes that n is divisible by s and that s1 = s n1/n is an integer, but this is only implicit in the main text and in App. A.1. State these assumptions explicitly, as is done for the independence setting in Sec. 3.4.
- [Secs. 6.1.2 and 6.2.2] The phrase 'final-sample validity' appears to be a typo for 'finite-sample validity'; please correct it in the two places where it occurs.
- [Cor. 1, Eq. (12)] The displayed expression for eps_{n1,n2,s} contains a line break and missing parentheses that make the formula hard to parse; please re-typeset it so that the nested radicals are unambiguous.
- [Sec. 4.3, Prop. 2] The text states that Prop. 2 requires only B >= 1/alpha - 1 permutations, but this condition is not included in the proposition statement. Add it explicitly, since it is needed for the quantile comparison argument.
- [App. D.6] The proof of Lemma D.5 relies on a distributional construction cited from [29, Sec. 6.1]; since this is central to the sub-Gaussian threshold bound, a self-contained statement of the construction would improve readability.
Circularity Check
No circularity: the cheap-test power guarantees are derived from variance and quantile-comparison lemmas, not from fitted parameters or from the paper's own conclusion.
full rationale
The paper's central claims (Thms. 1-4 and the minimax propositions) are derived from explicit upper bounds on unconditional and conditional variances of U/V-statistics, mean bounds on permuted statistics, and the quantile comparison method of Prop. 2. These proofs do not fit any parameter to the data whose power is later reported, and they do not assume the separation thresholds they aim to establish; each theorem states a sufficient condition of the form 'power is at least 1-beta whenever the population parameter exceeds an explicit expression' and then proves the condition by bounding the relevant moments. No instance of the enumerated circular patterns appears in the derivation chain. The only overlapping-author citation is [15], used in App. H for Lemma H.1, a high-probability bound on the Monte Carlo critical value in terms of the conditional quantile of the auxiliary sequence. The paper states that the proof is identical to [15, Lem. 6, Cor. 1] and gives the general argument in Prop. 2. That lemma is a technical order-statistic bound, not the paper's target result; its assumptions do not include cheap permutation power or the theorems being proved, so the citation is a tool rather than a self-imported conclusion. A separate concern noted in the paper's framing, App. A.1, is that the bin-level statistic analyzed in the power proofs is described as a way to 'frame' the cheap test as a standard U-statistic permutation test on bins; if the exact identity between Alg. 1's computed statistic and the analyzed U/V-statistic is not fully demonstrated, that would be a correctness or proof gap, not a circular reduction. The bin-level object is not defined in terms of the power threshold, and no equation in the paper sets the predicted quantity equal to an input by construction. Accordingly, the honest finding is no significant circularity, with score 0.
Assumptions & free parameters
assumptions (6)
- standard math Hoeffding exchangeability: under the null, the distribution of the concatenated sample is invariant under permutations and, for independence, under wild bootstrap swaps of Z blocks.
- standard math Standard U-statistic variance decomposition and kernel degeneracy theory (Lee 1990, Serfling 2009).
- standard math Concentration inequalities: Cantelli, Markov, Hoeffding, Hanson-Wright, bounded differences, and sub-Gaussian concentration.
- domain assumption The test statistic is a quadratic statistic (Def. 1) or an independence V-statistic (Def. 3) with symmetric base functions.
- domain assumption Finite variance components for Thms. 1 and 3, and sub-Gaussian or bounded kernel parameters for Thms. 2 and 4.
- domain assumption Equal-size bins and integrality: n is divisible by s and s n1/n is an integer, so each bin has exactly m = n/s points.
Cite this review
Pith. "Pith review of Cheap Permutation Testing." pith.science (2026). https://pith.science/paper/HE3Y43PV
@misc{pith2026250207672,
author = {Pith},
title = {Pith review of: Cheap Permutation Testing},
year = {2026},
howpublished = {\url{https://pith.science/paper/HE3Y43PV}},
note = {Machine review of arXiv:2502.07672}
}
read the original abstract
Permutation tests are a popular choice for distinguishing distributions and testing independence, due to their exact, finite-sample control of false positives and their minimax optimality when paired with U-statistics. However, standard permutation tests are also expensive, requiring a test statistic to be computed hundreds or thousands of times to detect a separation between distributions. In this work, we offer a simple approach to accelerate testing: group your datapoints into bins and permute only those bins. For U and V-statistics, we prove that these cheap permutation tests have two remarkable properties. First, by storing appropriate sufficient statistics, a cheap test can be run in time comparable to evaluating a single test statistic. Second, cheap permutation power closely approximates standard permutation power. As a result, cheap tests inherit the exact false positive control and minimax optimality of standard permutation tests while running in a fraction of the time. We complement these findings with improved power guarantees for standard permutation testing and experiments demonstrating the benefits of cheap permutations over standard maximum mean discrepancy (MMD), Hilbert-Schmidt independence criterion (HSIC), random Fourier feature, Wilcoxon-Mann-Whitney, aggregated MMD, cross-MMD, and cross-HSIC tests.
Forward citations
Cited by 1 Pith paper
-
Aggregation of Statistical Evidence under Exchangeability
Calibrating aggregated test statistics on the permutation distribution itself is finite-sample valid and at least as powerful as Bonferroni-type worst-case calibration, with sequential and two-batch extensions.
Reference graph
Works this paper leans on
-
[1]
A NDERSON , W. N. and V ERBEECK , J. (2023). Exact Permutation and Bootstrap Distribution of General- ized Pairwise Comparisons Statistics. Mathematics 11
2023
-
[2]
and S ALIGRAMA , V
A RIAS -CASTRO , E., P ELLETIER , B. and S ALIGRAMA , V. (2018). Remember the curse of dimensionality: the case of goodness-of-fit testing in arbitrary dimension.Journal of Nonparametric Statistics30 448– 471. 20
2018
-
[3]
and F RANZ , C
B ARINGHAUS , L. and F RANZ , C. (2004). On a new multivariate two-sample test. Journal of Multivariate Analysis 88 190-206
2004
-
[4]
B., KONTOYIANNIS , I
B ERRETT , T. B., KONTOYIANNIS , I. and SAMWORTH , R. J. (2021). Optimal rates for independence testing via U-statistic permutation tests. The Annals of Statistics 49 2457–2490
2021
-
[5]
and C LIFFORD , P
B ESAG , J. and C LIFFORD , P. (1991). Sequential monte carlo p-values. Biometrika 78 301–304
1991
-
[6]
B OUCHERON , S., L UGOSI , G. and M ASSART , P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford
work page 2013
-
[7]
C ANTELLI , F. P. (1929). Sui confini della probabilita. In Atti del Congresso Internazionale dei Matematici: Bologna del 3 al 10 de settembre di 1928 47–60
work page 1929
-
[8]
C HUNG , J. and F RASER , D. (1958). Randomization Tests for a Multivariate Two-Sample Problem.Journal of the American Statistical Association 729–735
work page 1958
Show all 85 references
-
[9]
and R OMANO , J
C HUNG , E. and R OMANO , J. P. (2013). Exact and asymptotically robust permutation tests. The Annals of Statistics 41 484 – 507
2013
-
[10]
and R OMANO , J
C HUNG , E. and R OMANO , J. P. (2016). Asymptotically valid and exact permutation tests based on two- sample U-statistics. Journal of Statistical Planning and Inference 168 97–105
2016
-
[11]
K., X IE, L., H UANG , S.-G., W ANG , Y., Y AN, J
C HUNG , M. K., X IE, L., H UANG , S.-G., W ANG , Y., Y AN, J. and S HEN , L. (2019). Rapid accelera- tion of the permutation test via transpositions. In Connectomics in NeuroImaging: Third International Workshop, CNI 2019, Held in Conjunction with MICCAI 2019, Shenzhen, China...
2019
-
[12]
P., SEJDINOVIC , D
C HWIALKOWSKI , K. P., SEJDINOVIC , D. and GRETTON , A. (2014). A wild bootstrap for degenerate kernel tests. Advances in neural information processing systems 27
2014
-
[13]
and O LVER, N
D ADUSH , D., G UZMÁN , C. and O LVER, N. (2018). Fast, Deterministic and Sparse Dimensionality Re- duction. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’18 1330–1344. Society for Industrial and Applied Mathematics, USA
2018
-
[14]
and A GARWAL , D
D ICICCIO , C., V ASUDEVAN , S., B ASU , K., K ENTHAPADI , K. and A GARWAL , D. (2020). Evaluating fairness using permutation tests. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining 1467–1477
2020
-
[15]
and M ACKEY, L
D OMINGO -E NRICH , C., D WIVEDI , R. and M ACKEY, L. (2023). Compress Then Test: Powerful Kernel Testing in Near-linear Time. InProceedings of The 26th International Conference on Artificial Intelli- gence and Statistics. Proceedings of Machine Learning Research 206 1174–1218. PMLR
2023
-
[16]
D WASS, M. (1957). Modified randomization tests for nonparametric hypotheses. The Annals of Mathemat- ical Statistics 181–187
1957
-
[17]
P., KIM, H.-J
F AY, M. P., KIM, H.-J. and H ACHEY, M. (2007). On using truncated sequential probability ratio test bound- aries for Monte Carlo implementation of hypothesis tests. Journal of Computational and Graphical Statistics 16 946–967
2007
-
[18]
and R AMDAS , A
F ISCHER , L. and R AMDAS , A. (2024). Sequential Monte-Carlo Testing by Betting. arXiv preprint arXiv:2401.07365
2024 arXiv
-
[19]
F ISHER , R. A. (1925). Statistical Methods for Research Workers. Oliver and Boyd, Edinburgh
1925
-
[20]
and R EYNAUD -BOURET , P
F ROMONT , M., L AURENT , B. and R EYNAUD -BOURET , P. (2013). The two-sample problem for Poisson processes: Adaptive tests with a nonasymptotic wild bootstrap approach. The Annals of Statistics 41 1431 – 1461
2013
-
[21]
G OOD , P. (2013). Permutation tests: a practical guide to resampling methods for testing hypotheses . Springer Science & Business Media
2013
-
[22]
and S CHÖLKOPF , B
G RETTON , A., B OUSQUET , O., S MOLA , A. and S CHÖLKOPF , B. (2005). Measuring Statistical Depen- dence with Hilbert-Schmidt Norms. In Proceedings of the 16th International Conference on Algorith- mic Learning Theory 63–77. Springer-Verlag, Berlin, Heidelberg
2005
-
[23]
and S MOLA , A
G RETTON , A., F UKUMIZU , K., T EO, C., S ONG , L., S CHÖLKOPF , B. and S MOLA , A. (2007). A Kernel Statistical Test of Independence. In Advances in Neural Information Processing Systems 20
2007
-
[24]
M., R ASCH , M
G RETTON , A., B ORGWARDT , K. M., R ASCH , M. J., S CHÖLKOPF , B. and S MOLA , A. (2012). A Kernel Two-Sample Test.Journal of Machine Learning Research 13 723-773
2012
-
[25]
Y., B ASU , K., Z HAO, Q
H E, H. Y., B ASU , K., Z HAO, Q. and O WEN , A. B. (2019). Permutation p-value approximation via gener- alized Stolarsky invariance. The Annals of Statistics 47 583–611
2019
-
[26]
H OEFFDING , W. (1952). The Large-Sample Power of Tests Based on Permutations of Observations. The Annals of Mathematical Statistics 23 169 – 192
1952
-
[27]
H OEFFDING , W. (1963). Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association 58 13–30
1963
-
[28]
J ANSSEN , A. (1997). Studentized permutation tests for non-iid hypotheses and the generalized Behrens- Fisher problem. Statistics & probability letters 36 9–21
1997
-
[29]
and W ASSERMAN , L
K IM, I., B ALAKRISHNAN , S. and W ASSERMAN , L. (2022). Minimax optimality of permutation tests. The Annals of Statistics 50 225–251. CHEAP PERMUTATION TESTING 21
2022
-
[30]
and S CHRAB , A
K IM, I. and S CHRAB , A. (2023). Differentially private permutation tests: Applications to kernel methods. arXiv preprint arXiv:2310.19043
2023 arXiv
-
[31]
A., W ESSELS , L
K NIJNENBURG , T. A., W ESSELS , L. F., R EINDERS , M. J. and S HMULEVICH , I. (2009). Fewer permuta- tions, more accurate P-values. Bioinformatics 25 i161–i168
2009
-
[32]
K ONING , N. W. (2024). More power by using fewer permutations. Biometrika 111 1405–1412
2024
-
[33]
K ONING , N. W. and H EMERIK , J. (2024). More efficient exact group invariance testing: using a represen- tative subgroup. Biometrika 111 441–458
2024
-
[34]
L ARSON , J. L. and O WEN , A. B. (2015). Moment based gene set tests. BMC bioinformatics 16 1–17
2015
-
[35]
L EE, A. J. (1990). U-Statistics: Theory and Practice . Statistics: A Series of Textbooks and Monographs . Taylor & Francis
1990
-
[36]
and E RIKSSON , L
L INDGREN , F., HANSEN , B., K ARCHER , W., SJÖSTRÖM , M. and E RIKSSON , L. (1996). Model validation by permutation tests: applications to variable selection. Journal of Chemometrics 10 521–532
1996
-
[37]
and S UTHERLAND , D
L IU, F., X U, W., L U, J., Z HANG , G., G RETTON , A. and S UTHERLAND , D. J. (2020). Learning Deep Kernels for Non-Parametric Two-Sample Tests. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Proceedings of ...
2020
-
[38]
M ANN , H. B. and W HITNEY , D. R. (1947). On a Test of Whether one of Two Random Variables is Stochas- tically Larger than the Other. The Annals of Mathematical Statistics 18 50 – 60
1947
-
[39]
M ARKOV, A. (1884). On certain applications of algebraic continued fractions. Unpublished Ph. D. thesis, St Petersburg
-
[40]
and P ONTIL , M
M AURER , A. and P ONTIL , M. (2021). Concentration inequalities under sub-Gaussian and sub-exponential conditions. In Advances in Neural Information Processing Systems 34 7588–7597. Curran Associates, Inc
2021
-
[41]
and T ALWALKAR , A
M OHRI , M., R OSTAMIZADEH , A. and T ALWALKAR , A. (2012). Foundations of Machine Learning. The MIT Press
2012
-
[42]
N EUHAUS , G. (1993). Conditional rank tests for the two-sample problem under random censorship. The Annals of Statistics 1760–1779
1993
-
[43]
P ANDA , S., S HEN , C., P ERRY, R., Z ORN , J., L UTZ , A., P RIEBE , C. E. and V OGELSTEIN , J. T. (2025). Universally consistent K-sample tests via dependence measures. Statistics & Probability Letters 216 110278
2025
-
[44]
and P ETERS , J
P FISTER , N., B ÜHLMANN , P., S CHÖLKOPF , B. and P ETERS , J. (2018). Kernel-based tests for joint inde- pendence. Journal of the Royal Statistical Society Series B: Statistical Methodology 80 5–31
2018
-
[45]
and SMYTH , G
P HIPSON , B. and SMYTH , G. K. (2010). Permutation P-values Should Never Be Zero: Calculating Exact P- values When Permutations Are Randomly Drawn. Statistical Applications in Genetics and Molecular Biology 9
2010
-
[46]
and R ECHT , B
R AHIMI , A. and R ECHT , B. (2008). Random Features for Large-Scale Kernel Machines. In Advances in Neural Information Processing Systems 20 (J. C. Platt, D. Koller, Y . Singer and S. T. Roweis, eds.) 1177–1184. Curran Associates, Inc
2008
-
[47]
F., C ANDÈS , E
R AMDAS , A., B ARBER , R. F., C ANDÈS , E. J. and T IBSHIRANI , R. J. (2023). Permutation tests using arbitrary permutation distributions. Sankhya A 1–22
2023
-
[48]
and G RETTON , A
S CHRAB , A., K IM, I., A LBERT , M., L AURENT , B., G UEDJ , B. and G RETTON , A. (2021). MMD Aggre- gated Two-Sample Test
2021
-
[49]
and G RETTON , A
S CHRAB , A., K IM, I., G UEDJ , B. and G RETTON , A. (2022). Efficient Aggregated Kernel Tests using Incomplete U-statistics
2022
-
[50]
D., B RAUN , T., E LLIOTT , M
S EGAL , B. D., B RAUN , T., E LLIOTT , M. R. and J IANG , H. (2018). Fast approximation of small p-values in permutation tests by partitioning the permutations. Biometrics 74 196–206
2018
-
[51]
and F UKUMIZU , K
S EJDINOVIC , D., S RIPERUMBUDUR , B., G RETTON , A. and F UKUMIZU , K. (2013). Equivalence of distance-based and RKHS-based statistics in hypothesis testing. The Annals of Statistics 2263–2291
2013
-
[52]
S ERFLING , R. (2009). Approximation Theorems of Mathematical Statistics 162. John Wiley & Sons
2009
-
[53]
and R AMDAS , A
S HEKHAR , S., K IM, I. and R AMDAS , A. (2022). A permutation-free kernel two-sample test. In Advances in Neural Information Processing Systems
2022
-
[54]
and R AMDAS , A
S HEKHAR , S., K IM, I. and R AMDAS , A. (2023). A Permutation-Free Kernel Independence Test. Journal of Machine Learning Research 24 1–68
2023
-
[55]
S ILVA, I. R. and A SSUNÇÃO , R. M. (2013). Optimal generalized truncated sequential Monte Carlo test. Journal of Multivariate Analysis 121 33-49. https://doi.org/10.1016/j.jmva.2013.06.003
2013 doi
-
[56]
and C HRISTMANN , A
S TEINWART , I. and C HRISTMANN , A. (2008). Support vector machines . Springer Science & Business Media
2008
-
[57]
J., T UNG , H.-Y., S TRATHMANN , H., D E, S., R AMDAS , A., S MOLA , A
S UTHERLAND , D. J., T UNG , H.-Y., S TRATHMANN , H., D E, S., R AMDAS , A., S MOLA , A. and G RET- TON , A. (2017). Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy. In International Conference on Learning Representations. 22
2017
-
[58]
and R IZZO , M
S ZEKELY, G. and R IZZO , M. (2004). Testing for equal distributions in high dimension. InterStat 5
2004
-
[59]
J., R IZZO , M
S ZÉKELY, G. J., R IZZO , M. L. and B AKIROV, N. K. (2007). Measuring and testing dependence by corre- lation of distances. The Annals of Statistics 35 2769 – 2794
2007
-
[60]
W ILCOXON , F. (1945). Individual Comparisons by Ranking Methods. Biometrics Bulletin 1 80–83
1945
-
[61]
and W ANG , Y
Z HOU , C., W ANG , H. and W ANG , Y. (2009). Efficient moments-based permutation tests. Advances in neural information processing systems 22
2009
-
[62]
Cheap Permutation Testing
Z MIGROD , R., V IEIRA , T. and C OTTERELL , R. (2022). Exact Paired-Permutation Testing for Structured Test Statistics. In Proceedings of the 2022 Conference of the North American Chapter of the Associa- tion for Computational Linguistics: Human Language Technologies4894–4902...
2022
-
[63]
+ 4n2 1n2 2 ≥ 8n1n2(n2 1 + n2
-
[64]
≥ 8(n1 − 1)(n2 − 1)(n2 1 + n2 2). B.1. Proof of Lem. B.1: Variance of homogeneity U-statistics. By [35, p. 38], Var(Un1,n1) ≤ P2 i=0 P2 j=0 2 i 2 j n1−2 2−i n2−2 2−j n1 2 −1n2 2 −1ˆσ2 i,j = 16P2 i=0 P2 j=0 (n1−2)!2 n1!i!(2−i)!2(n1−4+i)! (n2−2)!2 n2!j!(2−j)!2(n2−4+j)! ˆσ2 i,j w...
-
[65]
CHEAP PERMUTATION TESTING 27 B.2.1
and s(i) ≜ |{i1, i2} ∩ {i′ 1, i′ 2}| + |{j1, j2} ∩ {j′ 1, j′ 2}|. CHEAP PERMUTATION TESTING 27 B.2.1. Proof of (34). Following the proof of [29, Thm. 4.1], we define the index sets Itotal ≜ {i ∈ N8 + : (i1, i2) ∈ in1 2 , (j1, j2) ∈ in2 2 , (i′ 1, i′
-
[66]
By the argument of [29, Thm
∈ in2 2 }, I1 ≜ {i ∈ Itotal : s(i) ≤ 1}, and Ic 1 = {i ∈ Itotal : s(i) > 1}. By the argument of [29, Thm. 4.1], we have E[Var(U π,n n1,n2|X)] ≤ ˜ψY Z,2 |Ic 1| (n1)2 (2)(n2)2 (2) ,(39) where ˜ψY Z,2 is the maximum over i ∈ Ic 1 of E E[hho(Xπi1 , Xπi2 ; Xπn1 +j1 , Xπn1 +j2 )hho(...
-
[67]
• Ib, containing the indices for which exactly one pair among(i1, i2), (i′ 1, i′ 2), (n1 + j1, n1 + j′ 1), (n1 + j2, n1 + j′
share the same bin, but {⌊i1/m⌋, ⌊i2/m⌋} ∩ {⌊i′ 1/m⌋, ⌊i′ 2/m⌋} = ∅, {⌊(n1 + j1)/m⌋, ⌊(n1 + j2)/m⌋} ∩ {⌊(n1 + j′ 1)/m⌋, ⌊(n1 + j′ 2)/m⌋} = ∅. • Ib, containing the indices for which exactly one pair among(i1, i2), (i′ 1, i′ 2), (n1 + j1, n1 + j′ 1), (n1 + j2, n1 + j′
-
[68]
• Irest, containing the rest of indices
shares the same bin, and|{⌊i1/m⌋, ⌊i2/m⌋} ∩ {⌊i′ 1/m⌋, ⌊i′ 2/m⌋}| + |{⌊(n1 + j1)/m⌋, ⌊(n1 + j2)/m⌋} ∩ {⌊(n1 + j′ 1)/m⌋, ⌊(n1 + j′ 2)/m⌋}| = 1. • Irest, containing the rest of indices. For indices in Irest, there has to be at least one pair among (i1, i2), (i′ 1, i′ 2), (n1 + j...
-
[69]
From this argument, we can deduce that |Irest| ≤(4s1s4 2 + 4s2 1s3 2 + 16s2 1s3 2 + 16s3 1s2 2 + 4s4 1s2 + 4s3 1s2 2)m8 = (4s1s4 2 + 20s2 1s3 2 + 20s3 1s2 2 + 4s4 1s2)m8
that shares the same bin, and there have to be at least two pairs formed by an index in {i1, i2, n1 + j1, n1 + j2} and an 28 index in {i′ 1, i′ 2, n1 + j′ 1, n1 + j′ 2} such that both indices belong to the same bin. From this argument, we can deduce that |Irest| ≤(4s1s4 2 + 4s...
-
[70]
∈ is2 2 }, K1 ≜ {i ∈ Ktotal : s(i) ≤ 1}, Kc 1 = {i ∈ Ktotal : s(i) > 1}, and K2 ≜ {i ∈ Ktotal : s(i) = 2}. We compute the size of K2: |K2| = 2s1(s1 − 1)s2(s2 − 1)(s2 − 2)(s2 − 3) + 2s1(s1 − 1)(s1 − 2)(s1 − 3)s2(s2 − 1) + 4s1(s1 − 1)(s1 − 2) · 4s2(s2 − 1)(s2 − 2) = s1(s1 − 1)s2...
-
[71]
i ∈ K2, with, for the indices in i that are equal, the corresponding indices in K are also equal (so that, for each i ∈ K2, there are at most m6 terms with non-zero contribution), or
-
[72]
i ∈ Kc 1 \ K2, and K ∈ Jc 1 (as otherwise the terms would have zero contribution). CHEAP PERMUTATION TESTING 29 We now bound the size of Jc 1: |J1| = |{K ∈ Jtotal | s(K) = 0}| + |{K ∈ Jtotal | s(K) = 1}| |{K ∈ Jtotal | s(K) = 0}| ≥m(m − 1)(m − 2)(m − 3)m(m − 1)(m − 2)(m − 3) +...
-
[73]
∈ Ktotal : |{i1, i2, i3, i4} ∩ {i′ 1, i′ 2, i′ 3, i′ 4}| = 0}, K2 ≜ {(i1, i2, i3, i4, i′ 1, i′ 2, i′ 3, i′
-
[74]
∈ Ktotal : |{i1, i2, i3, i4} ∩ {i′ 1, i′ 2, i′ 3, i′ 4}| = 1}, and (K1 ∪ K2)c ≜ {(i1, i2, i3, i4, i′ 1, i′ 2, i′ 3, i′
-
[75]
∈ Ktotal : |{i1, i2, i3, i4} ∩ {i′ 1, i′ 2, i′ 3, i′ 4}| > 1}. Then, Var(Vn) = E[V 2 n ] − E[Vn]2 = 1 n8 P (i1,...,i4,i′ 1,...,i′ 4)∈Ktotal E[hin(Xi1, Xi2, Xi3, Xi4)hin(Xi′ 1, Xi′ 2, Xi′ 3, Xi′ 4)] − E[hin(Xi1, Xi2, Xi3, Xi4)]E[hin(Xi′ 1, Xi′ 2, Xi′ 3, Xi′ 4)] = (I) + (II ) + ...
-
[76]
∈ K1, (II ) is the summation over (i1, . . . , i′
-
[77]
∈ K2, and (III ) is the summation over (i1, . . . , i′
-
[78]
Note that |K2| ≤n4 · 4 · 4 · n3 = 16n7 and |(K1 ∪ K2)c| ≤n4 · 4 · 3 · 4 · 3 · n2 = 144n6
∈ (K1 ∪ K2)c. Note that |K2| ≤n4 · 4 · 4 · n3 = 16n7 and |(K1 ∪ K2)c| ≤n4 · 4 · 3 · 4 · 3 · n2 = 144n6. We also remark that for(i1, . . . , i′
-
[79]
By the definition (14) of ψ′ 1, we have that (II ) ≤ 1 n8 |K2|ψ′ 1 ≤ 16ψ′ 1 n
∈ K1, E[hin(Xi1, Xi2, Xi3, Xi4)hin(Xi′ 1, Xi′ 2, Xi′ 3, Xi′ 4)] = E[hin(Xi1, Xi2, Xi3, Xi4)]E[hin(Xi′ 1, Xi′ 2, Xi′ 3, Xi′ 4)], which implies that (I) = 0. By the definition (14) of ψ′ 1, we have that (II ) ≤ 1 n8 |K2|ψ′ 1 ≤ 16ψ′ 1 n . By the nonnegativity of hin, Cauchy-Schwa...
-
[80]
and s(K) ≜ |{k1, k2, k3, k4}∩{ k′ 1, k′ 2, k′ 3, k′ 4}|, we define the index sets Ltotal = [m]8, L1 = {K ∈ Ltotal : s(K) = 0}, L2 = {K ∈ Ltotal : s(K) = 1}, and (L1 ∪ L2)c = {K ∈ Ltotal : s(K) > 1} and note that |L2| ≤m4 · 4 · 4 · m3 = 16m7 and |(L1 ∪ L2)c| ≤m4 · 4 · 3 · 4 · 3...
-
[81]
The only non-zero summands in the sum over K have k1 = k′
-
[82]
• i ∈ ˜K2: Consider the three indices of i that satisfy the defining ˜K2 property
There are m7 such summands, and each contributes at most ˜ψ′ 1 to the sum. • i ∈ ˜K2: Consider the three indices of i that satisfy the defining ˜K2 property. In the sum- mation over K ∈ Ltotal, a summand contributes at most ˜ψ′ 1 when exactly two of the three i indices share t...
-
[83]
Moreover, our assumption (23) on Ψn ensures that Pr(Ac
≤ β/3 for A1 ≜ {T(bα) ≤ ΨX(α⋆)}. Moreover, our assumption (23) on Ψn ensures that Pr(Ac
-
[84]
≤ β/3 for A2 ≜ {ΨX(α⋆) ≤ Ψn(α⋆, β/3)}. Since ∆(X) rejects when T (X) > T(bα), the acceptance probability is upper-bounded by Pr(T (X) ≤ T(bα)) = Pr(T (X) ≤ T(bα), A1 ∩ A2) + Pr(T (X) ≤ T(bα), Ac 1 ∪ Ac 2) ≤ Pr(T (X) ≤ Ψn(α⋆, β/3)) + Pr(Ac 1 ∪ Ac 2) ≤ Pr(T (X) ≤ T −Φn( β 3 )) + Pr(Ac
-
[85]
APPENDIX I: Proof of Cor
≤ β, where the final two inequalities used the union bound and our assumptions (20) and (21). APPENDIX I: Proof of Cor. 3: Refined two moments method Our choices of Φn and ΨX satisfy the requirements (21) and (22) by Cantelli’s inequality [7, (18)]. Moreover, Markov’s inequali...
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.