Distributed Mirror Descent for Online Composite Optimization

• 成果类型: Article
• 署名作者: Yuan, Deming; Hong, Yiguang; Ho, Daniel W. C.; Xu, Shengyuan
• 署名单位: Nanjing University of Science & Technology; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; City University of Hong Kong
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.2987379
• 发表日期: 2021
• 页码: 714-729
• 关键词: Approximate mirror descent; average regularized regret; Bandit feedback; composite objective; online distributed optimization

摘要

In this article, we consider an online distributed composite optimization problem over a timevarying 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/root 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.