Online distributed optimization via dual averaging

By Saghar Hosseini, Airlie Chapman, Mehran Mesbahi. 2013

150 citations recorded by the source corpus.

This paper presents a regret analysis on a distributed online optimization problem computed over a network of agents. The goal is to distributively optimize a global objective function which can be decomposed into the summation of convex cost functions associated with each agent. Since the agents face uncertainties in the environment, their cost functions change at each time step. We extend a distributed algorithm based on dual subgradient averaging to the online setting. The proposed algorithm yields an upper bound on regret as a function of the underlying network topology, specifically its connectivity. The regret of an algorithm is the difference between the cost of the sequence of decisions generated by the algorithm and the performance of the best fixed decision in hindsight. A model for distributed sensor estimation is proposed and the corresponding simulation results are presented.

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

1. Ji Liu
2. Shahin Shahrampour
3. Tamás Linder
4. Mohammad Akbari
5. Peilin Zhao
6. Wenwu Zhu
7. Ali Jadbabaie
8. Kunlun He

In Management Science and Operations Research

1. Ji Liu
2. T. Zhang
3. Peilin Zhao
4. Shahin Shahrampour
5. Tamás Linder
6. Mohammad Akbari
7. Wenwu Zhu
8. Ali Jadbabaie

Citations in the corpus

• Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “…2015], decentralized online gradient descent [Akbari et al., 2017], decentralized continuous-time online saddle-point method [Lee et al., 2016], decentralized online Nesterov’s primal-dual method [Nedi et al., 2015, Lee et al., 2018], and online distributed dual averaging[Hosseini et al., 2013].”
• Projection-free Distributed Online Learning in Networks (2017, methodology): “…online gradient descent (D-OGD) (Ram et al., 2010) (Yan et al., 2013) and distributed online dual averaging (D-ODA) (Duchi et al., 2012) (Hosseini et al., 2013) (Lee et al., 2015), which have been successfully applied in handling large-scale streaming data in decentralized…”
• Distributed Online Convex Optimization on Time-Varying Directed Graphs (2017, background): “Let us now review the setup for a distributed version of the online optimization problem [17], [19].”
• Asynchronous Decentralized Online Learning (2021, unknown): “We index the prediction rounds of learner i as τ = 1 , . . . , N i .”
• Distributed Online Optimization in Dynamic Environments Using Mirror Descent (2016, background): “The extension of dual averaging to online distributed optimization is considered in [16].”