[leftmargin=*,topsep=0pt,noitemsep]
We notice that it is efficient to compress the innovation—the difference between a decision variable and its estimate, as it is expected to eventually decrease to zero. By leveraging such an observation, COLD is the first distributed algorithm that achieves linear convergence for \(\mu \) -strongly convex and \(L\) -smooth functions with both unbiased and biased \(\delta \) -contracted compressors, which is in sharp contrast to [1]}, [2]}, [3]}, [4]}, [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]} as they are only applicable to some specific biased or unbiased compressors.

The effect of compression on the convergence rate of COLD is explicitly revealed, e.g., the number of iterations to find an \(\epsilon \) -optimal solution is \(\mathcal {O}\big (\max \lbrace \frac{L}{\mu },\frac{1}{(1-\delta )^2\rho }\rbrace \log \frac{1}{\epsilon }\big )\)  for unbiased \(\delta \) -contracted compressors, where \(\delta <1\)  characterizes the compression resolution and \(\rho <1\)  is the spectral gap of the network. Specifically, \(\delta =0\)  corresponds to the uncompressed case under which COLD matches the rate of NIDS [13]} with infinite precision.

By designing a novel dynamical scaling mechanism, we obtain linearly convergent Dyna-COLD for a wider class of compressors, which covers the quantizers in [7]}, [8]}, [9]}. Numerical experiments validate the linear convergence of Dyna-COLD even for the 1-bit binary quantizer and show its advantages over competitors.

When (REF ) is reduced to the consensus problem, i.e., \(f_i(\mathbf {x})=\Vert \mathbf {x}-\mathbf {x}_i\Vert ^2\) , we strictly improve the rate of the state-of-the-art CHOCO-GOSSIP method [17]} from \(\mathcal {O}(\frac{1}{(1-\delta )\rho ^2}\log \frac{1}{\epsilon })\)  to \(\mathcal {O}(\frac{1}{(1-\delta )\rho }\log \frac{1}{\epsilon })\) , which matches the best rate in [18]}. By the dynamic scaling, we generalize and strengthen the theoretical result in [19]} which was established for a finite-level uniform quantizer.

