Timezone: »

 
Poster
Private Federated Frequency Estimation: Adapting to the Hardness of the Instance
Jingfeng Wu · Wennan Zhu · Peter Kairouz · Vladimir Braverman

Thu Dec 14 08:45 AM -- 10:45 AM (PST) @ Great Hall & Hall B1+B2 #1123
in Poster Session 5 »
In federated frequency estimation (FFE), multiple clients work together to estimate the frequency of their local data by communicating with a server, while maintaining the security constraint of $\mathtt{secsum}$ where the server can only access the sum of client-held vectors. For FFE with a single communication round, it is known that count sketch is nearly information-theoretically optimal [Chen et al., 2022]. However, when multiple communication rounds are allowed, we propose a new sketch algorithm that is provably more accurate than a naive adaptation of count sketch. Furthermore, we show that both our sketch algorithm and count sketch can achieve better accuracy when the problem instance is simpler. Therefore, we propose a two-phase approach to enable the use of a smaller sketch size for simpler problems. Finally, we provide mechanisms to make our proposed algorithm differentially private. We verify the performance of our methods through experiments conducted on real datasets.

Author Information

Jingfeng Wu (UC Berkeley)
Wennan Zhu (Google)
Peter Kairouz (Google)
Vladimir Braverman (Rice University)

More from the Same Authors