计算机应用 ›› 2018, Vol. 38 ›› Issue (8): 2337-2342.DOI: 10.11772/j.issn.1001-9081.2018010189

• 网络与通信 • 上一篇    下一篇

快速在线分布式对偶平均优化算法

李德权, 王俊雅, 马驰, 周跃进   

  1. 安徽理工大学 数学与大数据学院, 安徽 淮南 232000
  • 收稿日期:2018-01-22 修回日期:2018-03-23 出版日期:2018-08-10 发布日期:2018-08-11
  • 通讯作者: 王俊雅
  • 作者简介:李德权(1973-),男,安徽肥东人,教授,博士,主要研究方向:分布式优化、统计机器学习;王俊雅(1994-),女,安徽阜阳人,硕士研究生,主要研究方向:分布式优化、统计机器学习;马驰(1977-),男,安徽淮南人,副教授,博士,主要研究方向:高维数据处理;周跃进(1977-),男,安徽桐城人,副教授,博士,主要研究方向:统计机器学习。
  • 基金资助:
    国家自然科学基金资助项目(61472003,11701007);安徽省高校学科(专业)拔尖人才学术资助重点项目(gxbjZD2016049);安徽省学术和技术带头人及后备人选科研活动项目(2016H076);安徽省自然科学基金资助项目(KJ2017A087)。

Fast online distributed dual average optimization algorithm

LI Dequan, WANG Junya, MA Chi, ZHOU Yuejin   

  1. School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan Anhui 232000, China
  • Received:2018-01-22 Revised:2018-03-23 Online:2018-08-10 Published:2018-08-11
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61472003,11701007), the Academic Discipline (Professional) Top Talent Academic Project of Anhui Province (gxbjZD2016049), the Anhui Academic and Technical Leader and Reserve Personnel Research Project (2016H076), the Natural Science Foundation of Anhui Province (KJ2017A087).

摘要: 为提高分布式在线优化算法的收敛速度,对底层网络拓扑依次添边,提出一种快速的一阶分布式在线对偶平均优化(FODD)算法。首先,对于分布式在线优化问题,运用添边方法使所选的边与网络模型快速混合,进而建立数学模型并设计FODD算法对其进行优化求解。其次,揭示了网络拓扑和在线分布式对偶平均收敛速度之间的关系,通过提高底层拓扑网络的代数连通度改进了Regret界,将在线分布式对偶平均(ODDA)算法从静态网络拓展到时变网络拓扑上,并证明了FODD算法的收敛性,同时解析地给出了收敛速度。最后的数值仿真表明:和ODDA算法相比,所提出的FODD算法具有更快的收敛速度。

关键词: 分布式网络, 在线分布式对偶平均, Regret界, 代数连通度, 拉普拉斯矩阵

Abstract: To improve the convergence speed of distributed online optimization algorithms, a fast first-order Online Distributed Dual Average optimization (FODD) algorithm was proposed by sequentially adding edges to the underlying network topology. Firstly, aiming at solving the problem of the online distributed optimization to make the selected edge and network model mix quickly by using the method of edge addition, a mathematical model was established and solved by FODD. Secondly, the relationship between network topology designed and the convergence rate of the online distributed dual average algorithm was revealed, which clearly showed that, by improving the algebraic connectivity of the underlying topology network, the Regret bound could also be greatly improved. The Online Distributed Dual Average (ODDA) algorithm was extended from static networks to time-varying networks. Meanwhile, the proposed FODD algorithm was proved to be convergent and the convergence rate was specified. Finally, the results of numerical simulations show that, compared with existing algorithms such as ODDA, the proposed FODD algorithm has better convergence performance.

Key words: distributed network, Online Distributed Dual Averaging (ODDA), Regret bound, algebraic connectivity, Laplacian matrix

中图分类号: