Distributed discrete-time optimization by exchanging one bit of information

Jiaqi Zhang, Keyou You, Tamer Başar

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This paper proposes a distributed discrete-time algorithm to solve an additive cost optimization problem over undirected deterministic or time-varying graphs. Different from most previous methods that require to exchange exact states between nodes, each node in our algorithm needs only the sign of the relative state between its neighbors, which is clearly one bit of information. Our analysis is based on optimization theory rather than Lyapunov theory or algebraic graph theory. The latter is commonly used in existing literature, especially in the continuous-time algorithm design, and is difficult to apply in our case. Besides, an optimization-theory-based analysis may make our results more extendible. In particular, our convergence proofs are based on the convergences of the subgradient method and the stochastic subgradient method. Moreover, the convergence rate of our algorithm can vary from O(1/\ln(k)) to O(1/√k), depending on the choice of the stepsize. A quantile regression problem is included to illustrate the performance of our algorithm using simulations.

Original languageEnglish (US)
Title of host publication2018 Annual American Control Conference, ACC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Print)9781538654286
StatePublished - Aug 9 2018
Externally publishedYes
Event2018 Annual American Control Conference, ACC 2018 - Milwauke, United States
Duration: Jun 27 2018Jun 29 2018

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619


Other2018 Annual American Control Conference, ACC 2018
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Distributed discrete-time optimization by exchanging one bit of information'. Together they form a unique fingerprint.

Cite this