Optimal Regret for Communication-Efficient Decentralized Online Learning
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
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis
- (Mis)generalization of Helpful-Only Fine-tuning