Choco-SGD and Choco-Gossip Decentralized Optimization with Compressed Communication

A family of decentralized gossip and stochastic optimization algorithms (Choco-Gossip and Choco-SGD) over a connected network with symmetric doubly stochastic mixing matrix W = [w_{ij}] and spectral gap delta > 0, in which each node i maintains local parameters x_i^{(t)} and public replica states x_hat_j^{(t)} for its neighbors j in N_i, transmits only omega-contractive compressed state differences q_i^{(t)} = Q(x_i^{(t)} - x_hat_i^{(t)}) to update x_hat_i^{(t+1)} = x_hat_i^{(t)} + q_i^{(t)}, and applies consensus mixing x_i^{(t+1)} = x_i^{(t)} + gamma * sum_{j=1}^n w_{ij} (x_hat_j^{(t+1)} - x_hat_i^{(t+1)}) (preceded in Choco-SGD by a local stochastic gradient step x_i^{(t+1/2)} = x_i^{(t)} - eta_t * g_i(x_i^{(t)})), preserving the exact global average (1/n) sum_{i=1}^n x_i^{(t)} under arbitrary biased or randomized contractive compression and achieving linear consensus convergence O((1 - delta^2 * omega / 82)^t) and optimal O(sigma_bar^2 / (mu * n * T)) decentralized stochastic optimization speedup.