Collaborative Learning of Distributions under Heterogeneity and Communication Constraints
In modern machine learning, users often have to collaborate to learn the
distribution of the data. Communication can be a significant bottleneck. Prior
work has studied homogeneous users -- i.e., whose data follow the same discrete
distribution -- and has provided optimal communication-efficient methods for
estimating that distribution. However, these methods rely heavily on
homogeneity, and are less applicable in the common case when users' discrete
distributions are heterogeneous. Here we consider a natural and tractable model
of heterogeneity, where users' discrete distributions only vary sparsely, on a
small number of entries. We propose a novel two-stage method named SHIFT:
First, the users collaborate by communicating with the server to learn a
central distribution; relying on methods from robust statistics. Then, the
learned central distribution is fine-tuned to estimate their respective
individual distribution. We show that SHIFT is minimax optimal in our model of
heterogeneity and under communication constraints. Further, we provide
experimental results using both synthetic data and $n$-gram frequency
estimation in the text domain, which corroborate its efficiency.