Federated Heavy Hitters Discovery with Differential Privacy

By Wennan Zhu, Peter Kairouz, Haicheng Sun, H. Brendan McMahan, Wei Li. 2019

116 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications, Sociology and Political Science, Federated & Distributed Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Sociology and Political Science

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

Personalized Federated Learning: A Meta-Learning Approach (2020, background): “In particular, there have been several works on various aspects of FL, including preserving the privacy of users [6, 7, 8, 9] and lowering communication cost [10, 11, 12, 13].”
Differential Privacy Has Disparate Impact on Model Accuracy (2019, methodology): “We focus on DP-SGD [1] because it enables DP training of deep models for practical tasks (including federated learning [16, 40]), is available as an open-source framework [36], generalizes to iterative training procedures [24], and supports tighter bounds using the Rényi method [28].”
Federated Learning Of Out-Of-Vocabulary Words (2019, background): “, 2002), or tries (Gunasinghe and Alahakoon, 2012) require significant adaptation to be able to run on FL settings (Zhu et al., 2019).”
Personalized Federated Learning with Theoretical Guarantees: A Model-Agnostic Meta-Learning Approach (2020, background): “In particular, there have been several works on various aspects of FL, including preserving the privacy of users [6–9] and lowering communication cost [10– 13].”
Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints (2021, background): “On the other hand, the interactive scheme in (Zhu et al., 2020), which identifies (instead of estimating the frequencies of) heavy-hitter symbols, is similar to our proposed interactive scheme in nature.”
Personalized Federated Learning using Hypernetworks (2021, background): “Duchi et al. (2014); McMahan et al. (2017b); Agarwal et al. (2018); Zhu et al. (2019) proposed new meth-ods for preserving privacy, and Reisizadeh et al. (2020); Dai et al. (2019); Basu et al. (2020); Li et al. (2020b); Stich (2018) focused on reducing communication cost.”