Coordinate Dual Averaging for Decentralized Online Optimization With Nonseparable Global Objectives

By Soomin Lee, Angelia Nedić, Maxim Raginsky. 2015

39 citations recorded by the source corpus.

We consider a decentralized online convex optimization problem in a network of agents, where each agent controls only a coordinate (or a part) of the global decision vector. For such a problem, we propose two decentralized variants (ODA-C and ODA-PS) of Nesterov's primal-dual algorithm with dual averaging. In ODA-C, 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] over a static undirected graph. In ODA-PS, the agents implement the broadcast-based push-sum dynamics [2] over a time-varying sequence of uniformly connected digraphs. We show that the regret bounds in both cases have sublinear growth of <inline-formula><tex-math notation="LaTeX">$O(\sqrt{T})$</tex-math></inline-formula>, with the time horizon <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula>, when the stepsize is of the form <inline-formula><tex-math notation="LaTeX">$1/\sqrt{t}$</tex-math></inline-formula> and the objective functions are Lipschitz-continuous convex functions with Lipschitz gradients. We also implement the proposed algorithms on a sensor network to complement our theoretical analysis.

Subfields: Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “pectively [31, 32]. In recent years, due to the increasing volume of data, distributed online learning, especially decentralized methods, has attracted much attention. Examples of these works include [33, 34, 35]. Notably, [36] shares a similar problem deﬁnition and theoretical result as our paper. ”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, neutral): “Additionally, many decentralized online optimization methods are proposed, for example, decentralized online multi-task learning [41], decentralized online ADMM [35], decentralized online gradient descent [2], decentralized continuous-time online saddle-point method [23], decentralized online Nester”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, background): “…Nedić & Ozdaglar, 2009; Ram et al., 2010; Bianchi & Jakubowicz, 2013), ADMM (Wei & Ozdaglar, 2012; 2013; Iutzeler et al., 2013) or dual averaging (Duchi et al., 2012; Yuan et al., 2012; Lee et al., 2015; Tsianos et al., 2015), some of which can also accommodate constraints or regularization on θ.”