Private False Discovery Rate Control

By Cynthia Dwork, Weijie Su, Li Zhang. 2015

28 citations recorded by the source corpus.

We provide the first differentially private algorithms for controlling the false discovery rate (FDR) in multiple hypothesis testing, with essentially no loss in power under certain conditions. Our general approach is to adapt a well-known variant of the Benjamini-Hochberg procedure (BHq), making each step differentially private. This destroys the classical proof of FDR control. To prove FDR control of our method, (a) we develop a new proof of the original (non-private) BHq algorithm and its robust variants -- a proof requiring only the assumption that the true null test statistics are independent, allowing for arbitrary correlations between the true nulls and false nulls. This assumption is fairly weak compared to those previously shown in the vast literature on this topic, and explains in part the empirical robustness of BHq. Then (b) we relate the FDR control properties of the differentially private version to the control properties of the non-private version. \end{enumerate} We also present a low-distortion "one-shot" differentially private primitive for "top $k$" problems, e.g., "Which are the $k$ most popular hobbies?" (which we apply to: "Which hypotheses have the $k$ most significant $p$-values?"), and use it to get a faster privacy-preserving instantiation of our general approach at little cost in accuracy. The proof of privacy for the one-shot top~$k$ algorithm introduces a new technique of independent interest.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

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

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Tight Lower Bounds for Locally Differentially Private Selection (2018, background): “ous application: PAC learning [KLN+08], synthetic data generation [BLR13], frequent itemset mining [BLST10], feature selection and sparse regression [TS13, TTZ15, LCS+16], multiple hypothesis testing [DSZ15], and many more. For all of these problems, the best algorithms in the local model require an”
Tight Lower Bounds for Differentially Private Selection (2017, background): “A recent work by Dwork, Su, and Zhang [DSZ15] introduced the problem of privately controlling the false discovery rate.”
Private selection from private candidates (2018, background): “Some examples include private PAC learning [20], private frequent itemset mining [4], private PCA [7, 19] and private multiple hypothesis testing [14, 35].”
Differentially private model selection with penalized and constrained likelihood (2016, background): “, 2014; Karwa and Slavković, 2016), non-parametric density estimation (Wasserman and Zhou, 2010), hypothesis testing (Fienberg et al., 2011; Johnson and Shmatikov, 2013; Uhler et al., 2013; Yu et al., 2014; Karwa et al., 2014; Solea, 2014; Dwork et al., 2015; Sheffet, 2015; Wang et al., 2015; Gaboar”
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing (2016, background): “I ∞,P (A, n) ≤ log(e) · ( (2)n/2 + √ n ln(2/β)/2 ) This connection is powerful, because there are a vast collection of data analyses for which we have differentially private algorithms— including a growing literature on differentially private hypothesis tests [12, 13, 14, 15, 16, 17, 18, 19].”
Locally Private Hypothesis Testing (2018, background): “Several works have looked at the intersection of differential privacy and statistics (Dwork & Lei, 2009; Smith, 2011; Chaudhuri & Hsu, 2012; Duchi et al., 2013a; Dwork et al., 2015) mostly focusing on robust statistics; but only a handful of works study rigorously the significance and power of hypot”
Statistical Approximating Distributions Under Differential Privacy (2018, background): “…Karwa, 2016, D’Orazio et al., 2015, Sheffet, 2015, Rogers and Kifer, 2017, Uhler et al., 2013, Yu et al., 2014, Smith, 2011, Vu and Slavkovic, 2009, Dwork et al., 2015, Solea, 2014, Karwa and Slavkovic, 2016, Johnson and Shmatikov, 2013] on how to properly incorporate differential Key words and…”
Revisiting Differentially Private Hypothesis Tests for Categorical Data (2015, background): “Dwork et al. (2015) presented a framework for controlling the false discovery rate of a large sequence of hypothesis tests.”
Locally Private Mean Estimation: Z-test and Tight Confidence Intervals (2018, background): “Several works have studied the intersection of differential privacy and statistics (Dwork and Lei, 2009; Smith, 2011; Chaudhuri and Hsu, 2012; Duchi et al., 2013a,b; Dwork et al., 2015) mostly focusing on robust statistics; but only a handful of works study rigorously the significance and power of h”