Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications
Authors: Sifan Yang, Dan-Yue Li, Lijun Zhang
Organizations: National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China
Distributed online convex optimization (D-OCO) is a powerful paradigm for modeling distributed scenarios with streaming data. However, the communication cost between local learners and the central server is substantial in large-scale applications. To alleviate this bottleneck, we initiate the study of D-OCO with compressed communication. Firstly, to quantify the compression impact, we establish the Ω(δ−1/2T) and Ω(δ−1logT) lower bounds for convex and strongly convex loss functions, respectively, where δ∈(0,1] is the compression ratio. Secondly, we propose an optimal algorithm, which enjoys regret bounds of O(δ−1/2T) and O(δ−1logT) for convex and strongly convex loss functions, respectively. Our method incorporates the error feedback mechanism into the Follow-the-Regularized-Leader framework to address the coupling between the compression error and the projection error. Furthermore, we employ the online compression strategy to mitigate the accumulated error arising from the bidirectional compression. Our online method has great generality, and can be extended to the offline stochastic setting via online-to-batch conversion. We establish convergence rates of O(δ−1/2T−1/2) and O(δ−1T−1) for convex and strongly convex loss functions, respectively, providing the first guarantees for distributed non-smooth optimization with compressed communication and domain constraints.
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.
Hao Zhou, Xiaoyu Wang, Chang Yao +2
School of Software Technology, Zhejiang University, Ningbo, China · State Key Laboratory of Blockchain and Data Security, Zhejiang University, Hangzhou, China
Decentralized Online Convex Optimization (D-OCO) is a fundamental framework in which a set of local agents aims to minimize a sequence of global loss functions using only local computations and communications. While recent work has established near-optimal regret guarantees for convex and strongly convex losses, the case of exp-concave losses remains an open challenge: specifically, whether logarithmic regret is achievable. In this paper, we answer this question affirmatively by proposing Decentralized Online Newton Step (D-ONS), which adapts the idea of blocking and accelerated gossip to the Online Newton Step algorithm in a non-trivial manner. Concretely, our algorithm achieves a regret bound of O(Nd(1−σ2)−1/2log2(T)) where N is the number of agents, d is the dimension, T is the horizon, and 1−σ2 represents the spectral gap of the network. To our knowledge, this is the first logarithmic regret bound for decentralized online exp-concave optimization. We further establish a nearly matching lower bound of Ω(Nd(1−σ2)−1/2log(T/N)) showing the near optimality of our upper bound. Finally, we extend our algorithm to decentralized online linear regression in which the feasible domain is unbounded and features and labels are locally observed. By gossiping covariance and label-feature statistics, we also achieve logarithmic regret.
Hao Qiu, Mengxiao Zhang, Yuanyu Wan
National University of Singapore, Singapore · Department of Business Analytics, Tippie College of Business, University of Iowa, USA · School of Software Technology, Zhejiang University, Ningbo, China +1
We study decentralized online convex optimization when agents communicate over a graph and messages may be compressed. Classical decentralized online methods typically require learning-rate choices that depend on the horizon, comparator scale, or other problem parameters, while compressed communication introduces additional disagreement that must be controlled. We propose DECO-EF (DEcentralized COin-betting with Error Feedback), a decentralized parameter-free online learning algorithm that combines coin-betting predictions with compressed difference-based gossip. Each agent maintains a clean accumulated state and a compressed tracker, and communicates only compressed state differences during gossip steps. The method is parameter-free in the online-learning sense: it does not tune to the horizon, the comparator norm, or the learning rate. We prove expected comparator-adaptive network-regret bounds for DECO-EF under compressed communication. To the best of our knowledge, this gives the first expected sublinear network-regret guarantees for parameter-free decentralized online learning under compressed communication.
Tomas Ortega, Hamid Jafarkhani
Center for Pervasive Communications & Computing and EECS Department, University of California, Irvine, Irvine, CA 92697 USA