Dynamic Regret for Distributed Online Composite Optimization

• 成果类型: Article
• 署名作者: Hou, Ruijie; Yu, Yang; Li, Xiuxian
• 署名单位: Tongji University; Tongji University; Tongji University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3489222
• 发表日期: 2025
• 页码: 3056-3071
• 关键词: Heuristic algorithms; optimization; Power system dynamics; Approximation algorithms; vectors; noise; linear programming; Convex functions; Benchmark testing; Loss measurement; Composite optimization; Distributed algorithms; dynamic regret; online optimization; proximal gradient; sign information

摘要

This article focuses on online composite optimization over multiagent networks. In the distributed setting, each agent has its own local loss function, which consists of a convex, strongly convex or strongly convex and smooth function, and a time-varying nonsmooth regularizer. Two distributed online algorithms are proposed and corresponding dynamic regrets are analyzed. Two proposed algorithms are based on signs of relative states. The first algorithm obtains O(root T(C-T + 1)) dynamic regret bound when each local loss is a general convex composite function, where C-T is the path variation. If C-T can be estimated in advance for convex or strongly convex local loss with a time-varying nonsmooth regularizer, then dynamic regret bounds are, respectively, in the order of O(root T(C-T + 1)) and O(logT(1 + C-T)). The second algorithm is based on the first one, especially for handling the local loss composed of a strongly convex and smooth function with a nonsmooth regularizer, and then obtains O(1 + C-T) dynamic regret bound. In the end, numerical results are given to support the theoretical findings.