Dear all,
There will be a noon seminar next Thursday, June 20, given by Jakub Tětek, our
former bachelor student, now finishing PhD in Copenhagen. Please find the talk
details below.
I plan to go for lunch with Jakub before the talk (at about 11:20) -- let me
know if you'd like to join us. Likewise, if you'd like to meet with Jakub, I can
arrange that. He's visiting me till the end of June.
Best regards,
Pavel Veselý
-----------------------------------------------------
Better Differentially Private Approximate Histograms and Heavy Hitters using the
Misra-Gries Sketch
Jakub Tětek (University of Copenhagen)
June 20, 2024, 12:20 in S6
Abstract:
We consider the problem of computing differentially private approximate
histograms and heavy hitters in a stream of elements. In the non-private
setting, this is often done using the sketch of Misra and Gries [Science of
Computer Programming, 1982]. Chan, Li, Shi, and Xu [PETS 2012] describe a
differentially private version of the Misra-Gries sketch, but the amount of
noise it adds can be large and scales linearly with the size of the sketch; the
more accurate the sketch is, the more noise this approach has to add. We present
a better mechanism for releasing a Misra-Gries sketch under
$(\varepsilon,\delta)$-differential privacy. It adds noise with magnitude
independent of the size of the sketch; in fact, the maximum error coming from
the noise is the same as the best known in the private non-streaming setting, up
to a constant factor. Our mechanism is simple and likely to be practical. In the
full version of the paper we also give a simple post-processing step of the
Misra-Gries sketch that does not increase the worst-case error guarantee. It is
sufficient to add noise to this new sketch with less than twice the magnitude of
the non-streaming setting. This improves on the previous result for
$\varepsilon$-differential privacy where the noise scales linearly to the size
of the sketch.