TY - JOUR
T1 - Decentralized Online Convex Optimization with Event-Triggered Communications
AU - Cao, Xuanyu
AU - Basar, Tamer
N1 - Funding Information:
Manuscript received August 29, 2020; revised November 15, 2020; accepted December 11, 2020. Date of publication December 17, 2020; date of current version January 5, 2021. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Emilie Chouzenoux. This work was supported by the Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196. (Corresponding author: Xuanyu Cao.) The authors are with the Coordinated Science Lab, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail: xyc@illinois.edu; basar1@illinois.edu). Digital Object Identifier 10.1109/TSP.2020.3044843
Publisher Copyright:
© 1991-2012 IEEE.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
KW - Decentralized optimization
KW - event-triggering
KW - online convex optimization
UR - http://www.scopus.com/inward/record.url?scp=85098758878&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85098758878&partnerID=8YFLogxK
U2 - 10.1109/TSP.2020.3044843
DO - 10.1109/TSP.2020.3044843
M3 - Article
AN - SCOPUS:85098758878
VL - 69
SP - 284
EP - 299
JO - IRE Transactions on Audio
JF - IRE Transactions on Audio
SN - 1053-587X
M1 - 9296963
ER -