mlsanityData to 7 Oct 2026

Federated Online and Bandit Convex Optimization

arXiv 2311.17586 ↗First posted 29 Nov 2023cs.LG math.OC stat.MLcited by 7

Not on the map. Why?

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.

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

Builds on

34 of 57 references.

References · 34

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Advances and Open Problems in Federated Learningcited by 3,021
  3. 2019Introduction to Online Convex Optimizationcited by 793
  4. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  5. 2014Convex Optimization: Algorithms and Complexitycited by 569
  6. 2018Federated Learning for Mobile Keyboard Predictioncited by 565
  7. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  8. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  9. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  10. 2020Is Local SGD Better than Minibatch SGD?cited by 151
  11. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  12. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
22 more
  1. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
  2. 2020Differentially-Private Federated Linear Banditscited by 83
  3. 2013Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Ratescited by 64
  4. 2021Federated Multi-armed Bandits with Personalizationcited by 62
  5. 2021Federated Linear Contextual Banditscited by 61
  6. 2021Deep Federated Learning for Autonomous Drivingcited by 54
  7. 2020Federated Learning in Vehicular Networkscited by 53
  8. 2019Federated Learning Of Out-Of-Vocabulary Wordscited by 51
  9. 2020Federated Composite Optimizationcited by 49
  10. 2021Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspectivecited by 38
  11. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  12. 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
  13. 2021Asynchronous Upper Confidence Bound Algorithms for Federated Linear Banditscited by 31
  14. 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
  15. 2022A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Banditscited by 28
  16. 2021Communication-Efficient Online Federated Learning Framework for Nonlinear Regressioncited by 16
  17. 2021An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learningcited by 10
  18. 2021A Payload Optimization Method for Federated Recommender Systemscited by 10
  19. 2021The Minimax Complexity of Distributed Optimizationcited by 6
  20. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  21. 2022Addressing modern and practical challenges in machine learning: A survey of online federated and transfer learningcited by 6
  22. 2021Resource-Aware Asynchronous Online Federated Learning for Nonlinear Regressioncited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 0; 2026: 2.

7 papers.

  1. 2024The Limits and Potentials of Local SGD for Distributed Heterogeneous Learning with Intermittent Communicationcited by 12
  2. 2024Personalized Federated Learning with Mixture of Models for Adaptive Prediction and Model Fine-Tuningcited by 8
  3. 2024On the Necessity of Collaboration for Online Model Selection with Decentralized Datacited by 6
  4. 2024Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-upscited by 1
  5. 2026Distributed Online Convex Optimization with Compressed Communication: Optimal Regret and Applicationscited by 1
  6. 2024Multivariate and Online Transfer Learning with Uncertainty Quantificationcited by 0
  7. 2026FedSEA: Achieving Benefit of Parallelization in Federated Online Learningcited by 0