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) 规则相结合, 以保持线性趋同 。 还提出了一个新的 量子器, 加上一个通信效率的编码方案, 以一定的位数有效地执行不列颠哥伦比亚规则 。 这与大多数现有的量化规则形成对照, 后者的实施需要无限的位数。 为黑盒模型开发了统一的通信复杂性分析, 确定在所需的精度范围内达成优化问题解决方案所需的平均比特数 。 数值结果证实了我们的理论结论, 并表明配有拟议量化器的分布式算法比使用现有四分法规则的算法更有利于通信的复杂性 。