📊 statistics

Differentially Private Permutation Tests

This paper introduces a rigorous framework for differentially private permutation tests that extends classical methods to private settings while maintaining finite-sample validity and achieving minimax optimal power, specifically demonstrating its effectiveness through the development of dpMMD and dpHSIC kernel-based tests for two-sample and independence testing.

Original authors: Ilmun Kim, Antonin Schrab

Published 2026-07-30

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ilmun Kim, Antonin Schrab

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but you have a strict rule: you can never look at the clues directly. In the world of data science, this is the challenge of Differential Privacy. It's a set of mathematical rules that let researchers analyze huge piles of personal information—like medical records or browsing history—without ever being able to peek at any single person's data. It's like trying to figure out the average height of a crowd by only looking at a blurry, noisy photo of the group, ensuring no one can be identified.

To solve mysteries, statisticians use Hypothesis Testing. Think of this as a courtroom trial. The "Null Hypothesis" is the defendant's plea of "not guilty" (meaning the two groups of data are just random noise and look the same). The "Alternative Hypothesis" is the prosecution's claim that there is a real difference. To decide who wins, statisticians use a Permutation Test. Imagine you have two bags of marbles, one red and one blue. You mix them all up, then randomly shuffle them back into two new bags. If you do this a thousand times and the original bags were always more different than the shuffled ones, you know the red and blue marbles weren't just mixed by chance; there was a real pattern. The problem is, doing this shuffle-and-check process usually requires seeing the raw data, which breaks the privacy rules.

This paper, titled "Differentially Private Permutation Tests," tackles a tricky problem: How do you run this "shuffle and check" game when you aren't allowed to see the marbles clearly? The authors, Ilmun Kim and Antonin Schrab, introduce a new way to play the game that keeps the data private but still finds the truth. They show that you can't just add a little bit of noise to the data and hope for the best; that old way makes the test too weak to spot real differences. Instead, they built a smarter system that adds noise in a very specific, calculated way. Their method works for all kinds of data, from simple numbers to complex images, and they proved mathematically that it's the best possible way to do this under strict privacy rules.

The New Game Plan: Shuffling in the Dark

The authors realized that the old way of making permutation tests private was like trying to whisper a secret to a thousand friends by shouting it to each one individually. It worked, but the noise got so loud that the message was lost. Their new approach, called dpMMD (for two-sample testing) and dpHSIC (for independence testing), is more like a clever magic trick.

Instead of adding noise to every single shuffle, they use a technique that adds noise just once to the final decision-making process. They treat the "shuffled" data and the "original" data as a team, adding a tiny bit of mathematical fog (noise) to the whole group. This fog is thick enough to hide any single person's identity, but thin enough that the overall pattern of the data remains visible.

The paper proves that this new method is valid, meaning it won't falsely accuse innocent data of having a pattern (it controls the "Type I error" perfectly, even with small groups of data). It's also powerful, meaning it can actually spot the differences when they exist. The authors tested this on everything from synthetic math problems to real-world data, including a massive dataset of celebrity faces (the CelebA dataset). In these tests, their method was the clear winner, spotting differences in high-dimensional images where other privacy-preserving methods failed completely.

Why the Old Ways Didn't Work

One of the most interesting parts of the paper is what they didn't do. For a long time, statisticians loved using something called U-statistics to measure differences between groups. It was the standard tool for the job. However, the authors discovered that when you try to make U-statistics private, they become too sensitive to noise.

Imagine U-statistics as a very delicate scale. If you try to hide the weight of a single apple on that scale by adding a heavy blanket (noise) to protect privacy, the scale gets so covered in blankets that it can't tell the difference between a feather and a rock. The authors showed that their method, which uses a different type of calculation (called a plug-in estimator or V-statistic), is like a sturdier scale. It can handle the heavy privacy blankets without losing its ability to weigh the apples. In fact, they proved mathematically that in "high privacy" situations (where the noise is very heavy), the old U-statistic method is practically useless, while their new method remains sharp and accurate.

The Verdict from the Lab

The authors didn't just write equations; they ran thousands of simulations to see how their method held up in the real world. They tested it against other popular privacy methods, including some that rely on guessing the best settings (heuristics) and others that try to break the data into tiny pieces.

In the simulations, the new method, dpMMD, consistently outperformed the competition.

In "High Privacy" mode: When the rules were strictest (meaning the data was very blurry), the new method could still find the signal, while the old U-statistic methods and other privacy tools gave up and said "I don't know."
In "Low Privacy" mode: When the rules were looser, the new method performed just as well as the best non-private tests, proving that you don't have to sacrifice accuracy to get privacy.
Real-world test: When they applied it to the CelebA face dataset (over 100,000 pixels per image), the method successfully detected the difference between groups of men and women, even though the images were incredibly complex and the privacy noise was high. Other methods either failed to detect the difference or, in one case, started making false alarms (saying there was a difference when there wasn't).

The paper concludes that this new framework is a major step forward. It bridges the gap between the strict math of privacy and the practical need to analyze data. It shows that you don't have to choose between protecting people's secrets and understanding the world; with the right tools, you can do both. The code for their method is open for anyone to use, inviting other scientists to build on this new way of seeing the invisible.

Technical Summary: Differentially Private Permutation Tests

Problem Statement

The paper addresses the challenge of conducting hypothesis testing on sensitive data while adhering to Differential Privacy (DP) constraints. While significant progress has been made in private data analysis, existing methods for hypothesis testing often suffer from two primary limitations:

Reliance on Asymptotics: Many private tests depend on asymptotic distributions to determine critical values. In private settings, the convergence to these limiting distributions is often slow, and the limiting distribution itself may vary based on the interplay between privacy parameters and other statistical parameters, rendering asymptotic approximations unreliable for finite samples.
Limited Practicality and Data Types: Many existing private tests are designed specifically for discrete or bounded data, making them inapplicable to continuous or mixed-type data. Furthermore, many approaches rely on unspecified constants or heuristics, and few are accompanied by thorough empirical evaluations or open-source code.

The authors aim to bridge the gap between theoretical privacy guarantees and practical statistical efficiency by introducing a framework for differentially private permutation tests that maintains finite-sample validity and achieves competitive power across various data types.

Methodology

1. Differentially Private Permutation Framework

The core contribution is a general framework for extending classical non-private permutation tests to private settings.

Naive Approach vs. Proposed Approach: A naive extension would privatize the original test statistic and all permuted counterparts individually. This approach, however, requires adding noise proportional to the number of permutations ( $B$ ), leading to significant power loss as $B$ increases.
Quantile Representation: The authors propose a refined approach utilizing the quantile representation of the permutation test. Instead of privatizing every permuted statistic, they privatize the original statistic ( $T_0$ ) and the quantile threshold ( $Q_{1-\alpha}$ ) of the permuted statistics.
Algorithm:
1. Compute the test statistic $T_0$ on the original data.
2. Generate $B$ random permutations of the data and compute the permuted statistics $T_1, \dots, T_B$ .
3. Add Laplace noise to $T_0$ and to the quantile of $\{T_1, \dots, T_B\}$ . Crucially, the noise scale is determined by the global sensitivity of the statistic and the privacy parameters, but independent of $B$ .
4. Reject the null hypothesis if the privatized $T_0$ exceeds the privatized quantile.
Theoretical Guarantees: This method ensures:
- Finite-Sample Validity: The Type I error is controlled at level $\alpha$ for any finite sample size, provided the data is exchangeable under the null.
- Differential Privacy: The procedure satisfies $(\varepsilon, \delta)$ -differential privacy.
- Power: The framework establishes conditions for pointwise consistency and non-asymptotic uniform power, extending the "two moments method" to private settings.

2. Application to Kernel Tests

To demonstrate the framework's utility, the authors apply it to two specific problems using Reproducing Kernel Hilbert Space (RKHS) based statistics:

Two-Sample Testing: Using the Maximum Mean Discrepancy (MMD).
Independence Testing: Using the Hilbert–Schmidt Independence Criterion (HSIC).

Key Technical Innovations in Kernel Tests:

Sensitivity Analysis: The authors derive sharp upper and lower bounds for the global sensitivity of the plug-in estimators (V-statistics) for MMD and HSIC. This is critical for minimizing the noise added by the Laplace mechanism.
V-statistics vs. U-statistics: The paper explicitly analyzes the use of plug-in estimators (V-statistics) versus U-statistics. They prove that U-statistics have higher global sensitivity in the context of permutation tests, leading to sub-optimal power in high-privacy regimes. Consequently, the proposed dpMMD and dpHSIC tests utilize plug-in estimators.
Mechanism: The tests employ the standard Laplace mechanism with the derived sensitivity bounds.

Key Contributions

General DP Permutation Test Framework: Introduction of Algorithm 1, which privatizes permutation tests via quantile representation. This avoids the linear noise accumulation of naive approaches and guarantees finite-sample validity.
Theoretical Optimality (Minimax Analysis):
- The authors characterize the trade-off between privacy and statistical power via minimax analysis.
- They derive upper and lower bounds for the minimum separation rate (the smallest distance between distributions detectable with high power) in terms of the MMD metric and the $L_2$ metric.
- Result: The proposed dpMMD test is shown to be minimax rate-optimal across all privacy regimes (low, mid, and high privacy) for translation-invariant kernels.
- High-Privacy Regime: For $s \ge d/2$ (smoothness parameter), the test achieves the optimal separation rate of $(n\xi_{\varepsilon,\delta})^{-2s/(2s+d)}$ in the $L_2$ metric, matching the theoretical lower bound.
Negative Results for U-statistics: The paper provides a theoretical justification for avoiding U-statistics in private permutation tests. It demonstrates that U-statistics suffer from higher global sensitivity than their V-statistic counterparts, resulting in sub-optimal power in high-privacy regimes.
Empirical Validation: Extensive simulations on synthetic data (perturbed uniform distributions) and real-world high-dimensional data (CelebA face images) demonstrate that the proposed tests outperform existing private methods (including naive privatization, subsample-and-aggregate variants like TOT and SARRM, and TCS-ME) in terms of statistical power while maintaining correct Type I error control.

Results

Power Performance: In synthetic experiments, dpMMD consistently achieves significantly higher power than competing methods across high, mid, and low privacy regimes. In high-privacy settings, other methods often fail to detect the signal entirely, whereas dpMMD maintains non-trivial power.
Real-World Application: On the CelebA dataset (dimension $d \approx 116,000$ ), dpMMD successfully detects distribution shifts between women's and men's face images with corruption, even using a simple Gaussian kernel that ignores image structure.
Type I Error Control: Unlike some competing methods (e.g., TCS-ME, which showed miscalibration in high dimensions), the proposed permutation tests strictly control the Type I error at the nominal level $\alpha$ in finite samples.
Privacy "Free" Regime: The experiments confirm the theoretical finding that in the low-privacy regime (where the privacy parameter $\varepsilon$ is large), the power of dpMMD matches that of the non-private MMD test, meaning the privacy guarantee comes "for free" in terms of separation rate.

Significance and Claims

The paper claims to offer a practical and theoretically rigorous solution to the problem of private hypothesis testing. Its significance lies in:

Bridging Theory and Practice: It moves beyond asymptotic approximations to provide finite-sample guarantees, addressing a major gap in existing literature where many private tests are either theoretically sound but impractical or practical but lack rigorous finite-sample validation.
Handling Continuous Data: By leveraging kernel methods, the framework is applicable to continuous and high-dimensional data, overcoming the limitations of methods restricted to discrete data.
Optimality: The establishment of minimax optimality for the proposed tests provides a strong theoretical benchmark, proving that the loss of power due to privacy is unavoidable only beyond a certain threshold and is otherwise minimized.
Reproducibility: The authors emphasize the availability of public code to facilitate implementation and further research, contrasting with the "black-box" nature of many heuristic-based private testing methods.

The authors modestly note that while their framework is general, the current implementation focuses on kernel-based statistics. They identify future directions such as extending the framework to other privacy notions (e.g., local DP), exploring non-kernel statistics, and developing computationally efficient variants (sub-quadratic complexity) for large-scale applications.