Decentralized Multi-Agent Stochastic Optimization with Pairwise Constraints and Quantized Communications

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.