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

By Jayadev Acharya, Ziteng Sun, Huanyu Zhang. 2018

173 citations recorded by the source corpus.

We study the problem of estimating $k$-ary distributions under $\varepsilon$-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 $(\varepsilon=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 $\varepsilon$, 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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Science Applications, Privacy & Security

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 Networks and Communications

In Computer Science Applications

In Privacy & Security

Citations in the corpus

Learning discrete distributions: user vs item-level privacy (2020, background): “…with local diﬀerential privacy [Duchi et al., 2013, Kairouz et al., 2016, Acharya et al., 2019a, Ye and Barg, 2018], with global diﬀerential privacy [Diakonikolas et al., 2015, Acharya et al., 2020], and with communication constraints [Barnes et al., 2019, Acharya et al., 2019a], among others.”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “If we further assume X are drawn from some discrete distribution p, then the problem falls into distribution estimation under local differential privacy [9], [13], [34], [36], [42], [43], [44], [45], [46] and limited communication [11], [25], [45], [46], [47], [48], [49], [50].”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, background): “Distribution learning under LDP constraints has been studied in [4], [21], [37], [52], [56], all providing sample-optimal schemes with different merits.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, methodology): “And the communication complexity is only one bit while the least among others is Ω(log k ) bits [33].”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “Hadamard Response and its one-bit variant are proposed in [9], [7].”
Private Hypothesis Selection (2019, background): “There has also been a great deal of work on distribution learning in the local model of diﬀerential privacy [DJW13, WHW + 16, KBR16, ASZ19, DR18, JKMW18, YB18, GRS19].”
Differentially private anonymized histograms (2019, background): “The second model is local DP, where ✏-DP is guaranteed for each individual user’s data [35, 36, 37, 38, 39].”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “For ̺ > 1 (low-privacy regime), our bound matches the upper bound for the noninteractive case, established in [33, 5], showing that even in this lowprivacy regime interactivity cannot lead to better rates, except maybe up to constant factors.”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, background): “There have been several LDP frequency oracles [1, 4, 5, 9, 13, 16, 35] proposed.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “We refer to [13] for a general treatment of estimation problems under locally differentially private (LDP) constraints, while optimal schemes (and lower bounds) for estimating discrete distributions are proposed in [14], [15], [16], [17].”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “There has also been a great deal of work on distribution learning in the local model of differential privacy [29, 65, 45, 2, 30, 44, 67, 37].”
On the Power of Multiple Anonymous Messages (2019, unknown): “Thus, shuﬄed versions of the B -randomized response [97,3], RAPPOR [55,42,3], the Bassily–Smith protocol [12], TreeHist and Bitstogram [11], and the Hadamard response protocol [3,2], will still incur an error of Ω p min p 4 ? n ?”