Improved dynamic regret of distributed online multiple Frank-Wolfe convex optimization  

作　　者：Wentao ZHANG Yang SHI Baoyong ZHANG Deming YUAN 

机构地区：[1]School of Automation,Nanjing University of Science and Technology,Nanjing 210094,China [2]Department of Mechanical Engineering,University of Victoria,Victoria V8W 2Y2,Canada

出　　处：《Science China(Information Sciences)》2024年第11期160-175,共16页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.62273181,62373190,62221004);in part by Postgraduate Research and Practice Innovation Program of Jiangsu Province(Grant No.KYCX220453)。

摘　　要：In this paper,we explore a distributed online convex optimization problem over a time-varying multi-agent network.The network aims to minimize a global loss function through local computation and communication with neighboring agents.To effectively handle the optimization problem which involves highdimensional and structural constraint sets,we develop a distributed online multiple Frank-Wolfe algorithm that circumvents the expensive computational cost associated with projection operations.The dynamic regret bounds are established as O(T^(1-γ)+HT)with the linear oracle number O(T^(1+γ)),which depends on the horizon(total iteration number)T,the function variation H_(T),and the tuning parameter 0<γ<1.In particular,when the prior knowledge of H_(T)and T is available,the bound can be enhanced to O(1+H_(T)).Moreover,we explore the significant advantages provided by the multiple iteration technique and reveal a trade-off between dynamic regret bound,computational cost,and communication cost.Finally,the performance of our algorithm is validated and compared through the distributed online ridge regression problems with two constraint sets.

关 键 词：distributed online convex optimization multiple iterations Frank-Wolfe algorithm dynamic regret gradient tracking method 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]