Communication-Efficient Distributed Learning of Discrete Distributions
Communication-Efficient Distributed Learning of Discrete Distributions
复制标题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Elena Grigorescu;Jerry Li;Abhiram Natarajan;Krzysztof Onak;Ludwig Schmidt
当数据分布在多个服务器上时，我们启动对分布学习（密度估计）的系统研究。服务器必须与裁判进行通信，目标是用尽可能少的沟通来估计基础分布。我们专注于相对于L1和L2规范的离散分布的非参数密度估计。在各种感兴趣的设置中，我们提供了此基本估计任务的通信复杂性的第一个非平凡的上限和下限。具体来说，我们的结果包括以下内容：1。当未知离散分发是非结构化的，每个服务器只有一个示例时，我们表明任何黑板协议（即服务器使用公共消息任意交互的任何协议）都必须了解分布本质上可以传达整个样本。 2。对于结构化分布的情况，例如K-固定图和单调分布，我们设计了分布式学习算法，这些算法比幼稚的分布算法获得了明显更好的沟通保证，并在多个制度中获得了紧密的上和下限。我们的分布式学习算法在接近线性的时间内运行，并且可以建模错误指定。我们的结果提供了有关一系列基本分配估计任务的结构和沟通效率之间相互作用的见解。
We initiate a systematic investigation of distribution learning (density estimation) when the data is distributed across multiple servers. The servers must communicate with a referee and the goal is to estimate the underlying distribution with as few bits of communication as possible. We focus on non-parametric density estimation of discrete distributions with respect to the l1 and l2 norms. We provide the first non-trivial upper and lower bounds on the communication complexity of this basic estimation task in various settings of interest. Specifically, our results include the following: 1. When the unknown discrete distribution is unstructured and each server has only one sample, we show that any blackboard protocol (i.e., any protocol in which servers interact arbitrarily using public messages) that learns the distribution must essentially communicate the entire sample. 2. For the case of structured distributions, such as k-histograms and monotone distributions, we design distributed learning algorithms that achieve significantly better communication guarantees than the naive ones, and obtain tight upper and lower bounds in several regimes. Our distributed learning algorithms run in near-linear time and are robust to model misspecification. Our results provide insights on the interplay between structure and communication efficiency for a range of fundamental distribution estimation tasks.