# Private Federated Frequency Estimation: Adapting to the Hardness of the Instance

arXiv: https://arxiv.org/abs/2306.09396 · HTML: https://mlsanity.com/paper/2306.09396/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 20 references that are in the map.
- First posted on arXiv 15 Jun 2023.

## Builds on (most cited first, 7 of 7)

- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Practical Secure Aggregation for Federated Learning on User-Held Data](https://mlsanity.com/paper/1611.04482/) (2016)
- [Federated Heavy Hitters Discovery with Differential Privacy](https://mlsanity.com/paper/1902.08534/) (2019)
- [Differentially Private Linear Sketches: Efficient Implementations and Applications](https://mlsanity.com/paper/2205.09873/) (2022)
- [Frequency Estimation Under Multiparty Differential Privacy: One-shot and Streaming](https://mlsanity.com/paper/2104.01808/) (2021)
- [Improved Utility Analysis of Private CountSketch](https://mlsanity.com/paper/2205.08397/) (2022)
- [The communication cost of security and privacy in federated frequency estimation](https://mlsanity.com/paper/2211.10041/) (2022)

## Abstract (arXiv)

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.