Inference under Information Constraints III: Local Privacy Constraints
arXiv:2101.07981
Abstract
We study goodness-of-fit and independence testing of discrete distributions in a setting where samples are distributed across multiple users. The users wish to preserve the privacy of their data while enabling a central server to perform the tests. Under the notion of local differential privacy, we propose simple, sample-optimal, and communication-efficient protocols for these two questions in the noninteractive setting, where in addition users may or may not share a common random seed. In particular, we show that the availability of shared (public) randomness greatly reduces the sample complexity. Underlying our public-coin protocols are privacy-preserving mappings which, when applied to the samples, minimally contract the distance between their respective probability distributions.
arXiv commentTo appear in the Special Issue on Privacy and Security of Information Systems of the IEEE Journal on Selected Areas in Information Theory (JSAIT), 2021. Journal version of the AISTATS'19 paper "Test without Trust: Optimal Locally Private Distribution Testing" (arXiv:1808.02174), which it extends and supersedes
References in corpus (7)
- Optimal Algorithms for Testing Closeness of Discrete Distributions
- Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
- Optimal Testing for Properties of Distributions
- Revisiting Differentially Private Hypothesis Tests for Categorical Data
- Test without Trust: Optimal Locally Private Distribution Testing
- Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
- Generalized Error Exponents For Small Sample Universal Hypothesis Testing