pipette
ENEnglish

Optimal Regret for Communication-Efficient Decentralized Online Learning

Sifan Yang, Wenhao Yang, Wei Jiang, Yuanyu Wan, and Lijun Zhang

Preprint

En palabras de los autores

In this paper, we investigate decentralized online convex optimization with compressed communication, where 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 and for convex and strongly convex loss functions, respectively, where is the spectral gap of the communication matrix and is the compression quality factor. Compared with the corresponding lower bounds of and , these upper bounds exhibit polynomial gaps in their dependence on . 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 and for convex and strongly convex loss functions, respectively. Up to logarithmic factors in and , these results match the lower bounds in terms of , , , and .

Resultado principalLimitación que admiten los autores

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.