Decentralized online optimization with global objectives and local communication

Angelia Nedic, Soomin Lee, Maxim Raginsky

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

32 Scopus citations


We consider a decentralized online convex optimization problem in a static undirected network of agents, where each agent controls only a coordinate (or a part) of the global decision vector. For such a problem, we propose a decentralized variant of Nesterov's primal-dual algorithm with dual averaging. To mitigate the disagreements on the primal-vector updates, the agents implement a generalization of the local information-exchange dynamics recently proposed by Li and Marden [1]. We show that the regret has sublinear growth of O (√T) with the time horizon T when the stepsize is of the form 1/√t and the objective functions are Lipschitzcontinuous convex functions with Lipschitz gradients. We prove an analogous bound on the expected regret for the stochastic variant of the algorithm.

Original languageEnglish (US)
Title of host publicationACC 2015 - 2015 American Control Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages7
ISBN (Electronic)9781479986842
StatePublished - Jul 28 2015
Externally publishedYes
Event2015 American Control Conference, ACC 2015 - Chicago, United States
Duration: Jul 1 2015Jul 3 2015

Publication series

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


Other2015 American Control Conference, ACC 2015
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Decentralized online optimization with global objectives and local communication'. Together they form a unique fingerprint.

Cite this