Decentralized Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower Bounds

We investigate decentralized online convex optimization with compressed communication, where $n$ learners connected by a network collaboratively minimize a sequence of global loss functions using only local information and compressed data from their neighbors. Prior work has established regret bounds of $O(\max\\{\omega^{-2}\rho^{-4}n^{1/2},\omega^{-4}\rho^{-8}\\}n\sqrt{T})$ and $O(\max\\{\omega^{-2}\rho^{-4}n^{1/2},\omega^{-4}\rho^{-8}\\}n\ln{T})$ for convex and strongly convex functions, respectively, where $\omega\in(0,1]$ is the compression quality factor and $\rho<1$ is the spectral gap of the communication matrix. However, these regret bounds suffer from a prohibitively high quadratic or even quartic dependence on $\omega^{-1}$. Moreover, the super-linear dependence on $n$ is also undesirable. To overcome these shortcomings, we propose a novel algorithm that achieves improved regret bounds of $\tilde{O}(\omega^{-1/2}\rho^{-1}n\sqrt{T})$ and $\tilde{O}(\omega^{-1}\rho^{-2}n\ln{T})$ for convex and strongly convex functions, respectively. The primary idea is to design a two-level blocking update framework incorporating two novel ingredients: an online gossip strategy and an error compensation scheme, which work together to promote better consensus among learners. Furthermore, we establish the first lower bounds for this problem, justifying the optimality of our results with respect to both $\omega$ and $T$. Additionally, we consider the bandit feedback scenario and extend our method with classical gradient estimators to enhance existing regret bounds.

Many modern systems need to keep learning from data that arrives nonstop, without funneling everything through a central hub. Instead, each machine works on its own share of the data and only exchanges messages with its immediate neighbors, yet together they want to perform as well as if a single machine had seen all the data at once. The catch is that these messages become a serious bottleneck when the network is large or the data is high-dimensional. A common remedy is to compress them so each one is cheaper to send, but existing methods pay a steep price. The more aggressively they compress, the weaker their performance guarantees become, and they also scale poorly as more machines join. We design a new algorithm that largely removes this penalty. It keeps the machines in much closer agreement while still sending only a single compressed message per round, yielding far stronger guarantees in terms of how hard we compress, how the network is connected, and how many machines take part. We also prove the first fundamental limits for this problem, showing our method is close to the best achievable, and we extend it to the harder case where a machine only sees how good its choices turned out rather than detailed guidance. In short, our approach lets large decentralized systems learn effectively while spending far less on communication.