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

Abstract

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.

arXiv comment21 pages, 5 figures, and this paper has been accepted by IEEE Access

References in corpus (19)

• Federated Learning with Non-IID Data
• QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization
• Safe, Efficient, and Comfortable Velocity Control based on Reinforcement Learning for Autonomous Driving
• Asynchronous Federated Optimization
• Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Function
• Robust Localization and Tracking of Simultaneous Moving Sound Sources Using Beamforming and Particle Filtering
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Preserving Privacy and Security in Federated Learning
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback
• Communication-Efficient Stochastic Zeroth-Order Optimization for Federated Learning
• On the Convergence of Decentralized Gradient Descent
• On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Data
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization