Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication

Abstract

We study the problem of estimating $k$-ary distributions under $\epsilon$-local differential privacy. $n$ samples are distributed across users who send privatized versions of their sample to a central server. All previously known sample optimal algorithms require linear (in $k$) communication from each user in the high privacy regime $(\epsilon =O(1))$, and run in time that grows as $n\cdot k$, which can be prohibitive for large domain size $k$. We propose Hadamard Response (HR}, a local privatization scheme that requires no shared randomness and is symmetric with respect to the users. Our scheme has order optimal sample complexity for all $\epsilon$, a communication of at most $\log k+2$ bits per user, and nearly linear running time of $\tilde{O}(n+k)$. Our encoding and decoding are based on Hadamard matrices, and are simple to implement. The statistical performance relies on the coding theoretic aspects of Hadamard matrices, ie, the large Hamming distance between the rows. An efficient implementation of the algorithm using the Fast Walsh-Hadamard transform gives the computational gains. We compare our approach with Randomized Response (RR), RAPPOR, and subset-selection mechanisms (SS), both theoretically, and experimentally. For $k=10000$, our algorithm runs about 100x faster than SS, and RAPPOR.

Cited by in corpus (30)

• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]
• Breaking the Communication-Privacy-Accuracy Trilemma
• Successive Point-of-Interest Recommendation with Local Differential Privacy
• Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy
• On the Power of Multiple Anonymous Messages
• Locally Differentially Private Frequency Estimation with Consistency
• Learning discrete distributions: user vs item-level privacy
• Federated Heavy Hitters Discovery with Differential Privacy
• Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs
• Locally Differentially Private Analysis of Graph Statistics
• Private Identity Testing for High-Dimensional Distributions
• Locality Sensitive Hashing with Extended Differential Privacy
• Differentially Private Assouad, Fano, and Le Cam
• Context-Aware Local Differential Privacy
• Lossless Compression of Efficient Private Local Randomizers
• Continuous Release of Data Streams under both Centralized and Local Differential Privacy
• Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming
• Linear and Range Counting under Metric-based Local Differential Privacy
• Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
• Statistical Inference in the Differential Privacy Model
• Communication-Efficient Triangle Counting under Local Differential Privacy
• Improving Utility and Security of the Shuffler-based Differential Privacy
• Answering Multi-Dimensional Range Queries under Local Differential Privacy
• Privately Learning Mixtures of Axis-Aligned Gaussians
• Improving Frequency Estimation under Local Differential Privacy
• Optimal locally private estimation under ${\ell }_p$ loss for $1\le p\le 2$
• Optimal Compression of Locally Differentially Private Mechanisms
• Pointwise Bounds for Distribution Estimation under Communication Constraints
• Inference under Information Constraints III: Local Privacy Constraints