TY - GEN
T1 - Decentralized online optimization with global objectives and local communication
AU - Nedic, Angelia
AU - Lee, Soomin
AU - Raginsky, Maxim
N1 - Publisher Copyright:
© 2015 American Automatic Control Council.
PY - 2015/7/28
Y1 - 2015/7/28
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84940930889&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84940930889&partnerID=8YFLogxK
U2 - 10.1109/ACC.2015.7172037
DO - 10.1109/ACC.2015.7172037
M3 - Conference contribution
AN - SCOPUS:84940930889
T3 - Proceedings of the American Control Conference
SP - 4497
EP - 4503
BT - ACC 2015 - 2015 American Control Conference
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2015 American Control Conference, ACC 2015
Y2 - 1 July 2015 through 3 July 2015
ER -