# Federated Online and Bandit Convex Optimization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 57 references that are in the map.
- First posted on arXiv 29 Nov 2023.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [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)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Federated Learning for Mobile Keyboard Prediction](https://mlsanity.com/paper/1811.03604/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Deep Federated Learning for Autonomous Driving](https://mlsanity.com/paper/2110.05754/) (2021)
- [Federated Learning in Vehicular Networks](https://mlsanity.com/paper/2006.01412/) (2020)
- [Federated Learning Of Out-Of-Vocabulary Words](https://mlsanity.com/paper/1903.10635/) (2019)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective](https://mlsanity.com/paper/2111.03741/) (2021)
- [On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data](https://mlsanity.com/paper/2206.04723/) (2022)
- [Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization](https://mlsanity.com/paper/1805.10222/) (2018)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Communication-Efficient Online Federated Learning Framework for Nonlinear Regression](https://mlsanity.com/paper/2110.06556/) (2021)
- [An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning](https://mlsanity.com/paper/2106.02720/) (2021)
- [A Payload Optimization Method for Federated Recommender Systems](https://mlsanity.com/paper/2107.13078/) (2021)

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

- [The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communication](https://mlsanity.com/paper/2405.11667/) (2024)
- [Personalized Federated Learning with Mixture of Models for Adaptive Prediction and Model Fine-Tuning](https://mlsanity.com/paper/2410.21547/) (2024)
- [On the Necessity of Collaboration for Online Model Selection with Decentralized Data](https://mlsanity.com/paper/2404.09494/) (2024)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)
- [Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applications](https://mlsanity.com/paper/2604.09276/) (2026)
- [Multivariate and Online Transfer Learning with Uncertainty Quantification](https://mlsanity.com/paper/2411.12555/) (2024)
- [FedSEA: Achieving Benefit of Parallelization in Federated Online Learning](https://mlsanity.com/paper/2604.19336/) (2026)

## Abstract (arXiv)

We study the problems of distributed online and bandit convex optimization against an adaptive adversary. We aim to minimize the average regret on M machines working in parallel over T rounds with R intermittent communications. Assuming the underlying cost functions are convex and can be generated adaptively, our results show that collaboration is not beneficial when the machines have access to the first-order gradient information at the queried points. This is in contrast to the case for stochastic functions, where each machine samples the cost functions from a fixed distribution. Furthermore, we delve into the more challenging setting of federated online optimization with bandit (zeroth-order) feedback, where the machines can only access values of the cost functions at the queried points. The key finding here is identifying the high-dimensional regime where collaboration is beneficial and may even lead to a linear speedup in the number of machines. We further illustrate our findings through federated adversarial linear bandits by developing novel distributed single and two-point feedback algorithms. Our work is the first attempt towards a systematic understanding of federated online optimization with limited feedback, and it attains tight regret bounds in the intermittent communication setting for both first and zeroth-order feedback. Our results thus bridge the gap between stochastic and adaptive settings in federated online optimization.