# Projection-free Distributed Online Learning with Sublinear Communication Complexity

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 46 references that are in the map.
- First posted on arXiv 20 Mar 2021.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Revisiting Projection-free Online Learning: the Strongly Convex Case](https://mlsanity.com/paper/2010.07572/) (2020)
- [Projection-free Online Learning over Strongly Convex Sets](https://mlsanity.com/paper/2010.08177/) (2020)
- [A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization](https://mlsanity.com/paper/1301.4666/) (2013)
- [Projection-Free Bandit Convex Optimization](https://mlsanity.com/paper/1805.07474/) (2018)
- [Improved Regret Bounds for Projection-free Bandit Convex Optimization](https://mlsanity.com/paper/1910.03374/) (2019)
- [O(logT) Projections for Stochastic Optimization of Smooth and Strongly Convex Functions](https://mlsanity.com/paper/1304.0740/) (2013)

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

- [Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees](https://mlsanity.com/paper/2305.11726/) (2023)
- [Improved Dynamic Regret for Online Frank-Wolfe](https://mlsanity.com/paper/2302.05620/) (2023)
- [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)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Projection-free Online Learning with Arbitrary Delays](https://mlsanity.com/paper/2204.04964/) (2022)
- [A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization](https://mlsanity.com/paper/2512.23190/) (2025)
- [Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization](https://mlsanity.com/paper/2406.03787/) (2024)
- [Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds](https://mlsanity.com/paper/2601.04907/) (2026)
- [Decentralized Personalized Online Federated Learning](https://mlsanity.com/paper/2311.04817/) (2023)
- [Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions](https://mlsanity.com/paper/2602.09502/) (2026)
- [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)

To deal with complicated constraints via locally light computations in distributed online learning, a recent study has presented a projection-free algorithm called distributed online conditional gradient (D-OCG), and achieved an O(T3/4) regret bound for convex losses, where T is the number of total rounds. However, it requires T communication rounds, and cannot utilize the strong convexity of losses. In this paper, we propose an improved variant of D-OCG, namely D-BOCG, which can attain the same O(T3/4) regret bound with only O(√T) communication rounds for convex losses, and a better regret bound of O(T2/3(log T)1/3) with fewer O(T1/3(log T)2/3) communication rounds for strongly convex losses. The key idea is to adopt a delayed update mechanism that reduces the communication complexity, and redefine the surrogate loss function in D-OCG for exploiting the strong convexity. Furthermore, we provide lower bounds to demonstrate that the O(√T) communication rounds required by D-BOCG are optimal (in terms of T) for achieving the O(T3/4) regret with convex losses, and the O(T1/3(log T)2/3) communication rounds required by D-BOCG are near-optimal (in terms of T) for achieving the O(T2/3(log T)1/3) regret with strongly convex losses up to polylogarithmic factors. Finally, to handle the more challenging bandit setting, in which only the loss value is available, we incorporate the classical one-point gradient estimator into D-BOCG, and obtain similar theoretical guarantees.