Test without Trust: Optimal Locally Private Distribution Testing
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. We are concerned with two settings: First, when we insist on using an already deployed, general-purpose locally differentially private mechanism such as the popular RAPPOR or the recently introduced Hadamard Response for collecting data, and must build our tests based on the data collected via this mechanism; and second, when no such restriction is imposed, and we can design a bespoke mechanism specifically for testing. For the latter purpose, we introduce the Randomized Aggregated Private Testing Optimal Response (RAPTOR) mechanism which is remarkably simple and requires only one bit of communication per sample. We propose tests based on these mechanisms and analyze their sample complexities. Each proposed test can be implemented efficiently. In each case (barring one), we complement our performance bounds for algorithms with information-theoretic lower bounds and establish sample optimality of our proposed algorithm. A peculiar feature that emerges is that our sample-optimal algorithm based on RAPTOR uses public-coins, and any test based on RAPPOR or Hadamard Response, which are both private-coin mechanisms, requires significantly more samples.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Instance-Optimal Differentially Private Estimation
In this work, we study local minimax convergence estimation rates subject to $\epsilon$-differential privacy. Unlike worst-case rates, which may be conservative, algorithms that are locally minimax optimal must adapt to …
Locally Private Sampling with Public Data
Local differential privacy (LDP) is increasingly employed in privacy-preserving machine learning to protect user data before sharing it with an untrusted aggregator. Most LDP methods assume that users possess only a sing…
Privacy PreservingDifferentially Private Verification of Distribution Properties
A recent line of work initiated by Chiesa and Gur and further developed by Herman and Rothblum investigates the sample and communication complexity of verifying properties of distributions with the assistance of a powerf…
Local Private Hypothesis Testing: Chi-Square Tests
The local model for differential privacy is emerging as the reference model for practical applications of collecting and sharing sensitive information while satisfying strong privacy guarantees. In the local model, …
Two-sample testingSamplable Anonymous Aggregation for Private Federated Data Analysis
We revisit the problem of designing scalable protocols for private statistics and private federated learning when each device holds its private data. Locally differentially private algorithms require little trust but are…
Federated Learning