Communication Complexity of Distributed Convex Learning and Optimization
Communication Complexity of Distributed Convex Learning and Optimization
复制标题
DOI：
--
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Yossi Arjevani;Ohad Shamir
中科院分区：
文献类型：
--
作者：
Yossi Arjevani;Ohad Shamir
我们研究了凸学习和优化的通信有效的分布式方法的基本限制，在不同的假设下，对单个机器的信息，以及考虑的功能类型。我们确定的情况下，现有的算法已经是最坏情况下的最佳，以及进一步改进的空间仍然是可能的情况下。除此之外，我们的研究结果表明，如果局部目标函数之间没有相似性（由于统计数据相似性或其他原因），即使机器具有无限的计算能力，也可能需要许多通信回合。
We study the fundamental limits to communication-efficient distributed methods for convex learning and optimization, under different assumptions on the information available to individual machines, and the types of functions considered. We identify cases where existing algorithms are already worst-case optimal, as well as cases where room for further improvement is still possible. Among other things, our results indicate that without similarity between the local objective functions (due to statistical data similarity or otherwise) many communication rounds may be required, even if the machines have unbounded computational power.