Timezone: »

 
Poster
Federated Heavy Hitter Recovery under Linear Sketching
Adria Gascon · Peter Kairouz · Ziteng Sun · Ananda Suresh

Wed Jul 26 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #313
in Poster Session 4 »
Motivated by real-life deployments of multi-round federated analytics with secure aggregation, we investigate the fundamental communication-accuracy tradeoffs of the heavy hitter discovery and approximate (open-domain) histogram problems under a linear sketching constraint. We propose efficient algorithms based on local subsampling and invertible bloom look-up tables (IBLTs). We also show that our algorithms are information-theoretically optimal for a broad class of interactive schemes. The results show that the linear sketching constraint does increase the communication cost for both tasks by introducing an extra linear dependence on the number of users in a round. Moreover, our results also establish a separation between the communication cost for heavy hitter discovery and approximate histogram in the multi-round setting. The dependence on the number of rounds $R$ is at most logarithmic for heavy hitter discovery whereas that of approximate histogram is $\Theta(\sqrt{R})$. We also empirically demonstrate our findings.
[ PDF] 

Author Information

Adria Gascon (Google)
Peter Kairouz (Google)
Ziteng Sun (Google Research)
Ananda Suresh (Google Research)

More from the Same Authors