基于交替方向乘子法的分布式在线学习算法.pdf

中圈科孽技求犬誊硕士学位论文基于交替方向乘子法的分布式在线学习算法作者姓名: 学科专业: 导师姓名: 完成时间: 许浩锋控制科学与工程凌青副教授二O一五年五月万方数据 University ofScience andTechnology ofChina Adissertation formaster,Sdegree DeCentralized Online Learning Algorithms Based 0n Alternating Direction Method of Multipliers Author’S Name: Haofeng Xu Speciality: Control Technology and Engineering Supervisor: Associate Professor Qing Ling T1●o' FinlSneQ 1lme: May,201 5 万方数据中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文,是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外,论文中不包含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确的说明。作者签名:辫签字日期:函,,学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权,即:学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅,可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。么开口保密——年作者签名鲑茎壁导师签名: 签字日期:±!垒至塑!≯日万方数据摘要摘要随着网络技术的发展,社交网络、互联网金融、物联网等诸多相关应用领域快速崛起。上述应用每天都会产生海量数据;这些数据中除少量非实时的静态数据,更多的是具有实时特性的流数据。对于海量流数据的信息提取问题, 利用传统的分布式批处理学习方法已很难解决。因此,本文致力于研究流数据的分布式实时在线学习问题。本文针对分布式在线学习问题,提出了基于交替方向乘子法(ADMM)的同步分布式在线学习算法(oDM)与异步分布式在线学习算法(aoDM)。首先,针对分布式在线学习需要各节点根据新采集的数据来更新本地估计,同时保持网络中所有节点的估计趋于一致这一问题,建立了数学模型并设计同步算法oDM与异步算法aoDM进行求解。其次,针对分布式在线学习问题定义了同步与异步情况下的Regret界,用以刻画在线学习与批处理学习所带来的目标函数的差异。其中,对于同步算法oDM,本文证明了当本地即时损失函数是凸函数且函数次梯度有界时,算法具有0(订)的Regret界和D(订/丁) 的收敛速度;当本地即时损失函数是强凸函数且函数次梯度有界时,算法具有O(109T)的Regret界和O(109T/T)的收敛速度。对于异步算法aoDM,本文证明了当定义域是紧集且函数利普希茨连续时,算法具有0(1)的Regret界和 O(1/T)的收敛速度。最后,通过数值实验,证明了分布式在线学习算法oDM 与aoDM的有效性。关键词:分布式网络,在线学习,交替方向乘子法,Regret界万方数据 ABSTRACT AB STRACT With thedevelopment work technologies,working, bank— ing, ofthings,as well asmany other applications riserapidly and generate huge amounts ofdataevery thesedata,a small fractionisstaticand not ,while themajority isstreaming datathatneed real-time the learning ofhuge streaming data,traditional decentralized batch learning methods have shown theirdeficiency,which motivates theresearch onprocessing streaming datawith decentralized real-time onlinelearning algorithms inthisthesis. This thesisconsiders theonlineleaming pr