The structure of optimal private tests for simple hypotheses

By Clément Louis Canonne, Gautam Kamath, Audra McMillan, Adam D. Smith, Jonathan Ullman. 2018

90 citations recorded by the source corpus.

Hypothesis testing plays a central role in statistical inference, and is used in many settings where privacy concerns are paramount. This work answers a basic question about privately testing simple hypotheses: given two distributions P and Q, and a privacy level ε, how many i.i.d. samples are needed to distinguish P from Q subject to ε-differential privacy, and what sort of tests have optimal sample complexity? Specifically, we characterize this sample complexity up to constant factors in terms of the structure of P and Q and the privacy level ε, and show that this sample complexity is achieved by a certain randomized and clamped variant of the log-likelihood ratio test. Our result is an analogue of the classical Neyman-Pearson lemma in the setting of private hypothesis testing. We also give an application of our result to the private change-point detection. Our characterization applies more generally to hypothesis tests satisfying essentially any notion of algorithmic stability, which is known to imply strong generalization bounds in adaptive data analysis, and thus our results have applications even when privacy is not a primary concern.

Subfields: Statistics and Probability, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Recent advances in differential privacy for dynamic databases and time series data [125, 124, 89] have all assumed the existence of a trusted curator who can see raw data as they arrive online, and publish dynamically updated statistics.”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “We deﬁne two distributions D 0 and D 1 where under D 1 we have Pr The work of Cannone et al. [18] gives tight sample complexity bounds for private hypothesis testing in the curator model.”
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation (2019, background): “Mean estimation also naturally arises in hypothesis testing [33, 18, 7, 9, 10, 8].”
Private Hypothesis Selection (2019, background): “[24], which focuses on the case of private simple hypothesis testing.”
Profile-based Privacy for Locally Private Computations (2019, background): “This distinction in goal also applies with respect to the distributional privacy framework [2] and in the explorations of [3] into general privatized hypothesis testing.”
The Role of Interactivity in Local Differential Privacy (2019, methodology): “[10] study simple hypothesis testing under the centralized model of differential privacy, and Theorem 1 of Duchi et al.”