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.

本文基于联邦学习和安全加密协议，提出了一种新的混合化草图算法，可用于对多轮次的频率估计问题进行更准确的处理，并探讨了如何根据实际情况设置草图大小，并验证了算法具有更好的性能。