In this paper, we give efficient algorithms and lower bounds for solving the heavy hitters problem while preserving differential privacy in the fully distributed local model. In this model, there are n parties, each of which possesses a single element from a universe of size N . The heavy hitters problem is to find the identity of the most common element shared amongst the n parties. In the local model, there is no trusted database administrator, and so the algorithm must interact with each of the n parties separately, using a differentially private protocol. We give tight information-theoretic upper and lower bounds on the accuracy to which this problem can be solved in the local model (giving a separation between the local model and the more common centralized model of privacy), as well as computationally efficient algorithms even in the case where the data universe N may be exponentially large. Consider the problem of a website administrator who wishes to know what his most common traffic sources are. Each of n visitors arrives with a single referring site: the name of the last website that she visited, which is drawn from a vast universe N of possible referring sites (N here is the set of all websites on the internet). There is value in identifying the most popular referring site (the heavy hitter ): the site administrator may be able to better tailor the content of his webpage, or better focus his marketing resources. On the other hand, the identity of each individual's referring site might be embarrassing or otherwise revealing, and is therefore private information. We can therefore imagine a world in which this information must be treated "privately." Moreover, in this situation, visitors are communicating directly with the servers of the websites that they visit: i.e. there is no third party who might be trusted to aggregate all of the referring website data and provide privacy preserving statistics to the website administrator. In this setting, how well can the website administrator estimate the heavy hitter while being able to provide formal privacy guarantees to his visitors? This situation can more generally be modeled as the heavy hitters problem under the constraint of differential privacy. There are n individuals i ∈ [n] each of whom is associated with an element v i ∈ N of some large data universe N . The heavy hitter is the most frequently occurring element x ∈ N among the set {v 1 , . . . , v n }, and we would like to be able to identify that element, or one that occurs almost as frequently as the heavy hitter. Moreover, we wish to solve this problem 1 while preserving differential privacy in the fully distributed (local) model. We define this formally in section 2, but roughly speaking, an algorithm is differentially private if changes to the data of single individuals only result in small changes in the output distribution of the algorithm. Moreover, in the fully distributed setting, each individual (who can be viewed as a database of size 1) must interact with the algorithm independently of all of the other individuals, using a differentially private algorithm. This is in contrast to the more commonly studied centralized model, in which a trusted database administrator may have (exact) access to all of the data, and coordinate a private computation. We study this problem both from an information theoretic point of view, and from the point of view of efficient algorithms. We say that an algorithm for the private heavy hitters problem is efficient if it runs in time poly(n, log N ): i.e. polynomial in the database size, but only polylogarithmic in the universe size (i.e. in what we view as the most interesting range of parameters, the universe may be exponentially larger than the size of the database). We give tight information theoretic upper and lower bounds on the accuracy to which the heavy hitter can be found in the private distributed setting (separating this model from the private centralized setting), and give several efficient algorithms which achieve good, although information-theoretically sub-optimal accuracy guarantees. We leave open the question of whether efficient algorithms can exactly match the information theoretic bounds we prove for the private heavy hitters problem in the distributed setting. In this section, we summarize our results. The bounds we discuss here are informal and hide many of the parameters which we have not yet defined. The formal bounds are given in the main body of the paper. First, we provide an information theoretic characterization of the accuracy to which any algorithm (independent of computational constraints) can solve the heavy hitters problem in the private distributed setting. We say that an algorithm is α-accurate if it returns a universe element which occurs with frequency at most an additive α smaller than the true heavy hitter. In the centralized setting, a simple application of the exponential mechanism [MT07] gives an α-accurate mechanism for the heavy-hitters problem where α = O(log |N |), which in particular, is independent of the number of individuals n. In contrast, we show that in the fully distributed setting, no algorithm can be α-accurate for α = Ω( √ n) even in the case in which |N | = 2. Conversely, we give an almost matching upper bound (and an algorithm with run-time linear in N ) which is α-accurate for α = O( √ n log N ). Next, we consider efficient algorithms which run in time only polylogarithmic in the universe size |N |. Here, we give two algorithms. One is an application of a compressed sensing algorithm of Gilbert et al [GLPS10] , which is α-accurate for α =Õ(n 5/6 log N log log N ). Then, we give an algorithm based on group-testing using pairwise independent hash functions, which has an incomparable bound. Roughly speaking, it guarantees to return the exact heavy hitter (i.e. α = 0) whenever the frequency of the heavy hitter is larger than the ℓ 2 -norm of the frequencies of the remaining elements. Depending on how these frequencies are distributed, this can correspond to a bound of α-accuracy for α ranging anywhere between the optimal α = O( √ n) to α = O(n). 2 Our upper bounds, both information theoretic, and those with efficient algorithms, are based on the general technique of random projection and concentration of measure. To prove our information theoretic upper bound, we observe that to find the heavy hitter, we may view the private database as a histogram v in N dimensional space. Then, it is enough to find the index i ∈ [N ] of the universe element which maximizes v, e i , where e i is the i'th standard basis vector. Both v and each e i have small ℓ 1 -norm, and so each of these inner products can be approximately preserved by taking a random projection intoÕ(log N ) dimensional space. Moreover, we can project each individual's data into this space independently in the fully distributed setting, incurring a loss of only O( √ n) in accuracy. This mechanism, however, is not efficient, because to find the heavy hitter, we must enumerate through all |N | basis vectors e i in order to find the one that maximizes the inner product with the projected database. Similar ideas lead to our efficient algorithms, albeit with worse accuracy guarantees. For example, in our first algorithm, we apply techniques from compressed sensing to the projected database to recover (approximately) the heavy hitter, rather than checking basis vectors directly. In our second algorithm, we take a projection using a particular family of pairwise-independent hash functions, which are linear functions of the data universe elements. Because of this linearity, we are able to efficiently "invert" the projection matrix in order to find the heavy hitter. Our lower bound separates the distributed setting from the centralized setting by applying an anti-concentration argument. Roughly speaking, we observe that in the fully distributed setting, if individual data elements were selected uniformly i.i.d. from the data universe N , then even after conditioning on the messages exchanged with any differentially private algorithm, they remain independently distributed, and approximately uniform. Therefore, by the Berry-Esseen theorem, even after any algorithm computes its estimate of the heavy hitter, the true distribution over counts remains approximately normally distributed. Since the Gaussian distribution exhibits strong anticoncentration properties, this allows us to unconditionally give an Ω( √ n) lower bound for any algorithm in the fully distributed setting. Differential privacy was introduced in a sequence of papers culminating in [DMNS06] , and has since become the standard "solution concept" for privacy in the theoretical computer science literature. There is by now a very large literature on this topic, which is too large to summarize here. Instead, we focus only on the most closely related work, and refer the curious reader to a survey of Dwork [Dwo08] . Most of the literature on differential privacy focuses on the centralized model, in which there is a trusted database administrator. In this paper, we focus on the local or fully distributed model, introduced by [KLN + 08], in which each individual holds their own data (i.e. there are n databases, each of size 1), and the algorithm must interact with each one in a differentially private manner. There has been little work in this more restrictive model-the problems of learning [KLN + 08] and query release [GHRU11] in the local model are well understood 1 , but only up to polynomial factors 1 Roughly, the set of concepts that can be learned in the local model given polynomial sample complexity is equal to the set of concepts that can be learned in the SQ model given polynomial query complexity [KLN + 08], and the set of queries that can be released in the local model given polynomial sample complexity is equal to the set of concepts that can be agnostically learned in the SQ model given polynomial query complexity [GHRU11], but the polynomials
Finally, our efficient protocols are based on ideas from the large literature on streaming algorithms and compressive sensing (as were the efficient protocols of Hsu et al. REF ).
Distributed Private Heavy Hitters
ArXiv
ArXiv
Computer Science