Adaptive online distributed optimization in dynamic environments. (3rd September 2021) - Nazari, Parvin; Khorram, Esmaeil; Tarzanagh, Davoud Ataee
ABSTRACT: This paper presents a dynamic regret analysis on the decentralized online convex optimization problems computed over a network of agents. The goal is to distributively optimize a global function which can be decomposed into the summation of local cost functions associated with each agent. By exploiting the convexity of cost functions, previous studies have shown that the dynamic regret of a decentralized gradient-based algorithm can be upper bounded by the path-length of the comparator sequence and the connectivity in the underlying network. In this paper, we illustrate that the dynamic regret can be further improved by allowing the learner to use a class of adaptive search directions and step-sizes from estimates of first and second moments of the gradients. Specifically, we develop a new class of decentralized and stochastic algorithms based on the adaptive gradient method in the dynamic environment and show that their regret bounds for certain realistic classes of loss functions are considerably better than existing bounds. Numerical simulations verify the theoretical results and demonstrate the efficiency of the new proposed method in practice.