Priv'IT: Private and Sample Efficient Identity Testing

By Bryan Cai, Constantinos Daskalakis, Gautam Kamath. 2017

56 citations recorded by the source corpus.

We develop differentially private hypothesis testing methods for the small sample regime. Given a sample $\cal D$ from a categorical distribution $p$ over some domain $\Sigma$, an explicitly described distribution $q$ over $\Sigma$, some privacy parameter $\varepsilon$, accuracy parameter $\alpha$, and requirements $\beta_{\rm I}$ and $\beta_{\rm II}$ for the type I and type II errors of our test, the goal is to distinguish between $p=q$ and $d_{\rm{TV}}(p,q) \geq \alpha$. We provide theoretical bounds for the sample size $|{\cal D}|$ so that our method both satisfies $(\varepsilon,0)$-differential privacy, and guarantees $\beta_{\rm I}$ and $\beta_{\rm II}$ type I and type II errors. We show that differential privacy may come for free in some regimes of parameters, and we always beat the sample complexity resulting from running the $\chi^2$-test with noisy counts, or standard approaches such as repetition for endowing non-private $\chi^2$-style statistics with differential privacy guarantees. We experimentally compare the sample complexity of our method to that of recently proposed methods for private hypothesis testing.

Subfields: Artificial Intelligence

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

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “[16], studies the minimax sample complexity of private hypothesis testing.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, background): “At a high level, our protocol imitates the pan-private uniformity tester of Amin et al. [5] (which itself imitates a centrally private uniformity tester suggested by Cai et al. [14]).”
Differentially Private Chi-squared Test by Unit Circle Mechanism (2017, background): “Also recently, there is a study for the differential privacy of χ2 test of identity, which ensures type-I and typ-II error (Cai et al., 2017).”
Statistical Approximating Distributions Under Differential Privacy (2018, background): “…statistical tests and confidence intervals with improved performance [Johnson and Shmatikov, 2013, Uhler et al., 2013, Solea, 2014, Yu et al., 2014, Sheffet, 2015, Gaboardi et al., 2016, Rogers and Kifer, 2017, Karwa, 2016, Karwa and Slavkovic, 2016, D’Orazio et al., 2015, Cai et al., 2017].”
Differentially Private Identity and Equivalence Testing of Discrete Distributions (2018, methodology): “We remind the reader that (Cai et al., 2017) does not consider the more general problem of equivalence testing, and that ours are the first results in this setting.”
INSPECTRE: Privately Estimating the Unseen (2018, background): “Indeed, for many fundamental tasks, optimal algorithms for the nonprivate setting may be highly sensitive, thus necessitating crucial modifications to obtain differential privacy (Acharya et al., 2015; Cai et al., 2017).”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, methodology): “The work most closely related to ours is in [CDK17], which studied identity testing in the ﬁnite sample regime.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “Under the notion of (global) differential privacy (DP) [28], identity testing has been considered in [11], [20], with a complete characterization of the sample complexity derived in [8].”
Pan-Private Uniformity Testing (2019, methodology): “Inspired by similar statistics in non-private testing [3, 15, 2], Cai et al. [12] originally studied Z ′ for centrally private identity testing.”
Differentially Private Identity and Closeness Testing of Discrete Distributions (2017, background): “[5] do not consider the more general problem of closeness testing.”
Differentially Private Assouad, Fano, and Le Cam (2020, background): “Previous literature has studied various problems and established utility privacy trade-off bounds, including distribution estimation, hypothesis testing, property estimation, empirical risk minimization, etc (Chaudhuri et al., 2011; Lei, 2011; Bassily et al., 2014; Diakonikolas et al., 2015; Cai et ”
Test without Trust: Optimal Locally Private Distribution Testing (2018, background): “Identity testing in the finite sample setting has been considered in [10, 7], with a complete characterization of sample complexity derived in [6].”
Finite Sample Differentially Private Confidence Intervals (2017, methodology): “(2005); Schafer and Stark (2009) for the problem of estimating a minimax confidence interval for the bounded normal mean, and Casella and Strawderman (1981); Bickel et al.”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, background): “The problem has also been considered in the non-local diﬀerentially private setting [Wang et al., 2015, Gaboardi et al., 2016, Cai et al., 2017, Aliakbarpour et al., 2018, Acharya et al., 2018].”
Local Private Hypothesis Testing: Chi-Square Tests (2017, methodology): “Following these works, there has also been general work in private chi-square hypothesis tests, where the main tests are for goodness of fit and independence testing, although some do extend to more general tests (Wang et al., 2015; Gaboardi et al., 2016; Kifer & Rogers, 2017; Cai et al., 2017; Kaki”