Logarithmic Regret for Distributed Online Subgradient Method over Unbalanced Directed Networks

Makoto YAMASHITA  Naoki HAYASHI  Takeshi HATANAKA  Shigemasa TAKAI  

Publication
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
Keyword: 
online optimization,  multi-agent system,  cooperative control,  unbalanced directed network,  

Full Text: PDF>>
Buy this Article




Summary: 
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.