Private Federated Frequency Estimation: Adapting to the Hardness of the Instance
This work addresses the challenge of efficient and accurate frequency estimation in federated learning for practitioners, offering incremental improvements over prior methods.
The paper tackled the problem of multi-round federated frequency estimation by showing that existing count sketching methods are suboptimal and proposing a novel hybrid sketching algorithm that improves accuracy. It also introduced a two-phase approach to adapt sketch size to problem hardness, achieving better performance on large-scale datasets.
In federated frequency estimation (FFE), multiple clients work together to estimate the frequencies of their collective data by communicating with a server that respects the privacy constraints of Secure Summation (SecSum), a cryptographic multi-party computation protocol that ensures that the server can only access the sum of client-held vectors. For single-round FFE, it is known that count sketching is nearly information-theoretically optimal for achieving the fundamental accuracy-communication trade-offs [Chen et al., 2022]. However, we show that under the more practical multi-round FEE setting, simple adaptations of count sketching are strictly sub-optimal, and we propose a novel hybrid sketching algorithm that is provably more accurate. We also address the following fundamental question: how should a practitioner set the sketch size in a way that adapts to the hardness of the underlying problem? We propose a two-phase approach that allows for the use of a smaller sketch size for simpler problems (e.g., near-sparse or light-tailed distributions). We conclude our work by showing how differential privacy can be added to our algorithm and verifying its superior performance through extensive experiments conducted on large-scale datasets.