Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints
Collaborative Learning of Discrete Distributions under Heterogeneity and Communication Constraints
复制标题
DOI：
--
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Xinmeng Huang;Dong-hwan Lee;Edgar Dobriban;Hamed Hassani
中科院分区：
文献类型：
--
作者：
Xinmeng Huang;Dong-hwan Lee;Edgar Dobriban;Hamed Hassani
在现代机器学习中，用户经常需要协作来学习数据的分布。沟通可能是一个重要的瓶颈。先前的工作研究了同质用户——即，其数据遵循相同的离散分布——并提供了估计该分布的最佳通信效率方法。然而，这些方法严重依赖于同质性，在用户的离散分布是异构的情况下不太适用。在这里，我们考虑一个自然且易于处理的异质性模型，其中用户的离散分布仅在少量条目上稀疏地变化。我们提出了一种新的两阶段方法SHIFT：首先，用户通过与服务器通信进行协作，学习中心分布；依靠可靠的统计方法。然后，对学习的中心分布进行微调，以估计它们各自的个体分布。我们表明，在异质性模型和通信约束下，SHIFT是最小最大最优的。此外，我们提供了在文本域中使用合成数据和$n$-gram频率估计的实验结果，证实了该方法的有效性。
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.