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

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

2、，所提出的dom算法具有更快的收敛性能。 关键词：交替方向乘子法；在线学习；分布式网络；优化算法；regret 界 中图分类号： tp301.6 文献标志码：a 英文摘要 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 指mu

3、ltipliersmultipliers （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 consensua

4、l 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 g

5、iven. 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 m

6、ethod of multipliers （admm）； online learning； decentralized network； optimization algorithm；regret bound 0 引言 本文研究无中心分布式网络中的在线学习问题。考虑一个由n个节点构成的无向连通网络。记ni为节点i的邻居集合，对于任意jni，（i，j）构成网络中的一条边。设xrpr是否应为实数集，用黑正表示？r：表示普通的实数集是需要学习的向量，f ik（x）：rpr是节点i在k时刻的本地即时损失函数。在k+1时刻，节点i利用即时损失函数fik（x）、前一时刻自身的估计xik、所有邻居节点的估计

7、xjk（jni），对x进行更新，得到的结果记为xik+1。经过t次迭代后，节点希望找到全局网络最优解： 当n=1时，式（1）变成典型的在单个节点上完成的集中式在线学习问题，其应用包括在线回归、在线分类等序贯决策任务1-4。当n1时，由节点分布式采集在线数据，并将数据实时传递至信息融合中心进行集中式在线学习的方式会带来高昂的通信代价。因此，利用节点间的协作进行无中心分布式在线学习，是一种适合于分布式网络结构的解决方案，其典型的应用包括无线传感器网络、认知无线电网络、协同机器人网络等。事实上，无中心分布式网络中的批处理优化问题近年已经得到了广泛研究5-7。为了对分布式网络采集的数据流进行实时分析处

8、理，本文将在线学习和分布式优化相结合，设计了一种分布式在线交替方向乘子法（decentralized online alternating direction method of multipliers，dom），并在理论上分析了其学习性能。 zinkevich在文献8中给出了在线学习算法的分析工具regret界。regret界表征了在渐近意义下在线学习与批处理学习结果之间的偏差。若当迭代次数t趋于无穷时regret何意，为正还是斜？正体 跟前面的是相同涵义regret /（nt）趋于0，则可以说明在线学习算法的解在渐近意义上收敛到批处理算法给出的最优解。对于分布式在线学习，本文定义如下两类r

9、egret。第一类是名义regret： 由于任一本地估计都可以成为分布式在线学习的解，故定义全局rg为所有rjg的最大值。因此，rg从全网角度表征了本地估计的好坏。集中式在线学习（n=1）中rn和rg是等同的；但分布式在线学习中两者并不等价，因此对rg的研究就显得尤为重要。 下面简要介绍现有的分布式在线学习算法及其理论上给出的regret界。受分布式次梯度法6的启发，分布式在线自主学习（distributed autonomous online learning，daol）法中每个节点将邻居节点估计进行加权平均，然后沿着自身即时损失函数的次梯度方向下降9。当损失函数为凸时，文献9证明了daol

10、算法具有o（t）的regret界，这跟文献8中集中式算法的情况是一致的。文献10则将文献7中的对偶平均方法应用于分布式在线学习，提出了分布式在线梯度下降（distributed online gradient descent，dogd）算法，并且在时间平均意义下，证明dogd算法具有o（t）的regret界。 上述分布式在线算法的设计都是基于本地损失函数的次梯度信息，适合节点计算能力有限的情况。本文考虑节点有足够计算能力，即每步迭代时每个节点都有能力求解一个优化问题，而不是仅在次梯度方向下降，从而使得每步得到的估计尽可能接近最优解。基于这一考虑，本文设计了一种基于交替方向乘子法（alterna

11、ting direction method of multipliers，admm）的分布式在线学习算法，称为分布式在线交替方向乘子法（dom）。admm是求解分布式批处理学习问题的重要方法。admm首先将分布式批处理学习问题转化成一个具有一致性约束的优化问题；然后交替最小化增广拉格朗日函数并更新拉格朗日乘子；在最终得到的分布式算法中，每个节点最小化本地损失函数与一个随着迭代次数变化的二次项之和5。分布式admm已经在无线传感器网络、智能电网等领域取得了成功的应用11-14。本文将其应用领域拓展至分布式网络的在线学习问题。 1 问题描述 分布式在线算法的平均损失和平均差异性如图1和图2所示。图

12、1表明，dom在三个算法中收敛最快；dogd在低精度阶段表现尚可，但在高精度阶段收敛速度明显变慢。图2表明，dogd在学习过程中保持着较高的一致性；而dom具有较大的差异。这一现象表明，学习过程中保持较高的一致性有可能会带来负面作用。其主要原因是，这些具有一致性的估计有可能会远离真实值，从而产生较大的平均损失。daol的平均损失和平均差异两者的性能均处于dom和dogd之间。 实验2 在线分类问题。考虑30个节点的随机网络，在可能的870条弧中随机选中174条连通。实验中采用的数据集为a9a15，其中包含30000个训练样本和16281个测试样本。k时刻节点i收到一训练样本（aik，bik），

13、其中aik是否应为黑正？r123是包含123个特征的向量，bik是一个二进制值的标量类别标签。此处选用支持向量机模型作为训练的优化模型，时刻k节点i的即时损失函数为： fik（x）=（/2）x2+max1-bikaik，x，0 其中正则化参数=0.1。样本训练以在线训练方式完成，训练时长t=1000，训练任务是得到分类器：x是否应为黑正r123；同时采用libsvm软件包对所有训练样本作集中式训练并将得到的结果为参考基线。分类错误率将作为此次性能评价指标。 图3纵坐标表示的错误率是以10为底数取对数后的结果。从图3可以看出，libsvm软件包对数据a9a分类错误率约为10-0.81=15.5%

14、。dom相比dogd和daol错误率较低，具有更好的分类效果。 5 结语 基于分布式网络中流式数据实时分析这一问题的需要，本文设计了分布式在线交替方向乘子法。通过详细的理论分析，本文证明了dom算法具有o（t） 的regret界，相关的数值实验则进一步表明dom算法的可行性。考虑到实际分布式网络中数据的异步处理分析更具普遍性，故设计相关的在线异步算法可以成为下一个研究方向。 参考文献： 1shalev ss. online learning and online convex optimization j. foundations and trends in machine learning，

15、 2012， 4（2）：107-194. 2wang h， banerjee a. online alternating direction method c/ol/ proceedings of the 2012 29th international conference on machine learning. 2014-12-02. http：/abs/1206.6448？context=stat.ml. 3luo l. research on largescale machine learning j. ship electronic engineering， 2013， 33（2）： 9-12（罗霖.大规模机器学