Distributed Online Optimization over Partially Free-In and Free-Out Networks

This paper studies a distributed online optimization problem over partially Free-In and Free-Out (FIFO) networks, in which a set of unfixed agents cooperate to minimize the sum of a group of time-varying functions over a time horizon. To be specific, the agents are divided into static agents and dynamic agents. The static agents are those who remain in the network during the whole time horizon, while the dynamic agents are allowed to join and leave the network freely. Based on the dual averaging technique, two novel distributed algorithms are developed to address the distributed optimization problem in such a dynamic environment. In the case where agents can distinguish whether their out-neighbors are dynamic agents or static agents, a weighting matrix based algorithm is developed. In the case where the identities of out-neighbors are unavailable, a gradient-storage based algorithm is developed, which has higher communication and local storage requirements than the weighting matrix based algorithm. By assuming that each dynamic agent has at least one in-neighbor and one out-neighbor who are static agents, the running average regret is shown to be upper bounded by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\frac{1}{\sqrt{\mathit {T}}})$</tex-math></inline-formula> under suitable step-sizes, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathit {T}$</tex-math></inline-formula> is the time horizon. A simulation study on binary classification is given to verify the effectiveness of the developed algorithms. In addition, a numerical example is used to highlight the advantages of the proposed methods over the distributed sub-gradient decent method.