# Distributed Online Learning for Joint Regret with Communication Constraints

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

## Key facts

- Cited by 5 papers in the map (data through 7 Oct 2026).
- Builds on 36 of its 78 references that are in the map.
- First posted on arXiv 15 Feb 2021.

## Builds on (most cited first, 30 of 36)

- [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)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [MetaGrad: Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/1604.08740/) (2016)
- [Adaptive Gradient Quantization for Data-Parallel SGD](https://mlsanity.com/paper/2010.12460/) (2020)
- [Optimal Algorithms for Non-Smooth Distributed Optimization in Networks](https://mlsanity.com/paper/1806.00291/) (2018)
- [Optimal Gradient Compression for Distributed and Federated Learning](https://mlsanity.com/paper/2010.03246/) (2020)
- [Online Learning Without Prior Information](https://mlsanity.com/paper/1703.02629/) (2017)
- [A Distributed Synchronous SGD Algorithm with Global Top-k Sparsification for Low Bandwidth Networks](https://mlsanity.com/paper/1901.04359/) (2019)
- [PowerGossip: Practical Low-Rank Communication Compression in Decentralized Deep Learning](https://mlsanity.com/paper/2008.01425/) (2020)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Parameter-Free Online Convex Optimization with Sub-Exponential Noise](https://mlsanity.com/paper/1902.01500/) (2019)
- [CSER: Communication-efficient SGD with Error Reset](https://mlsanity.com/paper/2007.13221/) (2020)
- [MetaGrad: Adaptation using Multiple Learning Rates in Online Learning](https://mlsanity.com/paper/2102.06622/) (2021)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [Cooperative Online Learning: Keeping your Neighbors Updated](https://mlsanity.com/paper/1901.08082/) (2019)
- [Combining Online Learning Guarantees](https://mlsanity.com/paper/1902.09003/) (2019)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism](https://mlsanity.com/paper/2012.11579/) (2020)

## Built on by (most cited first, 5 of 5)

- [Nonstochastic Bandits and Experts with Arm-Dependent Delays](https://mlsanity.com/paper/2111.01589/) (2021)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Multitask Online Learning: Listen to the Neighborhood Buzz](https://mlsanity.com/paper/2310.17385/) (2023)
- [Decentralized Parameter-Free Online Learning](https://mlsanity.com/paper/2510.15644/) (2025)
- [Decentralized Parameter-Free Online Learning with Compressed Gossip](https://mlsanity.com/paper/2605.27831/) (2026)

## Abstract (arXiv)

We consider distributed online learning for joint regret with communication constraints. In this setting, there are multiple agents that are connected in a graph. Each round, an adversary first activates one of the agents to issue a prediction and provides a corresponding gradient, and then the agents are allowed to send a b-bit message to their neighbors in the graph. All agents cooperate to control the joint regret, which is the sum of the losses of the activated agents minus the losses evaluated at the best fixed common comparator parameters u. We observe that it is suboptimal for agents to wait for gradients that take too long to arrive. Instead, the graph should be partitioned into local clusters that communicate among themselves. Our main result is a new method that can adapt to the optimal graph partition for the adversarial activations and gradients, where the graph partition is selected from a set of candidate partitions. A crucial building block along the way is a new algorithm for online convex optimization with delayed gradient information that is comparator-adaptive, meaning that its joint regret scales with the norm of the comparator ||u||. We further provide near-optimal gradient compression schemes depending on the ratio of b and the dimension times the diameter of the graph.