Logarithmic Regret for Distributed Online Subgradient Method over Unbalanced Directed Networks

Makoto YAMASHITA  Naoki HAYASHI  Takeshi HATANAKA  Shigemasa TAKAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A   No.8   pp.1019-1026
Publication Date: 2021/08/01
Publicized: 2021/02/04
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020EAP1111
Type of Manuscript: PAPER
Category: Systems and Control
online optimization,  multi-agent system,  cooperative control,  unbalanced directed network,  

Full Text: PDF>>
Buy this Article

This paper investigates a constrained distributed online optimization problem over strongly connected communication networks, where a local cost function of each agent varies in time due to environmental factors. We propose a distributed online projected subgradient method over unbalanced directed networks. The performance of the proposed method is evaluated by a regret which is defined by the error between the cumulative cost over time and the cost of the optimal strategy in hindsight. We show that a logarithmic regret bound can be achieved for strongly convex cost functions. We also demonstrate the validity of the proposed method through a numerical example on distributed estimation over a diffusion field.