Differentially Quantized Gradient Descent
Differentially Quantized Gradient Descent
复制标题
差分量化梯度下降
DOI：
10.1109/isit45174.2021.9518254
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Hassibi, Babak
中科院分区：
文献类型：
--
作者：
Lin, Chung-Yi;Kostina, Victoria;Hassibi, Babak
考虑以下分布式优化场景。工作者可以访问用于计算梯度的训练数据，而服务器则根据其目标精度或延迟约束决定何时停止迭代计算。服务器知道的关于问题实例的唯一信息是它通过速率受限的无噪声通信信道从工作者接收的信息。我们介绍的技术，我们称之为差分量化（DQ），补偿过去的量化误差，使量化算法的下降轨迹遵循其未量化的对应。假设目标函数是光滑的和强凸的，我们证明了差分量化梯度下降（DQ-GD）达到线性收敛速度，其中是未量化梯度下降（GD）的收敛速度，是量化器的覆盖效率，和是每问题维的比特率。因此，在任何情况下，DQ-GD的收敛速率与未量化GD的收敛速率相同，即，没有由于量化而造成的损失。我们展示了一个匡威的证明，没有GD样的量化算法可以收敛速度比。由于量化器存在于（Rogers，1963），这意味着DQ-GD是渐近最优的。相比之下，其中工作者直接量化梯度的朴素量化GD仅获得。微分量子化的技术继续应用于动量梯度方法，如Nesterov的加速梯度下降法和Polyak的重球方法。对于这些算法来说，如果速率高于某个阈值，则与未量化的算法相比，差分量化算法获得的收敛速率不会损失。模拟和现实世界的最小二乘问题的实验结果验证了我们的理论分析。
Consider the following distributed optimization scenario. A worker has access to training data that it uses to compute the gradients while a server decides when to stop iterative computation based on its target accuracy or delay constraints. The only information that the server knows about the problem instance is what it receives from the worker via a rate-limited noiseless communication channel. We introduce the technique we call differential quantization (DQ) that compensates past quantization errors to make the descent trajectory of a quantized algorithm follow that of its unquantized counterpart. Assuming that the objective function is smooth and strongly convex, we prove that differentially quantized gradient descent (DQ-GD) attains a linear convergence rate of, whereis the convergence rate of unquantized gradient descent (GD),is the covering efficiency of the quantizer, andis the bitrate per problem dimension. Thus at any, the convergence rate of DQ-GD is the same as that of unquantized GD, i.e., there is no loss due to quantization. We show a converse demonstrating that no GD-like quantized algorithm can converge faster than. Since quantizers exist withas(Rogers, 1963), this means that DQ-GD is asymptotically optimal. In contrast, naively quantized GD where the worker directly quantizes the gradient attains only. The technique of differential quantization continues to apply to gradient methods with momentum such as Nesterov's accelerated gradient descent, and Polyak's heavy ball method. For these algorithms as well, if the rate is above a certain threshold, there is no loss in convergence rate obtained by the differentially quantized algorithm compared to its unquantized counterpart. Experimental results on both simulated and realworld least-squares problems validate our theoretical analysis.