mlsanityData to 7 Oct 2026

Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications

arXiv 2306.05655 ↗First posted 9 Jun 2023cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper focuses on a multi-agent zeroth-order online optimization problem in a federated learning setting for target tracking. The agents only sense their current distances to their targets and aim to maintain a minimum safe distance from each other to prevent collisions. The coordination among the agents and dissemination of collision-prevention information is managed by a central server using the federated learning paradigm. The proposed formulation leads to an instance of distributed online nonconvex optimization problem that is solved via a group of communication-constrained agents. To deal with the communication limitations of the agents, an error feedback-based compression scheme is utilized for agent-to-server communication. The proposed algorithm is analyzed theoretically for the general class of distributed online nonconvex optimization problems. We provide non-asymptotic convergence rates that show the dominant term is independent of the characteristics of the compression scheme. Our theoretical results feature a new approach that employs significantly more relaxed assumptions in comparison to standard literature. The performance of the proposed solution is further analyzed numerically in terms of tracking errors and collisions between agents in two relevant applications.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 40 of its 67 references that are in the map. First posted on arXiv 9 Jun 2023.

Builds on

40 of 67 references.

References · 40

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Learning with Non-IID Datacited by 1,099
  3. 2020Adaptive Federated Optimizationcited by 1,036
  4. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  5. 2019Introduction to Online Convex Optimizationcited by 793
  6. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  7. 2018Sparsified SGD with Memorycited by 373
  8. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  9. 2019Error Feedback Fixes SignSGD and other Gradient Compression Schemescited by 306
  10. 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
  11. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  12. 2019Asynchronous Federated Optimizationcited by 264
28 more
  1. 2019Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communicationcited by 218
  2. 2019SGD: General Analysis and Improved Ratescited by 206
  3. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  4. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  5. 2013On the Convergence of Decentralized Gradient Descentcited by 158
  6. 2018Stochastic Gradient Push for Distributed Deep Learningcited by 152
  7. 2016QSGD: Communication-Efficient SGD via Gradient Quantization and Encodingcited by 147
  8. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  9. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  10. 2022Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learningcited by 59
  11. 2019Safe, Efficient, and Comfortable Velocity Control based on Reinforcement Learning for Autonomous Drivingcited by 56
  12. 2019Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedbackcited by 49
  13. 2020Faster Non-Convex Federated Learning via Global and Local Momentumcited by 48
  14. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  15. 2019Communication-Efficient Distributed Learning via Lazily Aggregated Quantized Gradientscited by 32
  16. 2020Time-Varying Convex Optimization: Time-Structured Algorithms and Applicationscited by 31
  17. 2017Bandit Convex Optimization for Scalable and Dynamic IoT Managementcited by 24
  18. 2017Navigating Occluded Intersections with Autonomous Vehicles using Deep Reinforcement Learningcited by 21
  19. 2021Robust Training in High Dimensions via Block Coordinate Geometric Median Descentcited by 20
  20. 2022Preserving Privacy and Security in Federated Learningcited by 13
  21. 2020Tracking and regret bounds for online zeroth-order Euclidean and Riemannian optimisationcited by 12
  22. 2022A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimizationcited by 12
  23. 2021Communication-Efficient Variance-Reduced Decentralized Stochastic Optimization over Time-Varying Directed Graphscited by 9
  24. 2015Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Functioncited by 8
  25. 2020Decentralized Optimization On Time-Varying Directed Graphs Under Communication Constraintscited by 5
  26. 2022Stochastic Zeroth-order Functional Constrained Optimization: Oracle Complexity and Applicationscited by 5
  27. 2016Robust Localization and Tracking of Simultaneous Moving Sound Sources Using Beamforming and Particle Filteringcited by 2
  28. 2020Optimization with Zeroth-Order Oracles in Formationcited by 1

Built on by

Not cited yet.