用于分布式学习的贪婪低秩梯度压缩方法及其收敛性保证

《IEEE Transactions on Signal Processing》：Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees

低秩梯度压缩在分布式优化中的应用及收敛性研究。针对随机与贪心压缩策略的不足，提出GreedyLore算法，通过误差反馈修正和半懒散子空间更新实现强收敛保证，理论证明其收敛速度为O(σ√(NT+1)/T)，并验证了实验结果。

　　

摘要：

分布式优化在大规模信号处理和机器学习中至关重要，然而通信开销仍然是一个主要瓶颈。低秩梯度压缩通过使用低秩矩阵来近似传输的梯度，从而减少通信量，为这一问题提供了一种有前景的解决方案。现有方法通常采用随机压缩策略或贪婪压缩策略：随机压缩方法将梯度投影到随机选择的子空间上，这会导致高方差并降低实验性能；贪婪压缩方法则选择最具信息量的子空间，虽然可以获得良好的实验结果，但缺乏收敛性保证。为了解决这一难题，我们提出了GreedyLore——首个针对分布式学习的贪婪低秩梯度压缩算法，并提供了严格的收敛性保证。GreedyLore结合了误差反馈机制来纠正贪婪压缩引入的偏差，并引入了一种半懒惰的子空间更新机制，确保压缩算子在所有迭代过程中保持收缩性。通过这些技术，我们证明了在标准优化器（如MSGD和Adam）的框架下，GreedyLore的收敛速率为O(σNT??√+/T，这是低秩梯度压缩领域首次实现线性加速的收敛速率。我们进行了大量实验来验证我们的理论发现。