Innovation Compression for Communication-efficient Distributed Optimization with Linear Convergence
This work addresses communication efficiency for distributed optimization in peer-to-peer networks, offering incremental improvements over prior methods.
The paper tackles communication overhead in distributed optimization by proposing COLD and Dyna-COLD algorithms that compress innovation vectors, achieving linear convergence with rates matching uncompressed versions and strictly improving on existing quantized consensus results.
Information compression is essential to reduce communication cost in distributed optimization over peer-to-peer networks. This paper proposes a communication-efficient linearly convergent distributed (COLD) algorithm to solve strongly convex optimization problems. By compressing innovation vectors, which are the differences between decision vectors and their estimates, COLD is able to achieve linear convergence for a class of $δ$-contracted compressors. We explicitly quantify how the compression affects the convergence rate and show that COLD matches the same rate of its uncompressed version. To accommodate a wider class of compressors that includes the binary quantizer, we further design a novel dynamical scaling mechanism and obtain the linearly convergent Dyna-COLD. Importantly, our results strictly improve existing results for the quantized consensus problem. Numerical experiments demonstrate the advantages of both algorithms under different compressors.