TY - JOUR
T1 - Decentralized Multi-Agent Stochastic Optimization with Pairwise Constraints and Quantized Communications
AU - Cao, Xuanyu
AU - Basar, Tamer
N1 - Manuscript received September 13, 2019; revised January 28, 2020; accepted May 21, 2020. Date of publication May 28, 2020; date of current version June 16, 2020. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Soummya Kar. This work was supported by the Army Research Laboratory under Cooperative Agreement Number W911NF-17-2-0196. (Corresponding author: Xuanyu Cao.) The authors are with Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801-3028 USA (e-mail: xyc@ illinois.edu; [email protected]).
PY - 2020
Y1 - 2020
N2 - Decentralized optimization methods often entail information exchange between neighbors. In many circumstances, due to the limited communication bandwidth, the exchanged information has to be quantized. In this paper, we investigate the impact of quantization on the performance of decentralized stochastic optimization. We consider a multi-agent network, in which each node is associated with a stochastic cost and each pair of neighbors is associated with a constraint. The goal of the network is to minimize the aggregate expected cost subject to all the constraints. We first develop a decentralized stochastic saddle point algorithm with quantized communications for the scenario of sample feedback, in which a sample of the random variable in the stochastic cost function is revealed to each node at each time. We establish performance bounds for the expected cost suboptimality and expected constraint violations of the algorithm in terms of the quantization intervals. We show that asymptotic optimality can be achieved if the quantization intervals approach zero. On the other hand, if the quantization intervals are fixed and nonzero, then non-diminishing performance gaps exist, which indicate a tradeoff between optimization performance and communication overhead. We further extend the algorithm and analysis to the scenario of bandit feedback, where samples of the random variables are not available and only the values of the cost function at two random points close to the current decision are disclosed. We show that the performance of the algorithm does not degrade in order sense compared to its counterpart with sample feedback. Finally, two numerical examples, namely decentralized quadratically constrained quadratic program and decentralized logistic regression, are presented to corroborate the efficacy of the proposed algorithms.
AB - Decentralized optimization methods often entail information exchange between neighbors. In many circumstances, due to the limited communication bandwidth, the exchanged information has to be quantized. In this paper, we investigate the impact of quantization on the performance of decentralized stochastic optimization. We consider a multi-agent network, in which each node is associated with a stochastic cost and each pair of neighbors is associated with a constraint. The goal of the network is to minimize the aggregate expected cost subject to all the constraints. We first develop a decentralized stochastic saddle point algorithm with quantized communications for the scenario of sample feedback, in which a sample of the random variable in the stochastic cost function is revealed to each node at each time. We establish performance bounds for the expected cost suboptimality and expected constraint violations of the algorithm in terms of the quantization intervals. We show that asymptotic optimality can be achieved if the quantization intervals approach zero. On the other hand, if the quantization intervals are fixed and nonzero, then non-diminishing performance gaps exist, which indicate a tradeoff between optimization performance and communication overhead. We further extend the algorithm and analysis to the scenario of bandit feedback, where samples of the random variables are not available and only the values of the cost function at two random points close to the current decision are disclosed. We show that the performance of the algorithm does not degrade in order sense compared to its counterpart with sample feedback. Finally, two numerical examples, namely decentralized quadratically constrained quadratic program and decentralized logistic regression, are presented to corroborate the efficacy of the proposed algorithms.
KW - Decentralized optimization
KW - bandit feedback
KW - quantization
KW - sample feedback
KW - stochastic optimiza-tion
UR - http://www.scopus.com/inward/record.url?scp=85087338248&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087338248&partnerID=8YFLogxK
U2 - 10.1109/TSP.2020.2997394
DO - 10.1109/TSP.2020.2997394
M3 - Article
AN - SCOPUS:85087338248
SN - 1053-587X
VL - 68
SP - 3296
EP - 3311
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
M1 - 9103200
ER -