Locally Private Hypothesis Testing

By Or Sheffet. 2018

56 citations recorded by the source corpus.

We initiate the study of differentially private hypothesis testing in the local-model, under both the standard (symmetric) randomized-response mechanism (Warner, 1965, Kasiviswanathan et al, 2008) and the newer (non-symmetric) mechanisms (Bassily and Smith, 2015, Bassily et al, 2017). First, we study the general framework of mapping each user's type into a signal and show that the problem of finding the maximum-likelihood distribution over the signals is feasible. Then we discuss the randomized-response mechanism and show that, in essence, it maps the null- and alternative-hypotheses onto new sets, an affine translation of the original sets. We then give sample complexity bounds for identity and independence testing under randomized-response. We then move to the newer non-symmetric mechanisms and show that there too the problem of finding the maximum-likelihood distribution is feasible. Under the mechanism of Bassily et al (2007) we give identity and independence testers with better sample complexity than the testers in the symmetric case, and we also propose a $\chi^2$-based identity tester which we investigate empirically.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

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 Electrical and Electronic Engineering

Citations in the corpus

Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, positive): “We remark that distributed uniformity testing under LDP constraints has been studied recently in [46], however the lower bounds derived there are significantly weaker than what we obtain.”
The structure of optimal private tests for simple hypotheses (2018, background): “Another related area [1, 41, 66] studies hypothesis testing in the local model of differential privacy.”
Local Private Hypothesis Testing: Chi-Square Tests (2017, background): “Independent of this work, another paper (Sheffet, 2018) has addressed local private hypothesis testing.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “Unfortunately, it was shown in [44] that the sample complexity of any test relying on this scheme is (k5/2/ε2ρ2), far from optimal.”
Locally Private Mean Estimation: Z-test and Tight Confidence Intervals (2018, background): “Gaboardi and Rogers (2018) and Sheffet (2018) study the asymptotic power and the sample complexity (respectively) of a variety of chisquared based hypothesis tests in the local model.”
Locally Private Gaussian Estimation (2018, background): “In local differential privacy, several recent works have studied related statistical tasks like identity and independence testing [2, 17, 24], albeit restricted to discrete distributions.”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, background): “It has been known since Valiant and Valiant [2014], see also Balakrishnan and Wasserman [2018], that in the direct setup a weighted `2-test is needed in order to attain the optimal rates.”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, background): “…speciﬁcally identity testing, was studied in the locally differentially private (LDP) setting by Gaboardi and Rogers [GR18] and Sheffet [She18], followed by [ACFT19]; and in the communication-constrained setting in [ACT19c, ACT19b], as well as by (with a slightly different focus)…”
Optimal Noise-Adding Mechanism in Additive Differential Privacy (2018, methodology): “…(Duchi et al., 2012), deep learning (Shokri and Shmatikov, 2015; Abadi et al., 2016; Phan et al., 2016; Agarwal et al., 2018), hypothesis testing (Sheffet, 2018), matrix completion (Jain et al., 2018), expectation maximization (Park et al., 2017), and principal component analysis (Chaudhuri et…”
Differentially Private Testing of Identity and Closeness of Discrete Distributions (2017, background): “There has been a line of research for statistical testing and estimation problems under the notion of local differential privacy [57, 28, 34, 50, 40, 58, 63, 6, 53, 1].”
Test without Trust: Optimal Locally Private Distribution Testing (2018, background): “However, [22] did not consider finite sample performance analysis and the sample complexity upper bounds shown in [31] are far from optimal.”