On Arbitrary Compression for Decentralized Consensus and Stochastic Optimization over Directed Networks
This addresses communication bottlenecks in decentralized machine learning for networks with directed graphs, offering a flexible compression method, though it is incremental as it builds on existing gradient-based approaches.
The paper tackles decentralized consensus and stochastic optimization over directed networks by proposing a gradient-based algorithm that compresses messages to reduce communication overhead, allowing arbitrary compression ratios. It demonstrates linear convergence for consensus and provides explicit rates for smooth functions under strong convexity, convexity, and non-convexity, with numerical experiments validating efficiency.
We study the decentralized consensus and stochastic optimization problems with compressed communications over static directed graphs. We propose an iterative gradient-based algorithm that compresses messages according to a desired compression ratio. The proposed method provably reduces the communication overhead on the network at every communication round. Contrary to existing literature, we allow for arbitrary compression ratios in the communicated messages. We show a linear convergence rate for the proposed method on the consensus problem. Moreover, we provide explicit convergence rates for decentralized stochastic optimization problems on smooth functions that are either (i) strongly convex, (ii) convex, or (iii) non-convex. Finally, we provide numerical experiments to illustrate convergence under arbitrary compression ratios and the communication efficiency of our algorithm.