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.
Introduction
In modern robotics and Internet of Things (IoT) ecosystems, multi-agent systems—such as drone swarms or autonomous sensor networks—must often collaborate to track dynamic targets while navigating complex environments. This task is complicated by three primary constraints: information scarcity, communication bottlenecks, and the non-stationary nature of the environment.
First, agents frequently lack access to "first-order" information (gradients), such as the exact velocity or acceleration of a target. Instead, they rely on "zeroth-order" observations, such as simple distance measurements. Second, in a Federated Learning (FL) architecture, transmitting high-dimensional model updates between agents and a central server can overwhelm limited bandwidth. Finally, target tracking is inherently an "online" optimization problem; the objective function shifts at every time step as targets move, requiring the system to adapt in real-time.
This paper introduces FED-EF-ZO-SGD, a novel framework designed to address these challenges by integrating zeroth-order gradient estimation with error-feedback compression within a distributed online optimization setting.
The FED-EF-ZO-SGD Framework
The proposed algorithm, Federated Error-Feedback Zeroth-Order Stochastic Gradient Descent (FED-EF-ZO-SGD), relies on three integrated components to ensure efficient and safe coordination:
- Zeroth-Order (ZO) Gradient Estimation: To overcome the lack of direct gradient access, agents estimate the gradient of their local loss functions by performing two function evaluations at slightly perturbed points. This randomized smoothing technique allows the agents to approximate the direction of descent using only distance-based observations.
- Contractive Compression: To minimize communication overhead, agents apply compression operators to their updates before transmission. Supported schemes include Top-k (sending only the $k$ largest coordinates), Rand-k (randomly selecting coordinates), and 1-bit Quantization.
- Error Feedback (EF): A critical challenge with compression is the loss of information. FED-EF-ZO-SGD utilizes an error-feedback mechanism where the difference between the actual update and the compressed update is stored locally. This "residual" is added to the subsequent update, ensuring that the information lost during compression is eventually incorporated into the global model.
Theoretical Contributions
A significant portion of this work is dedicated to establishing the theoretical convergence of the algorithm under non-convex and non-stationary conditions. Unlike traditional analyses that rely on the restrictive "bounded gradient" assumption, the authors employ a more relaxed "intertwined perturbation analysis."
The theoretical results demonstrate that the algorithm achieves a $\xi$-accurate first-order solution with a complexity of $T = \mathcal{O}(1/\xi^2)$. Remarkably, the analysis shows that the dominant term in the convergence rate is independent of the compression ratio. This implies that agents can aggressively compress their communications to save bandwidth without a proportional degradation in the long-term convergence rate.
Experimental Evaluation
The performance of FED-EF-ZO-SGD was evaluated through two primary simulation scenarios:
- Multi-Agent Target Tracking: Five agents were tasked with tracking five actively evading sources on a 2D plane. The agents were required to maintain a safe distance from one another while minimizing the distance to their respective targets.
- Area Coverage Patrolling: Multiple UAVs patrolled circular routes with overlapping regions. The objective was to maximize area coverage while minimizing "area violations" (collisions).
The algorithm was compared against several baselines, including non-communicating SGD (SGDm) and standard Federated Averaging (FedAvg).
Key Results and Insights
The numerical experiments yielded several key findings:
- Safety and Coordination: In the tracking simulations, the federated approach significantly improved safety. While non-communicating baselines resulted in approximately 70 collisions, the proposed FL schemes reduced this number to fewer than 10.
- The Efficiency of 1-Bit Quantization: Surprisingly, 1-bit quantization with error feedback (QSGD1b-EF) occasionally outperformed the "No Compression" baseline. The authors hypothesize that the noise introduced by quantization may act as a regularizer, helping the optimization process escape local minima in the non-convex landscape.
- Scalability: Increasing the number of agents ($N$) was found to have an effect similar to increasing the batch size in centralized learning, effectively accelerating convergence through the aggregation of diverse local information.
Conclusion and Future Directions
FED-EF-ZO-SGD provides a robust solution for multi-agent coordination under strict communication and information constraints. By proving that compression can be achieved "at no cost" to the dominant convergence term, this work paves the way for more efficient distributed robotics.
Future research directions include addressing the dimensionality scaling inherent in zeroth-order methods and exploring "Personalized Federated Learning" to better accommodate agents operating in heterogeneous local environments. Additionally, adaptively tuning the regularization parameters for collision avoidance could further enhance the safety profiles of these systems in highly dynamic settings.
Summary updated