# Decentralized Parameter-Free Online Learning with Compressed Gossip

arXiv: https://arxiv.org/abs/2605.27831 · HTML: https://mlsanity.com/paper/2605.27831/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 38 references that are in the map.
- First posted on arXiv 27 May 2026.

## Builds on (most cited first, 24 of 24)

- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization](https://mlsanity.com/paper/1905.13727/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Decentralized Deep Learning with Arbitrary Communication Compression](https://mlsanity.com/paper/1907.09356/) (2019)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2006.11077/) (2020)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism](https://mlsanity.com/paper/2012.11579/) (2020)
- [Online Convex Optimization with Unconstrained Domains and Losses](https://mlsanity.com/paper/1703.02622/) (2017)
- [Comparator-adaptive Convex Bandits](https://mlsanity.com/paper/2007.08448/) (2020)
- [Asynchronous Federated Learning with Bidirectional Quantized Communications and Buffered Aggregation](https://mlsanity.com/paper/2308.00263/) (2023)
- [Gossiped and Quantized Online Multi-Kernel Learning](https://mlsanity.com/paper/2301.09848/) (2023)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Cooperative Online Learning with Feedback Graphs](https://mlsanity.com/paper/2106.04982/) (2021)
- [Distributed Online Optimization with Stochastic Agent Availability](https://mlsanity.com/paper/2411.16477/) (2024)
- [Communication Compression for Distributed Learning without Control Variates](https://mlsanity.com/paper/2412.04538/) (2024)
- [Decentralized Parameter-Free Online Learning](https://mlsanity.com/paper/2510.15644/) (2025)

## Abstract (arXiv)

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.