Cheap Permutation Testing

2025-02-11 · Source: stat.ML updates on arXiv.org · Field: Science & Research — Mathematics & Computational Sciences, Research Methodology & Innovation, Artificial Intelligence & Machine Learning · Depth: Expert, quick

Summary

The paper "Cheap Permutation Testing" (arXiv:2502.07672, v3 revised 21 Jul 2026) introduces a method to accelerate permutation tests. Standard permutation tests, used for distinguishing distributions and testing independence, are computationally expensive, requiring hundreds or thousands of test statistic computations. The proposed "cheap permutation tests" group datapoints into bins and permute only these bins. For U and V-statistics, this approach allows tests to run in time comparable to a single test statistic evaluation by storing sufficient statistics. Crucially, these cheap tests maintain exact false positive control and minimax optimality, closely approximating the power of standard permutation tests. Experiments demonstrate their benefits over various existing tests, including maximum mean discrepancy (MMD), Hilbert-Schmidt independence criterion (HSIC), and Wilcoxon-Mann-Whitney tests.

Key takeaway

For Data Scientists or Research Scientists performing statistical hypothesis testing, you should consider implementing cheap permutation tests. This method drastically reduces the computational cost of distinguishing distributions and testing independence, allowing you to run analyses in time comparable to a single statistic evaluation. You can achieve exact false positive control and maintain high statistical power, making it a superior alternative to traditional permutation tests and other common methods like MMD or HSIC for large datasets.

Key insights

Binning datapoints for permutation tests significantly reduces computation while preserving statistical power and false positive control.

Principles

• Binning data for permutation tests maintains exact false positive control.
• Cheap permutation power closely approximates standard power.
• Minimax optimality is inherited from standard tests.

Method

Group datapoints into bins, then permute only these bins. Store appropriate sufficient statistics to enable rapid test execution, comparable to a single statistic evaluation.

In practice

• Accelerate distribution and independence testing.
• Apply to U and V-statistics for efficiency.
• Improve over MMD, HSIC, and Wilcoxon-Mann-Whitney.

Topics

• Permutation Testing
• Statistical Hypothesis Testing
• U-statistics
• V-statistics
• Computational Efficiency
• Distribution Testing
• Independence Testing

Best for: AI Scientist, Research Scientist, Data Scientist

Related on AIssential

• LOTTERY: Learning from Reference-Only Samples in Two-Sample Testing under Size Asymmetry — LOTTERY enables robust two-sample testing in few-shot, imbalanced settings by learning reference-dependent representations from abundant reference data.
• Hypothesis Testing Is Just a Distance — Hypothesis testing fundamentally measures the distance of an observed result from a chance expectation, expressed in standard deviations.
• Stop Guessing When to Stop Testing: Efficient Model Evaluation with Just Enough Data — Sequential testing offers an adaptive, principled approach to model evaluation, balancing efficiency and reliability over fixed-size benchmarks.
• Empirical Evaluation of No Free Lunch Violations in Permutation-Based Optimization — Algebraic objective reformulation and benchmark design can locally violate No Free Lunch intuition, influencing algorithm performance.
• Finite Resources False Discovery Rate Control in Structured Hypothesis Spaces — A framework unifies FDR control for finite-data p-value uncertainty and structured hypothesis spaces, improving power and resource allocation.
• Handling Imbalanced Classification: What Works Better Than SMOTE — SMOTE is often suboptimal for imbalanced classification; prioritize model-aware, cost-sensitive, and decision-level techniques.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by stat.ML updates on arXiv.org.