2.624

2020影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

吴庆涛 朱军龙 葛泉波 张明川

吴庆涛, 朱军龙, 葛泉波, 张明川. 一种基于条件梯度的加速分布式在线学习算法. 自动化学报, 2022, 45(x): 1−16 doi: 10.16383/j.aas.c210830
引用本文: 吴庆涛, 朱军龙, 葛泉波, 张明川. 一种基于条件梯度的加速分布式在线学习算法. 自动化学报, 2022, 45(x): 1−16 doi: 10.16383/j.aas.c210830
Wu Qing-Tao, Zhu Jun-Long, Ge Quan-Bo, Zhang Ming-Chuan. An accelerated distributed online learning algorithm based on conditional gradient. Acta Automatica Sinica, 2022, 45(x): 1−16 doi: 10.16383/j.aas.c210830
Citation: Wu Qing-Tao, Zhu Jun-Long, Ge Quan-Bo, Zhang Ming-Chuan. An accelerated distributed online learning algorithm based on conditional gradient. Acta Automatica Sinica, 2022, 45(x): 1−16 doi: 10.16383/j.aas.c210830

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

doi: 10.16383/j.aas.c210830
基金项目: 国家自然科学基金(62033010, 61871430, 61976243), 中原科技创新领军人才(214200510012, 224200510004)资助
详细信息
    作者简介:

    吴庆涛:河南科技大学信息工程学院教授.主要研究方向为工业互联网, 智能系统, 模式识别和机器学习. E-mail: wqt8921@haust.edu.cn

    朱军龙:河南科技大学信息工程学院副教授.主要研究方向为大规模优化, 分布式多智能体优化, 随机优化及其在机器学习中的应用. E-mail: jlzhu@haust.edu.cn

    葛泉波:南京信息工程大学自动化学院教授.主要研究方向为信息融合, 非线性滤波, 无人系统和机器学习. 本文通信作者. E-mail: quanboge@163.com

    张明川:河南科技大学信息工程学院教授.主要研究方向为新型网络, 智能信息处理, 医疗辅助诊断和机器学习. E-mail: zhang_mch@haust.edu.cn

An Accelerated Distributed Online Learning Algorithm Based on Conditional Gradient

Funds: Supported by National Natural Science Foundation of China (62033010, 61871430, 61976243), Leading Talents of Science and Technology in the Central Plain of China(214200510012, 224200510004)
More Information
    Author Bio:

    WU Qing-Tao Professor at the School of Information Engineering, Henan University of Science and Technology. His research interest covers industrial Internet, intelligent system, pattern recognition, and machine learning

    ZHU Jun-Long Associate Professor at the School of Information Engineering, Henan University of Science and Technology. His research interest covers large-scale optimization, distributed multi-agent optimization, stochastic optimization, and their applications to machine learning

    GE Quan-Bo Professor at the School of Automation, Nanjing University of Information Science and Technology. His research interest covers information fusion, nonlinear filtering, unmanned system, and machine learning. Corresponding author of this paper

    ZHANG Ming-Chuan Professor at the School of Information Engineering, Henan University of Science and Technology. His research interest covers new generation network, intelligent information processing, medical aided diagnosis, and machine learning

  • 摘要: 由于容易实施, 基于投影梯度的分布式在线优化模型逐渐成为一种主流的在线学习方法. 然而, 在处理大数据应用时, 投影步骤成为了该方法的计算瓶颈. 近年来, 研究者提出了面向凸代价函数的分布式在线条件梯度算法, 其悔界为${\rm O}(T^{3/4})$, 其中$T$是一个时间范围. 该算法存在两方面的问题, 一是其悔界劣于公认的悔界${\rm O}(\sqrt{T})$; 二是没有分析非凸代价函数的收敛性能, 而实际应用中代价函数大部分是非凸函数. 因此, 本文提出了一种基于条件梯度的加速分布式在线学习算法, 使用Frank-Wolfe 步骤替代投影步骤, 避免了昂贵的投影计算. 文中证明了当局部代价函数为凸函数时, 所提算法达到公认的悔界${\rm O}(\sqrt{T})$; 当局部代价函数为潜在非凸函数时, 所提算法以速率${\rm O}(\sqrt{T})$收敛到平稳点. 最后, 仿真实验验证了所提算法的性能与理论证明的结论.
  • 图  1  在news20和aloi数据集上不同节点数下算法的性能

    Fig.  1  Performance of the algorithm at different nodes on news20 and aloi datasets

    图  2  在新的20个数据集和64个节点的aloi数据集上比较该算法和D-OCG算法

    Fig.  2  The algorithm is compared with D-OCG algorithm on the new aloi dataset with 20 datasets and 64 nodes

    图  3  算法在具有固定64个节点和不同拓扑结构的news20和aloi数据集上的性能

    Fig.  3  Performance of the algorithm on news20 and aloi datasets with fixed 64 nodes and different topologies

    表  1  不同算法的比较

    Table  1  Comparison of different algorithms

    算法 凸代价函数 非凸代价函数
    D-OCG[33] ${\rm O}(T^{3/4})$
    D-BOCG[34] ${\rm O}(T^{3/4})$
    本文算法 ${\rm O}(\sqrt{T})$ ${\rm O}(\sqrt{T})$
    下载: 导出CSV
  • [1] Zhu J L, Wu Q T, Zhang M C, Zheng R J, Li K Q. Projection-free decentralized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 2021, 22(51): 1-42
    [2] Rabbat M, Nowak R. Distributed optimization in sensor networks. In: Proceedings of Third International Symposium on Information Processing in Sensor NetworksProc. Berkeley, USA: IEEE, 2004. 20-27
    [3] Zhang M C, Hao B W, Ge Q B, Zhu J L, Zheng R J, Wu Q T. Distributed adaptive subgradient algorithms for online learning over time-varying networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021. 1-12
    [4] Abu-Elkheir M, Hayajneh M, Abu A N. Data management for the internet of things: design primitives and solution. Sensors, 2013, 13(11): 15582-15612 doi: 10.3390/s131115582
    [5] 孙路明, 张少敏, 姬涛, 李翠平, 陈红. 人工智能赋能的数据管理技术研究. 软件学报, 2020, 31(3): 600-619

    SUN Lu-Ming, ZHANG Shao-Min, JI Tao, LI Cui-Ping, CHEN Hong. Survey of data management techniques powered by artificial intelligence. Journal of Software, 2020, 31(3): 600-619
    [6] 黄刚, 李军华. 基于 AC-DSDE 进化算法多 UAVs协同目标分配. 自动化学报, 2021, 47(1): 173-184

    Huang Gang, Li Jun-Hua. Multi-UAV cooperative target allocation based on AC-DSDE evolutionary algorithm. Acta Automatica Sinica, 2021, 47(1): 173-184
    [7] Beck A, Nedić A, Ozdaglar A, Teboulle M. An ${\rm{ O}}(1/k)$ gradient method for network resource allocation problems. IEEE Transactions on Control of Network Systems, 2014, 1(1): 64-73 doi: 10.1109/TCNS.2014.2309751
    [8] 刘妹琴, 韩学艳, 张森林, 郑荣濠, 兰剑. 基于水下传感器网络的目标跟踪技术研究现状与展望. 自动化学报, 2021, 47(2): 235-251

    Liu Mei-Qin, Han Xue-Yan, Zhang Sen-Lin, Zheng Rong-Hao, Lan Jian. Research status and prospect of target tracking technologies via underwater sensor networks. Acta Automatica Sinica, 2021, 47(2): 235-251
    [9] 蒋弘毅, 王永娟, 康锦煜. 目标检测模型及其优化方法综述. 自动化学报, 2021, 47(6): 1232-1255

    Jiang Hong-Yi, Wang Yong-Juan, Kang Jin-Yu. A survey of object detection models and its optimization methods. Acta Automatica Sinica, 2021, 47(6): 1232-1255
    [10] Wen G H, Yu X H, Liu Z W, Yu W W. Adaptive consensus-based robust strategy for economic dispatch of smart grids subject to communication uncertainties. IEEE Transactions on Industrial Informatics, 2018, 14(6): 2484-2496 doi: 10.1109/TII.2017.2772088
    [11] 李小玲, 王怀民, 郭长国, 丁博, 李小勇. 分布式约束优化问题研究及其进展. 计算机学报, 2015, 38(8): 1656-1671 doi: 10.11897/SP.J.1016.2015.01656

    LI Xiao-Ling, WANG Huai-Min, GUO Chang-Guo, DING Bo, LI Xiao-Yong. Research and development of distributed constraint optimization problems. Chinese Journal of Computers, 2015, 38(8): 1656-1671 doi: 10.11897/SP.J.1016.2015.01656
    [12] Nedić A, Olshevsky A. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 2015, 60(3): 601-615 doi: 10.1109/TAC.2014.2364096
    [13] Qu G N, Li N. Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems, 2018, 5(3): 1245-1260 doi: 10.1109/TCNS.2017.2698261
    [14] Shalev-Shwartz S. Online learning and online convex optimization. Foundations and Trends R in Machine Learning, 2011, 4(2): 107-194 doi: 10.1561/2200000018
    [15] Hazan E, Kalai A, Kale S, Agarwal A. Logarithmic regret algorithms for online convex optimization. In: Proceedings of International Conference on Computational Learning Theory. Berlin, Germany: Springer, 2006. 499-513
    [16] Mateos-Núñez D, Cortés J. Distributed online convex optimization over jointly connected digraphs. IEEE Transactions on Network Science and Engineering, 2014, 1(1): 23-37 doi: 10.1109/TNSE.2014.2363554
    [17] Xu C Q, Zhu J L, Wu D O. Decentralized online learning methods based on weight-balancing over time-varying digraphs. IEEE Transactions on Emerging Topics in Computational Intelligence, 2021, 5(3): 394-406 doi: 10.1109/TETCI.2018.2880771
    [18] Akbari M, Gharesifard B, Linder T. Distributed online convex optimization on time-varying directed graphs. IEEE Transactions on Control of Network Systems, 2017, 4(3): 417-428 doi: 10.1109/TCNS.2015.2505149
    [19] Liu S, Xie L H, Quevedo D E. Event-Triggered quantized communication-based distributed convex optimization. IEEE Transactions on Control of Network Systems, 2018, 5(1): 167-178 doi: 10.1109/TCNS.2016.2585305
    [20] Zhu J L, Wu Q T, Zhang M C, Zheng R J, Li K Q. Projection-free decentalized online learning for submodular maximization over time-varying networks. Journal of Machine Learning Research, 2021, 22: 1-42
    [21] Raginsky M, Kiarashi N, Willett R. Decentralized online convex programming with local information. In: Proceedings of the 2011 American Control Conference. San Francisco, USA: IEEE, 2011. 5363-5369
    [22] Hosseini S, Chapman A, Mesbahi M. Online distributed convex optimization on dynamic networks. IEEE Transactions on Automatic Control, 2016, 61(11): 3545-3550 doi: 10.1109/TAC.2016.2525928
    [23] Yan F, Sundaram S, Vishwanathan S V N, Qi Y. Distributed autonomous online learning: regrets and intrinsic privacy-preserving properties. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(11): 2483-2493 doi: 10.1109/TKDE.2012.191
    [24] Liang Q K, Modiano E. Network utility maximization in adversarial environments. In: Proceedings of IEEE Conference on Computer Communications. Honolulu, USA: IEEE, 2018. 594-602
    [25] Frank M, Wolfe P. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 1956, 3(1-2): 95-110 doi: 10.1002/nav.3800030109
    [26] Jaggi M. Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: Proceedings of 30th International Conference Machine Learning. Atlanta, USA: JMLR, 2013. 427-435
    [27] Clarkson K L. Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. ACM Transactions on Algorithms, 2010, 6(4): 1-34
    [28] Hazan E, Kale S. Projection-free online learning. In: Proceedings of 29th International Conference Machine Learning. Edinburgh, UK: JMLR, 2012. 521-528
    [29] Garber D, Hazan E. A linearly convergent variant of the conditional gradient algorithm under strong convexity, with applications to online and stochastic optimization. SIAM Journal on Optimization, 2016, 26(3): 1493-1528 doi: 10.1137/140985366
    [30] Lafond J, Wai H T, Moulines E. On the online Frank-Wolfe algorithms for convex and non-convex optimizations. arXiv preprint arXiv: 1510.01171, 2016.
    [31] Hazan E, Luo H P. Variance-reduced and projection-free stochastic optimization. In: Proceedings of 33rd International Conference on International Conference on Machine Learning. New York, USA: JMLR, 2016. 1263-1271
    [32] Wai H T, Lafond J, Scaglione A, Moulines E. Decentralized Frank-Wolfe algorithm for convex and non-convex problems. IEEE Transactions on Automatic Control, 2017, 62(11): 5522-5537 doi: 10.1109/TAC.2017.2685559
    [33] Zhang W P, Zhao P L, Zhu W W, Hoi S, Zhang T. Projection-free distributed online learning in networks. In: Proceedings of 34th Intentional Conference of Machine Learning. Sydney, Australia: PMLR, 2017. 4054-4062
    [34] Wan Y Y, Tu W W, Zhang L J. Projection-free distributed online convex optimization with ${\rm{ O}}(\sqrt{T})$ communication complexity. In: Proceedings of 37th International Conference on Machine Learning. Online: PMLR, 2020. 9818-9828
    [35] Boyd S, Vandenberghe L. Convex Optimization. UK: Cambridge University, 2004.
    [36] Liu S, Qiu Z R, Xie L H. Convergence rate analysis of distributed optimization with projected subgradient algorithm. Automatica, 2017, 83: 162-169 doi: 10.1016/j.automatica.2017.06.011
    [37] Watts D J, Strogatz S H. Collective dynamics of 'small-world' networks. Nature, 1998, 393: 440-442 doi: 10.1038/30918
  • 加载中
计量
  • 文章访问数:  105
  • HTML全文浏览量:  28
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-09-01
  • 录用日期:  2022-03-01
  • 网络出版日期:  2022-05-07

目录

    /

    返回文章
    返回