TY - JOUR
T1 - Distributed Constrained Online Convex Optimization over Multiple Access Fading Channels
AU - Cao, Xuanyu
AU - Basar, Tamer
N1 - Funding Information:
This work was supported by the Army Research Laboratory under Cooperative Agreement Number W911NF-17-2-0196.
Publisher Copyright:
© 1991-2012 IEEE.
PY - 2022
Y1 - 2022
N2 - In this paper, we study distributed constrained online convex optimization for a wireless system consisting of a parameter server and multiple agents. Each agent has a local constraint function and a time-varying local loss function, and needs to choose sequential actions based on causal information. The goal of the overall system is to minimize the accumulated total loss of all agents over a time horizon subject to total constraints of the agents. To this end, the agents communicate with the server over multiple access noisy fading channels, where the information is exchanged imperfectly. We first consider the full information scenario, where the local loss function of each agent is fully revealed to the corresponding agent in each time slot. We propose a modified saddle-point algorithm, where each agent sends an analog signal pertaining to the current value of the local constraint function and the server receives a superposition of these signals distorted by the noisy fading channels. We analyze the performance of the proposed algorithm, and establish $ O(T)$ regret bound and $ O(T)$ constraint violation bound for the algorithm, where $T$ is the time horizon. Further, we extend the algorithm and performance analyses to the scenario of bandit feedback, where only the values of the local loss functions at two random points are disclosed to the agents in every time slot. In such a case, performance bounds similar to the full information scenario are established. Finally, numerical examples are presented to corroborate the efficacy of the proposed algorithms.
AB - In this paper, we study distributed constrained online convex optimization for a wireless system consisting of a parameter server and multiple agents. Each agent has a local constraint function and a time-varying local loss function, and needs to choose sequential actions based on causal information. The goal of the overall system is to minimize the accumulated total loss of all agents over a time horizon subject to total constraints of the agents. To this end, the agents communicate with the server over multiple access noisy fading channels, where the information is exchanged imperfectly. We first consider the full information scenario, where the local loss function of each agent is fully revealed to the corresponding agent in each time slot. We propose a modified saddle-point algorithm, where each agent sends an analog signal pertaining to the current value of the local constraint function and the server receives a superposition of these signals distorted by the noisy fading channels. We analyze the performance of the proposed algorithm, and establish $ O(T)$ regret bound and $ O(T)$ constraint violation bound for the algorithm, where $T$ is the time horizon. Further, we extend the algorithm and performance analyses to the scenario of bandit feedback, where only the values of the local loss functions at two random points are disclosed to the agents in every time slot. In such a case, performance bounds similar to the full information scenario are established. Finally, numerical examples are presented to corroborate the efficacy of the proposed algorithms.
KW - Online convex optimization
KW - channel fading
KW - channel noise
KW - constrained optimization
KW - distributed optimization
KW - multiple access
UR - http://www.scopus.com/inward/record.url?scp=85133736308&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85133736308&partnerID=8YFLogxK
U2 - 10.1109/TSP.2022.3185897
DO - 10.1109/TSP.2022.3185897
M3 - Article
AN - SCOPUS:85133736308
SN - 1053-587X
VL - 70
SP - 3468
EP - 3483
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
ER -