摘要：针对如何对分布式网络采集的数据进行在线学习的问题，提出了一种基于交替方向乘子法（ADMM）的分布式在线学习优化算法――分布式在线交替方向乘子法（DOM）。首先，针对分布式在线学习需要各节点根据新采集的数据来更新本地估计，同时保持网络中所有节点的估计趋于一致这一问题，建立了数学模型并设计DOM算法对其进行求解。其次，针对分布式在线学习问题定义了Regret 界，用以表征在线估计的性能；证明了当本地即时损失函数是凸函数时，DOM算法是收敛的，并给出了其收敛速度。最后，通过数值仿真实验结果表明，相比现有的分布式在线梯度下降法（DOGD）和分布式在线自主学习算法（DAOL），所提出的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 指multipliersMultipliers （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
0 引言
本文研究无中心分布式网络中的在线学习问题。考虑一个由n个节点构成的无向连通网络。记Ni为节点i的邻居集合，对于任意j∈Ni，（i，j）构成网络中的一条边。设x～∈RpR是否应为实数集，用黑正表示？R：表示普通的实数集是需要学习的向量，f ik（x～）：Rp→R是节点i在k时刻的本地即时损失函数。在k+1时刻，节点i利用即时损失函数fik（x～）、前一时刻自身的估计xik、所有邻居节点的估计xjk（j∈Ni），对x～进行更新，得到的结果记为xik+1。经过T次迭代后，节点希望找到全局网络最优解：
当n=1时，式（1）变成典型的在单个节点上完成的集中式在线学习问题，其应用包括在线回归、在线分类等序贯决策任务[1-4]。当n>1时，由节点分布式采集在线数据，并将数据实时传递至信息融合中心进行集中式在线学习的方式会带来高昂的通信代价。因此，利用节点间的协作进行无中心分布式在线学习，是一种适合于分布式网络结构的解决方案，其典型的应用包括无线传感器网络、认知无线电网络、协同机器人网络等。事实上，无中心分布式网络中的批处理优化问题近年已经得到了广泛研究[5-7]。为了对分布式网络采集的数据流进行实时分析处理，本文将在线学习和分布式优化相结合，设计了一种分布式在线交替方向乘子法（Decentralized online alternating direction method of Multipliers，DOM），并在理论上分析了其学习性能。
Zinkevich在文献[8]中给出了在线学习算法的分析工具――Regret界。Regret界表征了在渐近意义下在线学习与批处理学习结果之间的偏差。若当迭代次数T趋于无穷时Regret何意，为正还是斜？正体 跟前面的是相同涵义Regret /（nT）趋于0，则可以说明在线学习算法的解在渐近意义上收敛到批处理算法给出的最优解。对于分布式在线学习，本文定义如下两类Regret。第一类是名义Regret： 由于任一本地估计都可以成为分布式在线学习的解，故定义全局RG为所有RjG的最大值。因此，RG从全网角度表征了本地估计的好坏。集中式在线学习（n=1）中RN和RG是等同的；但分布式在线学习中两者并不等价，因此对RG的研究就显得尤为重要。
下面简要介绍现有的分布式在线学习算法及其理论上给出的Regret界。受分布式次梯度法[6]的启发，分布式在线自主学习（Distributed Autonomous Online Learning，DAOL）法中每个节点将邻居节点估计进行加权平均，然后沿着自身即时损失函数的次梯度方向下降[9]。当损失函数为凸时，文献[9]证明了DAOL算法具有O（T）的Regret界，这跟文献[8]中集中式算法的情况是一致的。文献[10]则将文献[7]中的对偶平均方法应用于分布式在线学习，提出了分布式在线梯度下降（Distributed Online Gradient Descent，DOGD）算法，并且在时间平均意义下，证明DOGD算法具有O（T）的Regret界。
上述分布式在线算法的设计都是基于本地损失函数的次梯度信息，适合节点计算能力有限的情况。本文考虑节点有足够计算能力，即每步迭代时每个节点都有能力求解一个优化问题，而不是仅在次梯度方向下降，从而使得每步得到的估计尽可能接近最优解。基于这一考虑，本文设计了一种基于交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）的分布式在线学习算法，称为分布式在线交替方向乘子法（DOM）。ADMM是求解分布式批处理学习问题的重要方法。ADMM首先将分布式批处理学习问题转化成一个具有一致性约束的优化问题；然后交替最小化增广拉格朗日函数并更新拉格朗日乘子；在最终得到的分布式算法中，每个节点最小化本地损失函数与一个随着迭代次数变化的二次项之和[5]。分布式ADMM已经在无线传感器网络、智能电网等领域取得了成功的应用[11-14]。本文将其应用领域拓展至分布式网络的在线学习问题。
1 问题描述
fik（x～）=（κ/2）‖x～‖2+max{1-bik〈aik，x～〉，0}
图3纵坐标表示的错误率是以10为底数取对数后的结果。从图3可以看出，Libsvm软件包对数据a9a分类错误率约为10-0.81=15.5%。DOM相比DOGD和DAOL错误率较低，具有更好的分类效果。
5 结语
基于分布式网络中流式数据实时分析这一问题的需要，本文设计了分布式在线交替方向乘子法。通过详细的理论分析，本文证明了DOM算法具有O（T） 的Regret界，相关的数值实验则进一步表明DOM算法的可行性。考虑到实际分布式网络中数据的异步处理分析更具普遍性，故设计相关的在线异步算法可以成为下一个研究方向。
参考文献：