Online Distributed Optimization via Dual Averaging

Abstract—This paper presents a regret analysis on a dis-tributed 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