Towards More Efficient Stochastic Decentralized Learning更有效的随机分散学习： 快速收敛与稀疏通信

《Towards More Efficient Stochastic Decentralized Learning更有效的随机分散学习： 快速收敛与稀疏通信》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、TowardsMoreEfficientStochasticDecentralizedLearning:FasterConvergenceandSparseCommunicationZebangShen1AryanMokhtari2TengfeiZhou1PeilinZhao3HuiQian1Abstractvariableofnoden,theproblemofinterestis()XN1XqRecently,thedecentralizedoptimizationproblemminfn(xn),fn,i(xn).(

2、1){xn}Nqisattractinggrowingattention.Mostexistingn=1n=1i=1s.t.x1=...=xNmethodsaredeterministicwithhighper-iterationcostandhaveaconvergenceratequadraticallyTheformulation(1)capturesproblemsinsensornetwork,dependingontheproblemconditionnumber.Be-mobilecomputation,a

3、ndmulti-agentcontrol,whereeithersides,thedensecommunicationisnecessarytoefficientlycentralizingdataorgloballyaggregateinterme-ensuretheconvergenceevenifthedatasetisdiateresultsisunfeasible(Johansson,2008;Bulloetal.,sparse.Inthispaper,wegeneralizethedecentral-2009;

4、Foreroetal.,2010;Ribeiro,2010).izedoptimizationproblemtoamonotoneopera-Developingefficientmethodsforsuchproblemhasbeentorrootfindingproblem,andproposeastochas-oneofthemajoreffortsinthemachinelearningcommunity.ticalgorithmnamedDSBAthat(i)convergesge-Whileearlyworkda

5、tesbackto1980’s(Tsitsiklisetal.,ometricallywitharatelinearlydependingonthe1986;Bertsekas&Tsitsiklis,1989),consensusbasedgradi-problemconditionnumber,and(ii)canbeimple-entdescentanddualaveragingmethodswithsublinearcon-mentedusingsparsecommunicationonly.Ad-vergence

6、havemadetheirdebut(Nedic&Ozdaglar,2009;ditionally,DSBAhandleslearningproblemslikeDuchietal.,2012),whichconsistoftwosteps:allnodes(i)AUC-maximizationwhichcannotbetackledeffi-gatherthe(usuallydense)iteratesfromtheirsneighborsviacientlyinthedecentralizedsetting.Exper

7、imentscommunicationtocomputeaweightedaverage,and(ii)up-onconvexminimizationandAUC-maximizationdatetheaveragebythefullgradientofthelocalfntoob-validatetheefficiencyofourmethod.tainnewiterates.Followingsuchprotocol,successorswithlinearconvergencehavebeenproposedrece

8、ntly(Shietal.,2015a;Mokhtarietal.,2016;Scamanetal.,2017).1.IntroductionDespitetheprogress,twoentangledchallenges,realizedbytheaboveinterlacingsteps,stillremain