Federated Heavy Hitters Discovery with Differential Privacy

Wennan Zhu, Peter Kairouz, Brendan McMahan, Haicheng Sun, Wei Li
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3837-3847, 2020.

Abstract

The discovery of heavy hitters (most frequent items) in user-generated data streams drives improvements in the app and web ecosystems, but can incur substantial privacy risks if not done with care. To address these risks, we propose a distributed and privacy-preserving algorithm for discovering the heavy hitters in a population of user-generated data streams. We leverage the sampling and thresholding properties of our distributed algorithm to prove that it is inherently differentially private, without requiring additional noise. We also examine the trade-off between privacy and utility, and show that our algorithm provides excellent utility while also achieving strong privacy guarantees. A significant advantage of this approach is that it eliminates the need to centralize raw data while also avoiding the significant loss in utility incurred by local differential privacy. We validate our findings both theoretically, using worst-case analyses, and practically, using a Twitter dataset with 1.6M tweets and over 650k users. Finally, we carefully compare our approach to Apple’s local differential privacy method for discovering heavy hitters.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-zhu20a, title = {Federated Heavy Hitters Discovery with Differential Privacy}, author = {Zhu, Wennan and Kairouz, Peter and McMahan, Brendan and Sun, Haicheng and Li, Wei}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3837--3847}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/zhu20a/zhu20a.pdf}, url = {https://proceedings.mlr.press/v108/zhu20a.html}, abstract = {The discovery of heavy hitters (most frequent items) in user-generated data streams drives improvements in the app and web ecosystems, but can incur substantial privacy risks if not done with care. To address these risks, we propose a distributed and privacy-preserving algorithm for discovering the heavy hitters in a population of user-generated data streams. We leverage the sampling and thresholding properties of our distributed algorithm to prove that it is inherently differentially private, without requiring additional noise. We also examine the trade-off between privacy and utility, and show that our algorithm provides excellent utility while also achieving strong privacy guarantees. A significant advantage of this approach is that it eliminates the need to centralize raw data while also avoiding the significant loss in utility incurred by local differential privacy. We validate our findings both theoretically, using worst-case analyses, and practically, using a Twitter dataset with 1.6M tweets and over 650k users. Finally, we carefully compare our approach to Apple’s local differential privacy method for discovering heavy hitters.} }
Endnote
%0 Conference Paper %T Federated Heavy Hitters Discovery with Differential Privacy %A Wennan Zhu %A Peter Kairouz %A Brendan McMahan %A Haicheng Sun %A Wei Li %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-zhu20a %I PMLR %P 3837--3847 %U https://proceedings.mlr.press/v108/zhu20a.html %V 108 %X The discovery of heavy hitters (most frequent items) in user-generated data streams drives improvements in the app and web ecosystems, but can incur substantial privacy risks if not done with care. To address these risks, we propose a distributed and privacy-preserving algorithm for discovering the heavy hitters in a population of user-generated data streams. We leverage the sampling and thresholding properties of our distributed algorithm to prove that it is inherently differentially private, without requiring additional noise. We also examine the trade-off between privacy and utility, and show that our algorithm provides excellent utility while also achieving strong privacy guarantees. A significant advantage of this approach is that it eliminates the need to centralize raw data while also avoiding the significant loss in utility incurred by local differential privacy. We validate our findings both theoretically, using worst-case analyses, and practically, using a Twitter dataset with 1.6M tweets and over 650k users. Finally, we carefully compare our approach to Apple’s local differential privacy method for discovering heavy hitters.
APA
Zhu, W., Kairouz, P., McMahan, B., Sun, H. & Li, W.. (2020). Federated Heavy Hitters Discovery with Differential Privacy. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3837-3847 Available from https://proceedings.mlr.press/v108/zhu20a.html.

Related Material