Distributed Mirror Descent for Online Composite Optimization

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number9070199
Pages (from-to)714-729
Journal / PublicationIEEE Transactions on Automatic Control
Volume66
Issue number2
Online published17 Apr 2020
Publication statusPublished - Feb 2021

Abstract

In this article, we consider an online distributed composite optimization problem over a time-varying multiagent network that consists of multiple interacting nodes, where the objective function of each node consists of two parts: a loss function that changes over time and a regularization function. This problem naturally arises in many real-world applications ranging from wireless sensor networks to signal processing. We propose a class of online distributed optimization algorithms that are based on approximate mirror descent, which utilizes the Bregman divergence as a distance-measuring function that includes the Euclidean distances as a special case. We consider two standard information feedback models when designing the algorithms, that is, full-information feedback and bandit feedback. For the full-information feedback model, the first algorithm attains an average regularized regret of order O(1/√T) with the total number of rounds T. The second algorithm, which only requires the information of the values of the loss function at two predicted points instead of the gradient information, achieves the same average regularized regret as that of the first algorithm. Simulation results of a distributed online regularized linear regression problem are provided to illustrate the performance of the proposed algorithms.

Research Area(s)

  • Approximate mirror descent, average regularized regret, bandit feedback, composite objective, online distributed optimization

Citation Format(s)

Distributed Mirror Descent for Online Composite Optimization. / Yuan, Deming; Hong, Yiguang; Ho, Daniel W. C.; Xu, Shengyuan.

In: IEEE Transactions on Automatic Control, Vol. 66, No. 2, 9070199, 02.2021, p. 714-729.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review