Decentralized Online Convex Optimization With Event-Triggered Communications

摘要

Decentralized multi-agent optimization usually relies on information exchange between neighboring agents, which can incur unaffordable communication overhead in practice. To reduce the communication cost, we apply event-triggering technique to the decentralized multi-agent online convex optimization problem, where each agent is associated with a time-varying local loss function and the goal is to minimize the accumulated total loss (the sum of all local loss functions) by choosing appropriate actions sequentially. We first develop an event-triggered decentralized online subgradient descent algorithm for the full information case, where the local loss function is fully revealed to each agent at each time. We establish an upper bound for the regret of each agent in terms of the event-triggering thresholds. It is shown that the regret is sublinear provided that the event-triggering thresholds converge to zero as time goes to infinity. The algorithm and analysis are further extended to the scenario of bandit feedback, where only the values of the local loss function at two random points close to the current action are disclosed to each agent. We show that the two-point bandit feedback does not degrade the performance of the proposed algorithm in order sense and a regret bound similar to the full information case can be established. Finally, numerical results on the problem of decentralized online least squares are presented to validate the proposed algorithms.