Information compression is essential to reduce communication cost in distributed optimization over peer-to-peer networks. This paper proposes a communication-efficient linearly convergent distributed (COLD) algorithm to solve strongly convex optimization problems. By compressing innovation vectors, which are the differences between decision vectors and their estimates, COLD is able to achieve linear convergence for a class of $\delta$-contracted compressors. We explicitly quantify how the compression affects the convergence rate and show that COLD matches the same rate of its uncompressed version. To accommodate a wider class of compressors that includes the binary quantizer, we further design a novel dynamical scaling mechanism and obtain the linearly convergent Dyna-COLD. Importantly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of both algorithms under different compressors.


翻译:信息压缩对于降低对同行网络的分布优化的通信成本至关重要。 本文建议采用通信效率线性分布式分布式( COLD) 算法, 以解决强烈的 convex 优化问题。 压缩创新矢量( 即决定矢量与其估计值之间的差异), COLD 能够实现某类 $\delta$ 承包的压缩压缩机的线性趋同。 我们明确量化压缩如何影响聚合率, 并显示COLD 与其未压缩版本的相同速度。 为了容纳包括二进制量化器在内的范围更广的压缩机, 我们进一步设计一个新的动态缩放机制, 并获得线性趋同的 Dyna- COLD 。 重要的是, 我们的结果严格地改善了四分化共识问题的现有结果。 数字实验展示了不同压缩器下两种算法的优势 。

0
下载
关闭预览

相关内容

专知会员服务
42+阅读 · 2020年12月18日
专知会员服务
44+阅读 · 2020年10月31日
【斯坦福】凸优化圣经- Convex Optimization (附730pdf下载)
专知会员服务
220+阅读 · 2020年6月5日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2021年7月6日
Arxiv
0+阅读 · 2021年7月2日
VIP会员
相关资讯
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
人工智能 | UAI 2019等国际会议信息4条
Call4Papers
6+阅读 · 2019年1月14日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员