Greedy Low-Rank Gradient Compression for Distributed Learning with Convergence Guarantees
This addresses communication overhead in distributed learning for large-scale machine learning, offering a novel solution with theoretical guarantees, though it is incremental in improving upon existing greedy methods.
The paper tackles the communication bottleneck in distributed optimization by proposing GreedyLore, a greedy low-rank gradient compression algorithm with error feedback and semi-lazy subspace updates, achieving a convergence rate of O(σ/√NT + 1/T) and providing the first linear speedup guarantee for such methods.
Distributed optimization is pivotal for large-scale signal processing and machine learning, yet communication overhead remains a major bottleneck. Low-rank gradient compression, in which the transmitted gradients are approximated by low-rank matrices to reduce communication, offers a promising remedy. Existing methods typically adopt either randomized or greedy compression strategies: randomized approaches project gradients onto randomly chosen subspaces, introducing high variance and degrading empirical performance; greedy methods select the most informative subspaces, achieving strong empirical results but lacking convergence guarantees. To address this gap, we propose GreedyLore--the first Greedy Low-Rank gradient compression algorithm for distributed learning with rigorous convergence guarantees. GreedyLore incorporates error feedback to correct the bias introduced by greedy compression and introduces a semi-lazy subspace update that ensures the compression operator remains contractive throughout all iterations. With these techniques, we prove that GreedyLore achieves a convergence rate of $\mathcal{O}(σ/\sqrt{NT} + 1/T)$ under standard optimizers such as MSGD and Adam--marking the first linear speedup convergence rate for low-rank gradient compression. Extensive experiments are conducted to validate our theoretical findings.