Local, Private, Efficient Protocols for Succinct Histograms

By Raef Bassily, Adam D. Smith. 2015

511 citations recorded by the source corpus.

We give efficient protocols and matching accuracy lower bounds for frequency estimation in the local model for differential privacy. In this model, individual users randomize their data themselves, sending differentially private reports to an untrusted server that aggregates them. We study protocols that produce a succinct histogram representation of the data. A succinct histogram is a list of the most frequent items in the data (often called "heavy hitters") along with estimates of their frequencies; the frequency of all other items is implicitly estimated as 0. If there are n users whose items come from a universe of size d, our protocols run in time polynomial in n and log(d). With high probability, they estimate the accuracy of every item up to error O(√{log(d)/(ε2n)}). Moreover, we show that this much error is necessary, regardless of computational efficiency, and even for the simple setting where only one item appears with significant frequency in the data set. Previous protocols (Mishra and Sandler, 2006; Hsu, Khanna and Roth, 2012) for this task either ran in time Ω(d) or had much worse error (about √[6]{log(d)/(ε2n)}), and the only known lower bound on error was Ω(1/√{n}). We also adapt a result of McGregor et al (2010) to the local setting. In a model with public coins, we show that each user need only send 1 bit to the server. For all known local protocols (including ours), the transformation preserves computational efficiency.

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

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “On the other hand, the smallest possible error in local DP is Θ(min( √ n logB ε , n)) provided δ 1/n (Bassily & Smith, 2015).”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “The adoption of the local model by major industry players has motivated a line of research in the theory of local di ﬀ erential privacy (e.g., [9, 8, 16, 59, 40, 42, 41]).”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, it is well understood theoretically and empirically that utility outcomes are far worse in the LM than in the TCM [11, 16, 22, 27, 38].”
Distributed Differential Privacy via Shuffling (2018, background): “We would like to find the minimum n such that a differentially private algorithm can solve the histogram problem; the following lower bound for locally differentially private protocols for histograms is from [3].”
Differentially-Private "Draw and Discard" Machine Learning (2018, background): “Since the focus on differentially private computations in the local model is recent, most, if not all, efforts to date have been limited to learning aggregate statistics, rather than trainng more complex machine learning models [18], [2], [5], [4], [7].”
Collecting Telemetry Data Privately (2017, methodology): “Our mechanisms are inspired by those in [19, 8, 7, 4], but allow for considerably simpler descriptions and implementations.”
Marginal Release Under Local Differential Privacy (2017, background): “The state of art asymptotic lower bound and matching algorithm are due to Bassily and Smith [4].”
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “ticularly among practitioners [17, 35], fewer such algorithms are known [40, 19, 8, 13, 5].”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “Instead, we use a simplified version of a data structure of Bassily and Smith [7].”
Discrete Distribution Estimation under Local Privacy (2016, background): “There is a rich literature on distribution estimation under local privacy (Chan et al., 2012; Hsu et al., 2012; Bassily & Smith, 2015), of which several works are particularly relevant herein.”
Heavy Hitters and the Structure of Local Privacy (2017, methodology): “Speciﬁcally, building on a transformation of Bassily and Smith [4], we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol with the same utility guarantees.”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, methodology): “, about adaptivity [3], [14], sketching [1], [18], [15], [16], or succinctness of communication [15], [16], [19]).”