Finite-Bit Quantization for Distributed Algorithms With Linear Convergence
Finite-Bit Quantization for Distributed Algorithms With Linear Convergence
复制标题
DOI：
10.1109/tit.2022.3176253
复制
发表时间：
2021-07
影响因子：
2.5
通讯作者：
Chang-Shen Lee;Nicolò Michelusi;G. Scutari
中科院分区：
文献类型：
--
作者：
Chang-Shen Lee;Nicolò Michelusi;G. Scutari
本文研究了网格网络上（强凸）复合优化问题的分布式算法。而不是专注于一个特定的算法设计，提出了一个黑盒模型，铸造线性收敛的分布式算法的形式固定点迭代。该算法模型配备了一个新的随机或确定性的偏置压缩（BC）规则的量化器设计，和一个新的自适应编码非均匀量化器（ANQ）加上一个通信效率高的编码方案，它实现了BC规则使用有限数量的位（低于机器精度）。这填补了存在于大多数现有技术的量化方案中的空白，例如基于流行的压缩规则的那些，其依赖于具有可忽略的量化误差（实际上以机器精度量化）的一些标量信号的通信。一个统一的通信复杂性分析的黑盒模型，确定所需的平均位数，以达到目标精度内的优化问题的解决方案。结果表明，建议的BC规则保持非量化算法的线性收敛性，并根据ANQ基于量化的收敛速度和通信成本之间的权衡的特点。数值结果验证了我们的理论研究结果，并表明，分布式算法配备了建议ANQ有更有利的通信成本比使用国家的最先进的量化规则的算法。
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, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Non-uniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules.