arXiv preprint ·
Optimal Regret for Communication-Efficient Decentralized Online Learning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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/2}nρ^{-1}\sqrt{T\ln n})$ and $O(ω^{-1}nρ^{-2}\ln n\ln 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/2}nρ^{-1/4}\sqrt{T})$ and $Ω(ω^{-1}nρ^{-1/2}\ln 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 $\widetilde O(ω^{-1/2}nρ^{-1/4}\sqrt{T})$ and $\widetilde O(ω^{-1}nρ^{-1/2}\ln 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 $ω$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Jailbreak Connectivity: Towards Diverse, Transferable, and Universal Multimodal Large Language Model Jailbreak
PhysicsNeMo-Mesh: GPU-Native Meshes and Simulation Cases for Physics AI
Nemotron 3.5 Super and Lightning: Open, Efficient Mixture-of-Experts Hybrid Mamba-Transformer Models for Agentic AI
Tactus: Tactile & Pose Sensing Glove for Natural Dexterity Data Collection
Evaluating Causal Reasoning in LLMs: A Case Study in the Challenges of Procedural Generation
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.