The structure of optimal private tests for simple hypotheses

DOI10.1145/3313276.3316336MaRDI QIDQ5212772zbMATH OpenOpenAlexFDO

Authors

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.11148

zbMATH Keywords

differential privacyhypothesis testing

Mathematics Subject Classification ID

Parametric hypothesis testing (62F03) Privacy of data (68P27)

Abstract: 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 $varepsilon$, how many i.i.d. samples are needed to distinguish $P$ from $Q$ subject to $varepsilon$-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 $varepsilon$, 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.

Recommendations

• Asymptotically Optimal and Private Statistical Estimation
• Testing the Lipschitz property over product distributions with applications to data privacy
• Minimax Optimal Procedures for Locally Private Estimation
• Sample-optimal identity testing with high probability
• Privacy-preserving statistical estimation with optimal convergence rates

Cited in

(11)

• Testing the Lipschitz property over product distributions with applications to data privacy
• Single and multiple change-point detection with differential privacy
• Structure and sensitivity in differential privacy: comparing \(K\)-norm mechanisms
• Privacy-preserving parametric inference: a case for robust statistics
• Canonical noise distributions and private hypothesis tests
• On robustness and local differential privacy
• On the power of private likelihood-ratio tests for goodness-of-fit in frequency tables
• Unbiased statistical estimation and valid confidence intervals under differential privacy
• Mechanisms for global differential privacy under Bayesian data synthesis
• Differentially private Assouad, Fano, and Le Cam
• Differentially private learning beyond the classical dimensionality regime

This page was built for publication: The structure of optimal private tests for simple hypotheses

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212772)