Heavy Hitters and the Structure of Local Privacy

By Mark Bun, Jelani Nelson, Uri Stemmer. 2017

166 citations recorded by the source corpus.

We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates which depend optimally on the number of users, the size of the domain, and the privacy parameter, but depend sub-optimally on the failure probability. We strengthen existing lower bounds on the error to incorporate the failure probability, and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters. (1) Advanced Grouposition: In the local model, group privacy for k users degrades proportionally to root k, instead of linearly in k as in the central model. Stronger group privacy yields improved max-information guarantees, as well as stronger lower bounds (via "packing arguments"), over the central model. (2) Building on a transformation of Bassily and Smith (STOC 2015), we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol. Again in contrast with the central model, this shows that we cannot obtain more accurate algorithms by moving from pure to approximate local privacy.

Subfields: Artificial Intelligence, Privacy & Security, Algorithms & Complexity

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 Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “Frequency estimation is also closely related to heavy hitter estimation [10], [13], [17], [36], [37], [38], [39], where the goal is to discover symbols that appear frequently in a given data set and estimate their frequencies.”
Pure Differentially Private Summation from Anonymous Messages (2020, background): “In the central and local settings, several prior works either obtained pure protocols in regimes where approximate protocols were previously known, or proved separations between pure and approximate protocols (e.g., [HT10, De12, NTZ13, SU15, BNS18]).”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “…follows: In the ﬁrst round the local agents send messages according to the ε -di ﬀ erentially private heavy hitters protocol of Theorem 2.18 (from [16]) with the inputs ( t,s t ) and β/ 3, that is, a protocol that returns with probability at least 1 − β/ 3 all values that are inputs of “many”…”
Distributed Differential Privacy via Shuffling (2018, methodology): “To complete the proof, we use (a slight generalization of) a transformation of Bun, Nelson, and Stemmer [7] to turn R into a related algorithm R′ satisfying (8(εS + lnn), 0)-differential privacy with only a slight loss of accuracy.”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “Various data analytics and machine learning problems have been studied under LDP, such as probability distribution estimation [15], [23], [30], [32], [42], heavy hitter discovery [4], [7], [33], [39], frequent new term discovery [37], frequency estimation [5], [38], frequent itemset mining [40], mar”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “As demonstrated empirically in Section VII, we ﬁnd that sampling is always better for the privacy/utility tradeoff (thereby, we verify what has been shown analytically [16], [27]).”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, methodology): “We note that the literature on heavy hitter estimation has mostly considered schemes with shared randomness [8, 7, 11], and it will be interesting to see if our methods can provide improved algorithms for the heavy hitter problem.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, methodology): “The problem of frequency/heavy hitter detection under εLDP has also received great attention (Hsu et al., 2012; Erlingsson et al., 2014; Bassily & Smith, 2015; Qin et al., 2016; Bassily et al., 2017; Ding et al., 2017; Bun et al., 2018).”
Privacy at Scale: Local Differential Privacy in Practice (2018, background): “Several works on LDP have started to appear in the theory literature, addressing questions about the power of LDP [3, 4, 11]: what are the lower bounds on the accuracy guarantees (as a function of privacy parameter and population size); is there any benefit from adding an additive “relaxation” δ to ”
Locally Differentially Private Data Collection and Analysis (2019, background): “Current researches focus on many related problems under the LDP model, such as mean/frequency estimation [15, 39, 48], probability distribution estimation [22, 56, 47], heavy hitter identification [5, 41, 8], itemset mining [50], marginal distribution release [12, 60], and empirical risk minimizatio”
The power of factorization mechanisms in local and central differential privacy (2019, methodology): “ γ2 norm. As sketched in the introduction, this can be achieved via a local version of the Gaussian noise mechanism, which can then be transformed into a purely private mechanism using the results of [BNS18]. This gives, however, a slightly suboptimal bound, and, instead, we use the local randomizer”
Answering Multi-Dimensional Analytical Queries under Local Differential Privacy (2019, background): “LDP mechanisms. e.g. e.g. other tasks, e.g. , finding heavy hitters [4, 6, 36], frequent item-set works [9, 12, 13], as we also support AVG aggregation function Releasing marginals privately.”
On the Power of Multiple Anonymous Messages (2019, unknown): “2-heavy hitters, namely those jsuch that ° n i1 px iq j¥ 2, in time OpTBq, by querying ApFO;1q;:::;ApFO;Bq. (See the remark after Theorem 3.6.) 3 Frequency oracle and heavy hitters Most prior work [7, 6, 11] has focused on the case of computing heavy hitters when each user holds only a single elemen”
On the Round Complexity of the Shuffle Model (2020, unknown): “the public channel to execute a 1-round (ε,0)-diﬀerentially private protocol in the local model for histograms over the (distributed) database Y = (y1,y2,...,yn) with failure probability δ (see e.g., [12], or Theorem B.2). This results in a data structure D (known to all parties) that gives estimati”
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints (2021, methodology): “See, for instance Table 1 in (Bun et al., 2019), where we pick ε = Θ(1), β = Θ(1/n) and |X| = d to translate to our settings. where in the last inequality we choose n1 = n/2 and assume n d 2 log2 d 2b .”
The Role of Interactivity in Local Differential Privacy (2019, background): “As previous work [7, 10] has established that (ε, 0)- and (ε, δ)-local privacy are approximately equivalent for reasonable parameter ranges, our lower bound also holds for sequentially interactive (ε, δ)-locally private protocols.”