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

Ege C. Kaya, Mehmet Berk Sahin, Abolfazl Hashemi

TL;DR

This paper introduces FED-EF-ZO-SGD, a novel framework for multi-agent target tracking that works even when agents can only sense distances (zeroth-order information) and must operate under strict communication constraints. By combining error-feedback compression with zeroth-order gradient estimation, the authors prove that distributed agents can achieve high-performance coordination and collision avoidance with a convergence rate that is effectively independent of how much the data is compressed.

What Problem Does This Paper Address?

In many real-world robotics and IoT scenarios, agents (like delivery drones or mobile sensors) need to collaborate to track moving targets while avoiding collisions. This presents three major technical hurdles:

  1. Information Scarcity (Zeroth-Order): Agents often lack access to complex "first-order" information like velocity or acceleration gradients. They might only know their current distance to a target—a "zeroth-order" observation.
  2. Communication Bottlenecks: In a Federated Learning (FL) setup, sending high-dimensional model updates between agents and a central server is slow and expensive.
  3. Dynamic Environments: Unlike static image recognition, target tracking is an "online" problem where the objective function changes at every time step as targets move.

Existing solutions often rely on overly restrictive assumptions (like "bounded gradients") that don't hold up in the messy, non-convex reality of multi-agent navigation.

Methods

The authors propose the FED-EF-ZO-SGD (Federated Error-Feedback Zeroth-Order Stochastic Gradient Descent) algorithm. Its "secret sauce" lies in three components:

  • Zeroth-Order (ZO) Gradient Estimation: Since agents can't see gradients, they estimate them by taking two function evaluations (e.g., sensing distance at two slightly different points) and using a randomized smoothing technique.
  • Contractive Compression: To save bandwidth, agents compress their updates using techniques like Top-k (sending only the largest values), Rand-k (sending random values), or 1-bit Quantization.
  • Error Feedback (EF): This is the crucial "memory" component. Instead of just throwing away the data lost during compression, agents store the "compression error" and add it back into the next update. This ensures that no information is permanently lost, only delayed.

Theoretically, the authors employ a new "intertwined perturbation analysis" to prove convergence under much more relaxed assumptions than previous literature, specifically allowing for gradients that grow proportionally to their expected value.

Datasets

The paper evaluates the algorithm using custom-designed simulation environments rather than standard static datasets, reflecting the "online" nature of the problem:

  • Multi-Agent Target Tracking: A simulation involving 5 agents tracking 5 actively evading sources on a 2D plane.
  • Area Coverage Patrolling: A scenario where multiple UAVs must patrol designated circular routes with overlapping regions, aiming to maximize coverage while minimizing "area violations" (collisions).
  • Benchmark Baselines: The authors compare their method against non-communicating SGD (SGDm) and standard Federated Averaging (FedAvg).

Key Insights and Ideas

  • Compression at "No Cost": The most striking theoretical finding is that the dominant term in the convergence rate is independent of the compression ratio. This means you can compress your data aggressively to save bandwidth without hurting the final accuracy in the long run.
  • Quantization as a Feature, Not a Bug: In numerical experiments, 1-bit quantization with error feedback (QSGD1b-EF) actually outperformed the "No Compression" setting. The authors suggest the inherent noise introduced by quantization might help the algorithm escape local minima in non-convex landscapes.
  • The "Batch Size" Effect: Increasing the number of agents ($N$) in the federated setting acts similarly to increasing the batch size in traditional deep learning, accelerating convergence by aggregating more diverse information at the server.
  • Collision Avoidance via Regularization: By adding a non-convex regularization term to the local loss functions, the authors successfully integrated safety constraints directly into the optimization process.

Key Results

  • Convergence: The algorithm achieves a $\xi$-accurate first-order solution with a complexity of $T = \mathcal{O}(1/\xi^2)$, matching the rate of more information-heavy first-order methods.
  • Safety: In tracking simulations, the proposed FL schemes reduced the number of collisions from ~70 (in non-communicating baselines) to fewer than 10.
  • Efficiency: The method maintained high tracking accuracy even when updates were compressed down to a single bit, proving its viability for communication-constrained hardware.

Limitations and Future Work

  • Dimensionality Scaling: Like most zeroth-order methods, the complexity still scales with the dimension ($d$) of the problem. In extremely high-dimensional spaces, the gradient estimation might become too slow.
  • Fixed Hyperparameters: The regularization parameter ($\lambda$) for collision avoidance was fixed during experiments. The authors suggest that adaptively tuning this parameter—similar to safe reinforcement learning—is a promising next step.
  • Personalization: The current model uses simple averaging at the server. Future work could explore "Personalized Federated Learning," where the server tailors updates to the specific local environment of each agent.

Summary updated

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.
BibTeX
@article{kaya2023communication,
  author = {Ege C. Kaya and Mehmet Berk Sahin and Abolfazl Hashemi},
  title = {{Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications}},
  journal = {IEEE Access},
  year = {2023},
  doi = {10.1109/access.2023.3284891},
}

Loading related content...

Figure