Differentially Private Kolmogorov-Smirnov-Type Tests

The test statistics for many nonparametric hypothesis tests can be expressed in terms of a pseudo-metric applied to the empirical cumulative distribution function (ecdf), such as Kolmogorov-Smirnov, Kuiper, Cram\'er-von Mises, and Wasserstein. These test statistics can be used to test goodness-of-fit, two-samples, paired data, or symmetry. For the design of differentially private (DP) versions of these tests, we show that test statistics of this form have small sensitivity, requiring a minimal amount of noise to achieve DP. The tests are also distribution-free, enabling accurate $p$-value calculations via Monte Carlo approximations. We show that in several settings, especially with small privacy budgets or heavy tailed data, our new DP tests outperform alternative nonparametric DP tests.Comment: 16 pages before references. 3 Figure