Communication-Efficient Zeroth-Order Distributed Online Optimization:
  Algorithm, Theory, and Applications
Ege C. Kaya M. Berk Sahin Abolfazl Hashemi
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.