Decentralized Parameter-Free Online Learning with Compressed Gossip
It solves the problem of parameter-free decentralized online learning with compressed communication, which is important for distributed systems with bandwidth constraints.
The paper proposes DECO-EF, a decentralized parameter-free online learning algorithm that achieves the first expected sublinear network-regret guarantees under compressed communication, without requiring tuning of horizon, comparator norm, or learning rate.
We study decentralized online convex optimization when agents communicate over a graph and messages may be compressed. Classical decentralized online methods typically require learning-rate choices that depend on the horizon, comparator scale, or other problem parameters, while compressed communication introduces additional disagreement that must be controlled. We propose DECO-EF (DEcentralized COin-betting with Error Feedback), a decentralized parameter-free online learning algorithm that combines coin-betting predictions with compressed difference-based gossip. Each agent maintains a clean accumulated state and a compressed tracker, and communicates only compressed state differences during gossip steps. The method is parameter-free in the online-learning sense: it does not tune to the horizon, the comparator norm, or the learning rate. We prove expected comparator-adaptive network-regret bounds for DECO-EF under compressed communication. To the best of our knowledge, this gives the first expected sublinear network-regret guarantees for parameter-free decentralized online learning under compressed communication.