Online distributed optimization algorithm with dynamic regret analysis under unbalanced graphs

We consider online distributed convex optimization problems with a sum of locally dynamic loss functions under unbalanced graphs. When optimizing the dynamic local loss function, every node tracks the time-varying global optimal solution by communicating with neighboring nodes via communication networks in a cooperative way. We propose a novel online distributed Push–Pull algorithm and present that the proposed online optimization algorithm can track the dynamic optimal solution with proper step sizes. We analyze the dynamic regret of the proposed algorithm in two cases where the global loss function is strongly convex and smooth, or is convex, smooth and Lipschitz. Our results illustrate that the dynamic regret of the proposed online optimization algorithm can be sublinear, if the path length and the gradient variance are sublinear. At last, we demonstrate the property of the online distributed optimization algorithm by two simulation examples.