Practical Locally Private Heavy Hitters
We present new practical local differentially private heavy hitters algorithms achieving optimal or near-optimal worst-case error -TreeHist and Bitstogram. In both algorithms, server running time isÕ(n) and user running time isÕ(1), hence improving on the prior state-of-the-art result of Bassily and Smith [STOC  2015] requiringÕ(n 5/2 ) server time andÕ(n 3/2 ) user time. With a typically large number of participants in local algorithms (n in the millions), this reduction in time complexity, in particular at the user side, is crucial for the use of such algorithms in practice. We implemented Algorithm TreeHist to verify our theoretical analysis and compared its performance with the performance of Google's RAPPOR code.
Private Heavy Hitters is the following problem: a set of n users each has an
element from a universe of size d. The goal is to find the elements that occur
(approximately)
most frequently, but do so under a local differential privacy constraint.
This is immensely useful subroutine, which can be used, e.g. to estimate the
common home pages of users of a browswer, or words commonly used by users of a
phone. In fact, this is the functionality implemented by the RAPPOR system in
chrome, and more recently in use in iphones.
To make things a bit more formal, there is an a desired privacy level that
determines how well one can solve this problem. A \gamma-approximate heavy
hitters algorithm outputs a set of elements that contains most elements with
true relative frequency at least 2\gamma and a negligible number of elements with
relative frequency less than \gamma. The best achievable accuracy is \sqrt{n log
d}/eps, and Bassily and Smith showed matching lower and upper bounds. In that
work, this was achieved at a server processing cost of n^{5/2}. This work gives
two more practical algorithms that achieve the same gamma with a server
processing cost of approximately n^{3/2}.
On the positive side, this is an important problem and algorithms for this
problem are already in largescale use. Thus advances in this direction are
valuable.
On the negative side, in most applications, the target gamma is a separate
parameter (see more detailed comment below) and it would be much more accurate
to treat it as such and present and compare bounds in terms of n, d and gamma.
Clarifying these dependencies better would make the work more relevant and
usable.
Detailed comment:
In practice, the goal is usually to collect several statistics at a small
privacy cost. So a target eps, of say 1, is split between several different
statstics, so that the target gamma is not \sqrt{n log d}/eps, but \sqrt{n log
d}/ k\eps, when we want to collect k statistics. Often this k itself is
determined based on what may be achievable, for a fixed constant gamma, of say
0.01. In short then, the gamma used in practice is almost never \sqrt{n log
d}/eps, but a separate parameter. I believe therefore that the correct
formulation of the problem should treat gamma as a separate parameter, instead
of fixing it at ~\sqrt{n}.