Communication-Efficient Distributed Learning of Discrete Probability Distributions
Communication-Efficient Distributed Learning of Discrete Probability Distributions
复制标题
离散概率分布的通信高效分布式学习
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Ilias Diakonikolas
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas
当数据分布在多个服务器上时，我们开始对分布学习(密度估计)进行系统调查。服务器必须与裁判通信，目标是用尽可能少的通信比特来估计潜在的分布。我们着重于离散分布关于`1和`2范数的非参数密度估计。我们给出了在各种感兴趣的环境下这一基本估计任务的通信复杂性的第一个非平凡的上下界。具体地，我们的结果包括：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 `1 and `2 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.
近线性时间内的样本最优密度估计
DOI：
10.48550/arxiv.1506.00671
发表时间：
2015
期刊：
--
影响因子：
--
作者：
Acharya J
通讯作者：
Acharya J
使用可变宽度直方图的近线性时间中的近最优密度估计
DOI：
10.48550/arxiv.1411.0169
发表时间：
2014
期刊：
--
影响因子：
--
作者：
Chan S
通讯作者：
Chan S