分布式在线交替方向乘子法

doi:10.11772/j.issn.1001-9081.2015.06.1595

计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1595-1599.DOI: 10.11772/j.issn.1001-9081.2015.06.1595

分布式在线交替方向乘子法

许浩锋, 凌青

中国科学技术大学自动化系, 合肥 230026

收稿日期:2015-01-13 修回日期:2015-03-28 发布日期:2015-06-12
通讯作者: 凌青(1981-),男,安徽安庆人,副教授,博士,主要研究方向:分布式网络系统、分布式优化算法。qingling@mail.ustc.edu.cn
作者简介:许浩锋(1989-),男,浙江绍兴人,硕士研究生,主要研究方向:分布式在线优化.
基金资助:
国家自然科学基金资助项目(61004137)。

Decentralized online alternating direction method of multipliers

XU Haofeng, LING Qing

Department of Automation, University of Science and Technology of China, Hefei Anhui 230026, China

Received:2015-01-13 Revised:2015-03-28 Published:2015-06-12

摘要/Abstract

摘要：

针对如何对分布式网络采集的数据进行在线学习的问题,提出了一种基于交替方向乘子法(ADMM)的分布式在线学习优化算法——分布式在线交替方向乘子法(DOM)。首先,针对分布式在线学习需要各节点根据新采集的数据来更新本地估计,同时保持网络中所有节点的估计趋于一致这一问题,建立了数学模型并设计DOM算法对其进行求解。其次,针对分布式在线学习问题定义了Regret 界,用以表征在线估计的性能;证明了当本地即时损失函数是凸函数时,DOM算法是收敛的,并给出了其收敛速度。最后,通过数值仿真实验结果表明,相比现有的分布式在线梯度下降法(DOGD)和分布式在线自主学习算法(DAOL),所提出的DOM算法具有更快的收敛性能。

关键词: 交替方向乘子法, 在线学习, 分布式网络, 优化算法, Regret 界

Abstract:

Aiming at the problem of learning streaming data collected by a decentralized network in an online manner, a decentralized online learning algorithm — Decentralized Online alternating direction method of Multipliers (DOM) was proposed based on the Alternating Direction Method of Multipliers (ADMM). Firstly, observing that decentralized online learning required each node to update its local iterate based on new local data while keeping the estimation of all the nodes converged to a consensual iterate, a mathematical model was developed and solved by DOM. Secondly, a Regret bound of decentralized online learning was defined to evaluate performance of online estimation. DOM was proved to be convergent when the instantaneous local cost functions were convex, and the convergence rate was given. Finally, the results of numerical experiments show that, compared with existing algorithms such as Distributed Online Gradient Descent (DOGD) and Distributed Autonomous Online Learning (DAOL), the proposed algorithm DOM has the fastest convergence rate.

Key words: Alternating Direction Method of Multipliers (ADMM), online learning, decentralized network, optimization algorithm, Regret bound

中图分类号:

TP301.6

许浩锋, 凌青. 分布式在线交替方向乘子法[J]. 计算机应用, 2015, 35(6): 1595-1599.

XU Haofeng, LING Qing. Decentralized online alternating direction method of multipliers[J]. Journal of Computer Applications, 2015, 35(6): 1595-1599.

参考文献

[1] SHALEV S-S. Online learning and online convex optimization [J]. Foundations and Trends in Machine Learning, 2012, 4(2):107-194.
[2] WANG H, BANERJEE A. Online alternating direction method [C/OL]//Proceedings of the 2012 29th International Conference on Machine Learning. [2014-12-02]. http://arxiv.org/abs/1206.6448?context=stat.ML.
[3] LUO L. Research on large-scale machine learning [J]. Ship Electronic Engineering, 2013, 33(2): 9-12(罗霖.大规模机器学习问题研究[J].舰船电子工程, 2013, 33(2):9-12.)
[4] GAO Q. A new online optimization algorithm for non-smooth losses based on ADMM [J]. Computer Technology and Development, 2014, 24(2): 96-100(高乾坤.一种基于ADMM 的非光滑损失在线优化算法[J].计算机技术与发展, 2014, 24(2):96-100.)
[5] SCHIZAS I, RIBEIRO A, GIANNAKIS G. Consensus in Ad Hoc WSNs with noisy links — Part I: distributed estimation of deterministic signals [J]. IEEE Transactions on Signal Processing, 2008, 56(1): 350-364.
[6] NEDIC A, OZDAGLAR A. Distributed subgradient methods for multi-Agent optimization [J]. IEEE Transactions on Automatic Control, 2009, 54(1): 48-61.
[7] DUCHI J, AGARWAL A, WAINWRIGHT M. Dual averaging for distributed optimization: Convergence analysis and network scaling [J]. IEEE Transactions on Automatic Control, 2012, 57(3): 592–606.
[8] ZINKEVICH M. Online convex programming and generalized infinitesimal gradient ascent [EB/OL]. [2014-12-06]. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.6680&rep=rep1&type=pdf.
[9] YAN F, SUNDARAM S, VISHWANATHAN S, et al. Distributed autonomous online learning: Regrets and intrinsic privacy-preserving properties [J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(11): 2483-2493.
[10] HOSSEINI S, CHAPMAN A, MESBAHI M. Online distributed optimization via dual averaging [C]//Proceedings of the 2013 IEEE 52nd Annual Conference on Decision and Control.Piscataway: IEEE, 2013: 1484-1489.
[11] BAZERQUE J A, MATEOS G, GIANNAKIS G B. Group-Lasso on splines for spectrum cartography [J]. IEEE Transactions on Signal Processing, 2011, 59(10): 4648-4663.
[12] SHI W, LING Q, YUAN K, at el. On the linear convergence of the ADMM in decentralized consensus optimization [J]. IEEE Transactions on Signal Processing, 2014, 62(7): 1750-1761.
[13] KEKATOS V, GIANNAKIS G. Distributed robust power system state estimation [J]. IEEE Transactions on Power Systems, 2013, 28(2):1617-1626.
[14] MOTA J F C, XAVIER J M F, AGUIAR P M Q, at el. D-ADMM: a communication-efficient distributed algorithm for separable optimization [J]. IEEE Transactions on Signal Processing, 2013, 61(10): 2718-2723.
[15] PlATT J C. Fast training of support vector machines using sequential minimal optimization [M]. Cambridge: MIT Press, 1999: 185-208.

分布式在线交替方向乘子法

Decentralized online alternating direction method of multipliers

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李开荣, 刘爽, 胡倩倩, 唐亦媛. 基于转角约束的改进蚁群优化算法路径规划[J]. 计算机应用, 2021, 41(9): 2560-2568.
[2]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[3]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[4]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[5]	李辉, 吴传生, 刘俊, 刘文. 基于梯度曲面面积与稀疏约束的图像平滑方法[J]. 计算机应用, 2021, 41(7): 2039-2047.
[6]	汤安迪, 韩统, 徐登武, 谢磊. 基于混沌麻雀搜索算法的无人机航迹规划方法[J]. 计算机应用, 2021, 41(7): 2128-2136.
[7]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[8]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[9]	许飞雪, 刘勤明, 欧阳海玲, 叶春明. 基于性能合同的多部件系统维修策略模型优化[J]. 计算机应用, 2021, 41(4): 1184-1191.
[10]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[11]	郭一村, 陈华辉. 在线哈希算法研究综述[J]. 计算机应用, 2021, 41(4): 1106-1112.
[12]	冉家敏, 倪志伟, 彭鹏, 朱旭辉. 考虑空间众包工作者服务质量的任务分配策略及其萤火虫群优化算法求解[J]. 计算机应用, 2021, 41(3): 794-802.
[13]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[14]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[15]	陆荣秀, 陈明明, 杨辉, 朱建勇. 基于溶液图像时序特征的元素组分含量动态监测系统[J]. 计算机应用, 2021, 41(10): 3075-3081.