Skip to content
Preprint

Optimal Regret for Communication-Efficient Decentralized Online Learning

Oct 2026 · 0 citations · 32 references
Computer Science

Abstract

In this paper, we investigate decentralized online convex optimization with compressed communication, where $n$ learners over a network jointly minimize a sequence of global loss functions based only on their local losses and compressed messages from their neighbors. The best known regret bounds for this problem are $O(\omega^{-1/2}n\rho^{-1}\sqrt{T\ln n})$ and $O(\omega^{-1}n\rho^{-2}\ln n\ln T)$ for convex and strongly convex loss functions, respectively, where $\rho\in(0,1)$ is the spectral gap of the communication matrix and $\omega\in(0,1]$ is the compression quality factor. Compared with the corresponding lower bounds of $\Omega(\omega^{-1/2}n\rho^{-1/4}\sqrt{T})$ and $\Omega(\omega^{-1}n\rho^{-1/2}\ln T)$, these upper bounds exhibit polynomial gaps in their dependence on $\rho^{-1}$. To close these gaps, we first develop Ascent-gossip, which combines an online compression strategy with a Chebyshev recursion and attains a faster consensus rate than existing compressed gossip methods. Furthermore, by adopting Ascent-gossip, we propose an online algorithm that achieves optimal regret bounds of $\widetilde O(\omega^{-1/2}n\rho^{-1/4}\sqrt{T})$ and $\widetilde O(\omega^{-1}n\rho^{-1/2}\ln T)$ for convex and strongly convex loss functions, respectively. Up to logarithmic factors in $n$ and $\rho^{-1}$, these results match the lower bounds in terms of $T$, $n$, $\rho$, and $\omega$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.