Cheap Permutation Testing

Understand

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.