New FTRL Algorithms Improve Decentralized Online Optimization with Compression

Decentralized Online Convex Optimization (D-OCO) is a critical framework for distributed applications that process streaming data, but it often faces a communication bottleneck. Previous research has explored D-OCO with compressed communication, primarily developing algorithms based on Online Gradient Descent (OGD). However, for D-OCO with exact communication, the most effective algorithms have been variants of Follow-The-Regularized-Leader (FTRL). This new paper bridges this gap by introducing FTRL-type algorithms for D-OCO under compressed communication. The proposed FTRL-type algorithms offer a more elegant design and theoretical analysis compared to their OGD counterparts. The key innovation lies in leveraging the dual update mechanism inherent in FTRL, which allows for a straightforward application of techniques used for average consensus with communication compression. The research presents two specific algorithms. The first is designed for the full-information setting and achieves regret bounds comparable to existing methods. The second algorithm targets the more challenging bandit setting, where it significantly improves both the regret bounds and communication costs of current algorithms. This advancement provides a more efficient and robust approach to decentralized optimization in environments with communication constraints.