  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.
