This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, we propose a black-box model casting distributed algorithms in the form of fixed-point iterates, converging at linear rate. The algorithmic model is coupled with a novel (random) Biased Compression (BC-)rule on the quantizer design, which preserves linear convergence. A new quantizer coupled with a communication-efficient encoding scheme is also proposed, which efficiently implements the BC-rule using a finite number of bits. This contrasts with most of existing quantization rules, whose implementation calls for an infinite number of bits. A unified communication complexity analysis is developed for the black-box model, determining the average number of bit required to reach a solution of the optimization problem within the required accuracy. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed quantizer have more favorable communication complexity than algorithms using existing quantization rules.


翻译:本文的论文研究分配了网状网络(强 convex)复合优化问题的算法, 但须有定量通信。 我们不以特定的算法设计为重点, 而是提议一个黑盒模型筛选分布式算法, 其形式为固定点列列列, 以线性速率相融合 。 算法模型与一个小说( 随机) 双向压缩( BC) 规则相结合, 以保持线性趋同 。 还提出了一个新的 量子器, 加上一个通信效率的编码方案, 以一定的位数有效地执行不列颠哥伦比亚规则 。 这与大多数现有的量化规则形成对照, 后者的实施需要无限的位数。 为黑盒模型开发了统一的通信复杂性分析, 确定在所需的精度范围内达成优化问题解决方案所需的平均比特数 。 数值结果证实了我们的理论结论, 并表明配有拟议量化器的分布式算法比使用现有四分法规则的算法更有利于通信的复杂性 。

0
下载
关闭预览

相关内容

专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【LeetCode 136】 关关的刷题日记32 Single Number
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
5+阅读 · 2017年12月14日
VIP会员
相关VIP内容
专知会员服务
41+阅读 · 2021年4月2日
专知会员服务
50+阅读 · 2020年12月14日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【LeetCode 136】 关关的刷题日记32 Single Number
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员