Test without Trust: Optimal Locally Private Distribution Testing

By Jayadev Acharya, Clément Louis Canonne, Cody R. Freitag, Himanshu Tyagi. 2018

64 citations recorded by the source corpus.

We study the problem of distribution testing when the samples can only be accessed using a locally differentially private mechanism and focus on two representative testing questions of identity (goodness-of-fit) and independence testing for discrete distributions. First, we construct tests that use existing, general-purpose locally differentially private mechanisms such as the popular RAPPOR or the recently introduced Hadamard Response for collecting data and show that our proposed tests are sample optimal, when we insist on using these mechanisms. Next, we allow bespoke mechanisms designed specifically for testing and introduce the Randomized Aggregated Private Testing Optimal Response (RAPTOR) mechanism which is remarkably simple and requires only one bit of communication per sample. We show that our proposed mechanism yields sample-optimal tests, and in particular outperforms any test based on RAPPOR or Hadamard response. A distinguishing feature of our optimal mechanism is that, in contrast to existing mechanisms, it uses public randomness.

Subfields: Artificial Intelligence, Computer Science Applications

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 Computer Science Applications

Citations in the corpus

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.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “who can then transmit it, causing an increased communication cost from the users. The complementary problem of hypothesis testing has also been studied in the locally diﬀerentially private setting in [39,40,41], where the goal is to test whether the data samples are generated from one class of distr”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, background): “[3]) to reduce the sample complexity dependence on k from k3/4 to k2/3.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Note that the special case of L = 2 was proven in the extended abstract [2], in a similar fashion.”
INSPECTRE: Privately Estimating the Unseen (2018, methodology): “, 2017; Acharya et al., 2018b; Aliakbarpour et al., 2018; Acharya et al., 2019c). We also provide lower bounds, showing that our upper bounds are almost tight. A more formal statement of our results appears in Section 2. Experimental Results. We demonstrate the efficacy of our method with experiment”
The Role of Interactivity in Local Differential Privacy (2019, background): “[1, 2] gives a qualitatively different separation between the private-coin and public-coin models of noninteractive local privacy.”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, background): “Besides the standard estimation problem, one can also consider the problem of estimating succinct histograms, or heavy hitters; see, for example, Bassily and Smith [2015]. Compared with estimation problems, hypothesis testing is relatively under-explored in the setting of local differential privacy.”
Locally Private Mean Estimation: Z-test and Tight Confidence Intervals (2018, methodology): “Recent work from Acharya et al. (2018a) improves on the sample complexity bounds in Sheffet (2018) and consider the setting where access to public randomness is allowed. There is also work from Kairouz et al. (2016) on estimating distributions for categorical data in the local privacy model. Finally”
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.”
Two Party Distribution Testing: Communication and Security (2018, background): “More recently, a more stringent model of Locally Diﬀerentially Private Testing was proposed [She18, ACFT18].”
Manipulation Attacks in Local Differential Privacy (2019, methodology): “We consider the RAPTOR protocol, introduced by Acharya et al. (2019).”
Pan-Private Uniformity Testing (2019, methodology): “Finally, we note that these results add to lines of work conceptually connecting restricted memory to pan-privacy [26, 36] and connecting restricted communication to local privacy [33, 5, 22, 6, 31].”
On the Power of Multiple Anonymous Messages (2019, unknown): “…much less error than what is possible in the local model could lead to more accurate and eﬃcient shuﬄe model protocols for fundamental primitives such as clustering [91] and distribution testing [1], for which current locally diﬀerentially private protocols use frequency estimation as a black box.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “A preliminary version of this work containing partial results appeared in the Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019 [1].”
Distributed Signal Detection under Communication Constraints (2020, methodology): “Speciﬁcally, recent work (Acharya et al., 2018, 2019c) has shown that, in the same communication-constrained setting as ours, the task of testing whether an unknown distribution over a domain of size k is (i) uniform, or (ii) ε -far from uniform in total variation distance, requires n = Θ( k 3 / 2…”
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].”
Differentially Private Assouad, Fano, and Le Cam (2020, unknown): “We believe fingerprinting and DP Assouad’s lemma are both powerful tools for proving lower bounds under approximate DP. In estimating Gaussian distributions, fingerprinting provides strong lower bounds under approximate DP, whereas private Assouad’s method gives an additional polynomial blow-up comp”