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.