Computer Science ›› 2019, Vol. 46 ›› Issue (3): 332-337.doi: 10.11896/j.issn.1002-137X.2019.03.049

• Interdiscipline & Frontier • Previous Articles    

Distributed Online Conditional Gradient Optimization Algorithm

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

  1. (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: 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, Projection-free, Distributed network, Online learning, Regret bound

CLC Number: 

  • TP301.6
[1] LIU Ling-yun, QIAN Hui, XING Hong-jie, DONG Chun-ru, ZHANG Feng. Incremental Classification Model Based on Q-learning Algorithm [J]. Computer Science, 2020, 47(8): 171-177.
[2] KONG Fang, LI Qi-zhi, LI Shuai. Survey on Online Influence Maximization [J]. Computer Science, 2020, 47(5): 7-13.
[3] YANG Li-peng, ZHANG Yang-sen, ZHANG Wen, WANG Jian, ZENG Jian-rong. Web Log Analysis Method Based on Storm Real-time Streaming Computing Framework [J]. Computer Science, 2019, 46(9): 176-183.
[4] HE Xiao-wen, HU Yi-fei, WANG Hai-ping, CHEN Mo. Online Learning Nonnegative Matrix Factorization [J]. Computer Science, 2019, 46(6A): 473-477.
[5] WAN Jia-shan, CHEN Lei, WU Jin-hua, GAO Chao. Persona Based Social User Modeling Using KD-Tree [J]. Computer Science, 2019, 46(6A): 442-445.
[6] YANG Hai-min, PAN Zhi-song, BAI Wei. Review of Time Series Prediction Methods [J]. Computer Science, 2019, 46(1): 21-28.
[7] QIN Yi-xiu, WEN Yi-min, HE Qian. Multi-source Online Transfer Learning Algorithm for Classification of Data Streams with Concept Drift [J]. Computer Science, 2019, 46(1): 64-72.
[8] CHEN Jin-yin, FANG Hang, LIN Xiang, ZHENG Hai-bin, YANG Dong-yong, ZHOU Xiao. Personal Learning Recommendation Based on Online Learning Behavior Analysis [J]. Computer Science, 2018, 45(11A): 422-426.
[9] ZHAO Qiang-li and JIANG Yan-huang. Online Data Stream Mining for Seriously Unbalanced Applications [J]. Computer Science, 2017, 44(6): 255-259.
[10] WANG Chang-bao, LI Qing-wen and YU Hua-long. Active,Online and Weighted Extreme Learning Machine Algorithm for Class Imbalance Data [J]. Computer Science, 2017, 44(12): 221-226.
[11] XUE Wei, ZHANG Wen-sheng and REN Jun-hong. Online Learning Based on Stochastic Spectral Gradient [J]. Computer Science, 2016, 43(9): 47-51.
[12] WANG Wan-liang,CHEN Yu,QIU Hong and ZHENG Jian-wei. Incremental Kernel Discriminant Analysis Method via QR Decomposition [J]. Computer Science, 2014, 41(4): 297-301.
[13] DU Cui-lan,TAN Jian-long,WANG Xiao-yan,ZHANG Yu,LIU Ping and FAN Dong-jin. Fault Location Technology Based on the Distributed Event Processing System [J]. Computer Science, 2013, 40(Z6): 302-306.
[14] YAN Qing-sen,LI Lin-sheng,XU Xiao-feng and WANG Can. Survey of Visual Tracking Algorithm [J]. Computer Science, 2013, 40(Z6): 204-209.
[15] ZHANG Jun ,WANG Jian-Hua, JI Wei Dong (Computer & Science, Harbin Normal Univ, Harbin 150025). [J]. Computer Science, 2006, 33(9): 115-117.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .