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

Xuanyu Cao, Tamer Basar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number9103200
Pages (from-to)3296-3311
Number of pages16
JournalIEEE Transactions on Signal Processing
StatePublished - 2020
Externally publishedYes


  • Decentralized optimization
  • bandit feedback
  • quantization
  • sample feedback
  • stochastic optimiza-tion

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Decentralized Multi-Agent Stochastic Optimization with Pairwise Constraints and Quantized Communications'. Together they form a unique fingerprint.

Cite this