一种基于条件梯度的加速分布式在线学习算法  

An Accelerated Distributed Online Learning Algorithm Based on Conditional Gradient

作　　者：吴庆涛 朱军龙 葛泉波 张明川 WU Qing-Tao;ZHU Jun-Long;GE Quan-Bo;ZHANG Ming-Chuan(School of Information Engineering,Henan University of Science and Technology,Luoyang 471023;School of Automation,Nanjing University of Information Science and Technology,Nanjing 210044)

机构地区：[1]河南科技大学信息工程学院,洛阳471023 [2]南京信息工程大学自动化学院,南京210044

出　　处：《自动化学报》2024年第2期386-402,共17页Acta Automatica Sinica

基　　金：国家自然科学基金(62033010,61871430,61976243);中原科技创新领军人才(214200510012,224200510004)资助。

摘　　要：由于容易实施,基于投影梯度的分布式在线优化模型逐渐成为一种主流的在线学习方法.然而,在处理大数据应用时,投影步骤成为该方法的计算瓶颈.近年来,研究者提出了面向凸代价函数的分布式在线条件梯度算法,其悔界为O(T^(3/4)),其中T是一个时间范围.该算法存在两方面的问题,一是其悔界劣于公认的悔界O(/T);二是没有分析非凸代价函数的收敛性能,而实际应用中代价函数大部分是非凸函数.因此,提出一种基于条件梯度的加速分布式在线学习算法,使用Frank-Wolfe步骤替代投影步骤,避免昂贵的投影计算.文中证明当局部代价函数为凸函数时,所提算法达到公认的悔界O(/T);当局部代价函数为潜在非凸函数时,所提算法以速率O(/T)收敛到平稳点.最后,仿真实验验证了所提算法的性能与理论证明的结论.The distributed online optimization model based on projected gradient has become a prominent paradigm for online learning due to its simplicity.However,this paradigm is incapable of handling massive data ap-plications because the projection step becomes the computational bottleneck.Recent studies have presented the dis-tributed online conditional gradient algorithms for convex cost functions,which achieved an O(T^(3/4))regret bound,where T is a time horizon.There are two negative problems for those algorithms.The first one is that the regret O(√T)bound of those algorithms is worse than the well known regret bound.The second one is that the conver-gence performance of the presented algorithms has not been analyzed for non-convex cost functions,which are common in practice.In this paper,we propose an accelerated distributed online learning algorithm based on the conditional gradient method over networks,which avoids the prohibitively expensive projection steps by using Frank-Wolfe O(√T)step.Moreover,when the local cost functions are convex,we show that the regret bound of is achieved.When the local cost functions are potentially non-convex,we also show that the algorithm converges to some sta-O(√T)tionary points at rate of.Finally,the performance of the proposed algorithm and the theoretical results are verified by simulation experiments.

关 键 词：条件梯度 分布式在线学习 悔界 收敛速率 

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