  Motivated by real-life deployments of multi-round federated analytics with
secure aggregation, we investigate the fundamental communication-accuracy
tradeoffs of the heavy hitter discovery and approximate (open-domain) histogram
problems under a linear sketching constraint. We propose efficient algorithms
based on local subsampling and invertible bloom look-up tables (IBLTs). We also
show that our algorithms are information-theoretically optimal for a broad
class of interactive schemes. The results show that the linear sketching
constraint does increase the communication cost for both tasks by introducing
an extra linear dependence on the number of users in a round. Moreover, our
results also establish a separation between the communication cost for heavy
hitter discovery and approximate histogram in the multi-round setting. The
dependence on the number of rounds $R$ is at most logarithmic for heavy hitter
discovery whereas that of approximate histogram is $\Theta(\sqrt{R})$. We also
empirically demonstrate our findings.
