提出两种新型压缩通信下的分布式在线优化算法，性能更优。
Revisiting Decentralized Online Convex Optimization with Compressed Communication
- 采用FTRL框架设计压缩通信的分布式在线优化算法
- 带宽受限下，实现更优的误差累积与通信成本
- 适合大规模流式数据分布式系统，尤其关注通信效率的场景
去中心化在线凸优化（D-OCO）是处理流式数据分布式应用的常用框架。为缓解通信瓶颈，以往研究提出了基于在线梯度下降（OGD）的压缩通信算法。然而，在无压缩通信情况下，最优算法多为跟随正则化领导者（FTRL）变体。本文首次提出两种适用于压缩通信的FTRL型算法。相较于OGD类算法，新方法在算法设计与理论分析上更为简洁优雅。核心思想在于：利用FTRL的对偶更新机制，可直接套用压缩通信下的平均一致性技术。第一个算法针对全信息设定，达到现有最优误差界；第二个算法用于轶事（bandit）设定，显著改进了误差界和通信开销。
原文摘要 · Abstract (English)
Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。