分布式在线条件梯度优化算法

doi:10.11896/j.issn.1002-137X.2019.03.049

计算机科学 ›› 2019, Vol. 46 ›› Issue (3): 332-337.doi: 10.11896/j.issn.1002-137X.2019.03.049

• 交叉与前沿 • 上一篇

分布式在线条件梯度优化算法

李德权,董翘,周跃进

(安徽理工大学数学与大数据学院安徽淮南 232001)

收稿日期:2018-01-17 修回日期:2018-03-07 出版日期:2019-03-15 发布日期:2019-03-22
作者简介:李德权(1973-),男,博士,教授,硕士生导师,主要研究方向为分布式优化理论、统计机器学习;董翘(1993-),女,硕士生,主要研究方向为分布式优化理论与应用,E-mail:1047869260@qq.com;周跃进(1977-),男,博士,副教授,主要研究方向为高维数据处理和统计机器学习。
基金资助:
国家自然科学基金资助项目(61472003),高校学科(专业)拔尖人才学术资助重点项目(gxbjZD2016049),安徽省学术和技术带头人及后备人选资助项目(2016H076),安徽省教育厅自然科学基金重点项目(KJ2017A087)资助

Distributed Online Conditional Gradient Optimization Algorithm

LI De-quan, DONG Qiao, ZHOU Yue-jin

(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan,Anhui 232001,China)

Received:2018-01-17 Revised:2018-03-07 Online:2019-03-15 Published:2019-03-22

摘要/Abstract

摘要： 针对现有分布式在线优化算法所面临的高维约束难以计算的问题,提出一种分布式在线条件梯度优化算法(Distributed Online Conditional Gradient Optimization Algorithm,DOCG)。首先,通过多个体网络节点间的相互协作进行数据采集,并通过共享采集的信息更新局部估计,同时引入反映环境变化的局部即时损失函数。然后,该算法利用历史梯度信息进行加权平均,提出一种新的梯度估计方案,其用线性优化步骤替代投影步骤,避免了投影运算在高维约束时难以计算的问题。最后,通过分析表征在线估计性能的Regret界,证明了所提DOCG算法的收敛性。利用低秩矩阵填充问题进行仿真验证,结果表明,相比于现有分布式在线梯度下降法(DOGD),所提DOCG算法具有更快的收敛速度。

关键词: Regret界, 分布式网络, 条件梯度, 无投影, 在线学习

Abstract: In order to overcome the problem that the high-dimensional constraints in existing distributed online optimization algorithms are hard to be calculated,a distributed online conditional gradient optimization algorithm (DOCG) was proposed in this paper.Firstly,data collection is carried out through mutual cooperation among nodes of the muti-agent distributed network,and then each node updates its local iterate based on new local data,together with an instantaneous local cost functions that reflects the environmental changes.Secondly,by virtue of the historical gradient information for weighted averaging,a new gradient estimation scheme is proposed,in which the sophisticated projection step is replaced by the linear optimization step and thus avoids the disadvantages of the projection operator that is hard to be calculated.Finally,by defining the corresponding Regret bound to characterize the performance of online estimation,the convergence of the DOCG algorithm is proved.Simulation results are conducted on low-rank matrix completion problems,which clearly show that the proposed algorithm has faster convergence rate than the existing distributed online gradient method(DOGD).

Key words: Conditional gradient, Distributed network, Online learning, Projection-free, Regret bound

中图分类号:

TP301.6

李德权,董翘,周跃进. 分布式在线条件梯度优化算法[J]. 计算机科学, 2019, 46(3): 332-337. https://doi.org/10.11896/j.issn.1002-137X.2019.03.049

LI De-quan, DONG Qiao, ZHOU Yue-jin. Distributed Online Conditional Gradient Optimization Algorithm[J]. Computer Science, 2019, 46(3): 332-337. https://doi.org/10.11896/j.issn.1002-137X.2019.03.049

参考文献

相关文章 15

[1]	刘凌云, 钱辉, 邢红杰, 董春茹, 张峰. 一种基于Q-学习算法的增量分类模型 Incremental Classification Model Based on Q-learning Algorithm 计算机科学, 2020, 47(8): 171-177. https://doi.org/10.11896/jsjkx.190600150
[2]	孔芳, 李奇之, 李帅. 在线影响力最大化研究综述 Survey on Online Influence Maximization 计算机科学, 2020, 47(5): 7-13. https://doi.org/10.11896/jsjkx.200200071
[3]	杨立鹏, 张仰森, 张雯, 王建, 曾健荣. 基于Storm实时流式计算框架的网络日志分析方法 Web Log Analysis Method Based on Storm Real-time Streaming Computing Framework 计算机科学, 2019, 46(9): 176-183. https://doi.org/10.11896/j.issn.1002-137X.2019.09.025
[4]	何孝文, 胡一飞, 王海平, 陈默. 在线学习非负矩阵分解 Online Learning Nonnegative Matrix Factorization 计算机科学, 2019, 46(6A): 473-477.
[5]	杨海民, 潘志松, 白玮. 时间序列预测方法综述 Review of Time Series Prediction Methods 计算机科学, 2019, 46(1): 21-28. https://doi.org/10.11896／j.issn.1002-137X.2019.01.004
[6]	秦一休, 文益民, 何倩. 概念漂移数据流分类中的多源在线迁移学习算法 Multi-source Online Transfer Learning Algorithm for Classification of Data Streams with Concept Drift 计算机科学, 2019, 46(1): 64-72. https://doi.org/10.11896／j.issn.1002-137X.2019.01.010
[7]	陈晋音, 方航, 林翔, 郑海斌, 杨东勇, 周晓. 基于在线学习行为分析的个性化学习推荐 Personal Learning Recommendation Based on Online Learning Behavior Analysis 计算机科学, 2018, 45(11A): 422-426.
[8]	赵强利,蒋艳凰. 类别严重不均衡应用的在线数据流学习算法 Online Data Stream Mining for Seriously Unbalanced Applications 计算机科学, 2017, 44(6): 255-259. https://doi.org/10.11896/j.issn.1002-137X.2017.06.044
[9]	王长宝,李青雯,于化龙. 面向类别不平衡数据的主动在线加权极限学习机算法 Active,Online and Weighted Extreme Learning Machine Algorithm for Class Imbalance Data 计算机科学, 2017, 44(12): 221-226. https://doi.org/10.11896/j.issn.1002-137X.2017.12.040
[10]	薛伟,张文生,任俊宏. 基于随机谱梯度的在线学习 Online Learning Based on Stochastic Spectral Gradient 计算机科学, 2016, 43(9): 47-51. https://doi.org/10.11896/j.issn.1002-137X.2016.09.008
[11]	王万良,陈宇,邱虹,郑建炜. 一种基于QR分解的增量式核判别分析法 Incremental Kernel Discriminant Analysis Method via QR Decomposition 计算机科学, 2014, 41(4): 297-301.
[12]	杜翠兰,谭建龙,王晓岩,张宇,刘萍,樊冬进. 基于事件处理的分布式系统故障定位技术 Fault Location Technology Based on the Distributed Event Processing System 计算机科学, 2013, 40(Z6): 302-306.
[13]	闫庆森,李临生,徐晓峰,王灿. 视频跟踪算法研究综述 Survey of Visual Tracking Algorithm 计算机科学, 2013, 40(Z6): 204-209.
[14]	王万良，陈星昊，郑建炜，黄琼芳. 一种增量式类内局部保持降维算法 Incremental Within-class Locality Preserving Dimension Reduction Algorithm 计算机科学, 2012, 39(Z11): 154-158.
[15]	汪晓妍,王阳生,周明才,冯雪涛,周晓旭. 综合鲁棒特征和在线学习的自适应三维人脸多特征跟踪 Adaptive 3D Facial Feature Tracking Combining Robust Feature with Online Learning 计算机科学, 2009, 36(11): 247-250.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

分布式在线条件梯度优化算法

Distributed Online Conditional Gradient Optimization Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0