# Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 38 references that are in the map.
- First posted on arXiv 8 Jan 2026.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (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)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Gradient Sparsification for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1710.09854/) (2017)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Communication Compression for Decentralized Training](https://mlsanity.com/paper/1803.06443/) (2018)
- [Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression](https://mlsanity.com/paper/2206.03665/) (2022)
- [3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation](https://mlsanity.com/paper/2202.00998/) (2022)
- [Projection-free Distributed Online Learning with Sublinear Communication Complexity](https://mlsanity.com/paper/2103.11102/) (2021)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Optimal and Efficient Algorithms for Decentralized Online Convex Optimization](https://mlsanity.com/paper/2402.09173/) (2024)
- [Quantized Distributed Online Projection-free Convex Optimization](https://mlsanity.com/paper/2302.13559/) (2023)

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

- [Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications](https://mlsanity.com/paper/2604.09276/) (2026)
- [Revisiting Decentralized Online Convex Optimization with Compressed Communication](https://mlsanity.com/paper/2607.01665/) (2026)

## Abstract (arXiv)

We investigate distributed online convex optimization with compressed communication, where n learners connected by a network collaboratively minimize a sequence of global loss functions using only local information and compressed data from neighbors. Prior work has established regret bounds of O(maxω-2ρ-4n1/2,ω-4ρ-8n√T) and O(maxω-2ρ-4n1/2,ω-4ρ-8nlnT) for convex and strongly convex functions, respectively, where ω∈(0,1] is the compression quality factor (ω=1 means no compression) and ρ<1 is the spectral gap of the communication matrix. However, these regret bounds suffer from a quadratic or even quartic dependence on ω-1. Moreover, the super-linear dependence on n is also undesirable. To overcome these limitations, we propose a novel algorithm that achieves improved regret bounds of tildeO(ω-1/2ρ-1n√T) and tildeO(ω-1ρ-2nlnT) for convex and strongly convex functions, respectively. The primary idea is to design a two-level blocking update framework incorporating two novel ingredients: an online gossip strategy and an error compensation scheme, which collaborate to achieve a better consensus among learners. Furthermore, we establish the first lower bounds for this problem, justifying the optimality of our results with respect to both ω and T. Additionally, we consider the bandit feedback scenario, and extend our method with the classic gradient estimators to enhance existing regret bounds.