Optimal Regret for Communication-Efficient Decentralized Online Learning

arXiv:2610.38334 · cs.LG · Submitted 2026-10-28 · Read on arXiv

cs.LG

Submitted: 2026-10-28

Updated: 2026-10-28

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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…

Terminology

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(ω-1/2nρ-1 sqrt T n) and O(ω-1nρ-2 n T) for convex and strongly convex loss functions, respectively, where ρ in(0,1) is the spectral gap of the communication matrix and ω in(0,1] is the compression quality factor. Compared with the corresponding lower bounds of Ω(ω-1/2nρ-1/4 sqrt T) and Ω(ω-1nρ-1/2 T), these upper bounds exhibit polynomial gaps in their dependence on ρ-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 O(ω-1/2nρ-1/4 sqrt T) and O(ω-1nρ-1/2 T) for convex and strongly convex loss functions, respectively. Up to logarithmic factors in n and ρ-1, these results match the lower bounds in terms of T, n, ρ, and ω.

Related papers