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

分布式在线交替方向乘子法摘要：针对如何对分布式网络采集的数据进行在线学习的问题提出了一种基于交替方向乘子法（ADMM）的分布式在线学习优化算法――分布式在线交替方向乘子法（DOM）。首先针对分布式在线学习需要各节点根据新采集的数据来更新本地估计同时保持网络中所有节点的估计趋于一致这一问题建立了数学模型并设计DOM算法对其进行求解。其次针对分布式在线学习问题定义了Regret界用以表征在线估计的性能；证明了当本地即时损失函数是凸函数时DOM算法是收敛的并给出了其收敛速度。最后通过数值仿真实验结果表明相比现有的分布式在线梯度下降法（DOGD）和分布式在线自主学习算法（DAOL）所提出的DOM算法具有更快的收敛性能。关键词：交替方向乘子法；在线学习；分布式网络；优化算法；Regret界中图分类号：TP301.6文献标志码：A英文摘要Abstract：Aimingattheproblemoflearningstreamingdatacollectedbyadecentralizednetworkinanonlinemanneradecentralizedonlinelearningalgorithm―DecentralizedOnlinealternatingdirectionmethodof指multipliersMultipliers（DOM）wasproposedbasedontheAlternatingDirectionMethodofMultipliers（ADMM）.FirstlyobservingthatdecentralizedonlinelearningrequiredeachnodetoupdateitslocaliteratebasedonnewlocaldatawhilekeepingtheestimationofallthenodesconvergedtoaconsensualiterateamathematicalmodelwasdevelopedandsolvedbyDOM.SecondlyaRegretboundofdecentralizedonlinelearningwasdefinedtoevaluateperformanceofonlineestimation.DOMwasprovedtobeconvergentwhentheinstantaneouslocalcostfunctionswereconvexandtheconvergenceratewasgiven.FinallytheresultsofnumericalexperimentsshowthatcomparedwithexistingalgorithmssuchasDistributedOnlineGradientDescent（DOGD）andDistributedAutonomousOnlineLearning（DAOL）theproposedalgorithmDOMhasthefastestconvergencerate.英文关键词Keywords：AlternatingDirectionMethodofMultipliers（ADMM）；onlinelearning；decentralizednetwork；optimizationalgorithm；Regretbound0引言本文研究无中心分布式网络中的在线学习问题。考虑一个由n个节点构成的无向连通网络。记Ni为节点i的邻居集合对于任意j∈Ni（ij）构成网络中的一条边。设x～∈RpR是否应为实数集用黑正表示？R：表示普通的实数集是需要学习的向量fik（x～）：RpR是节点i在k时刻的本地即时损失函数。在k+1时刻节点i利用即时损失函数fik（x～）、前一时刻自身的估计xik、所有邻居节点的估计xjk（j∈Ni）对x～进行更新得到的结果记为xik+1。经过T次迭代后节点希望找到全局网络最优解：当n=1时式（1）变成典型的在单个节点上完成的集中式在线学习问题其应用包括在线回归、在线分类等序贯决策任务[1-4]。当n>1时由节点分布式采集在线数据并将数据实时传递至信息融合中心进行集中式在线学习的方式会带来高昂的通信