Revisiting Decentralized Online Convex Optimization with Compressed Communication

Decentralized Online Convex Optimization (D-OCO) is a framework where multiple learners in a network collaboratively minimize a global loss function while only communicating with their immediate neighbors. A significant challenge in this setting is the communication bottleneck, which researchers typically address using compressed communication. While previous approaches have relied on variants of Online Gradient Descent (OGD), this paper introduces two novel algorithms based on Follow-the-Regularized-Leader (FTRL) that are specifically designed for compressed communication.

The authors propose two algorithms: CD-FTGL for the full-information setting and CD-FTBL for the bandit setting. The core innovation lies in the dual update mechanism of FTRL, which allows for a more elegant integration with Choco-Gossip—a technique for average consensus under communication compression. By maintaining local approximations of the cumulative average gradient, the authors demonstrate that the consensus error can be controlled independently of the projection operation, leading to simpler algorithmic designs and improved theoretical guarantees.

In the full-information setting, the proposed CD-FTGL algorithm matches the best existing regret bounds while offering a more straightforward analysis. In the more challenging bandit setting, the CD-FTBL algorithm significantly improves both the regret bounds and the required communication rounds compared to previous state-of-the-art methods. Specifically, the authors show that their bandit algorithm achieves O(nT^3/4) and O(nT^2/3(logT)^1/3) regret for convex and strongly convex functions, respectively, while requiring only sublinear communication rounds. Experimental results on logistic regression tasks confirm that these algorithms reach lower average loss with fewer transmitted bits than competing OGD-based approaches.