Adaptive online distributed optimization in dynamic environments. (3rd September 2021)

• Record Type: Journal Article
• Authors: Nazari, Parvin; Khorram, Esmaeil; Tarzanagh, Davoud Ataee
• Is Part Of: Optimization methods and software. Volume 36:Number 5(2021)
• Page Start: 973
• Page End: 997
• Publication Date: 2021-09-03
• Subjects: Adaptive online learning -- decentralized optimization -- convex optimization -- dynamic regret; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1637433
• Languages: English
• ISSNs: 1055-6788

Abstract

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.