Communication-Efficient Regret-Optimal Distributed Online Convex Optimization

Abstract

Online convex optimization in distributed systems has shown great promise in collaboratively learning on data streams with massive learners, such as in collaborative coordination in robot and IoT networks. When implemented in communication-constrained networks like robot and IoT networks, two critical yet distinct objectives in distributed online convex optimization (DOCO) are minimizing the overall regret and the communication cost. Achieving both objectives simultaneously is challenging, especially when the number of learners <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> and learning time <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> are prohibitively large. To address this challenge, we propose novel algorithms in typical adversarial and stochastic settings. Our algorithms significantly reduce the communication complexity of the algorithms with the state-of-the-art regret by a factor of <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(n^{2})$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$\tilde{\mathcal {O}}(\sqrt{nT})$</tex-math></inline-formula> in adversarial and stochastic settings, respectively. We are the first to achieve nearly optimal regret and communication complexity simultaneously up to polylogarithmic factors. We validate our algorithms through experiments on real-world datasets in classification tasks. Our algorithms with appropriate parameters can achieve <inline-formula><tex-math notation="LaTeX">$90\%\sim 99\%$</tex-math></inline-formula> communication saving with close accuracy over existing methods in most cases. The code is available at <uri>https://github.com/GGBOND121382/Communication-Efficient_Regret-Optimal_DOCO</uri>.