求解二次損失函數(shù)優(yōu)化問題的分布式共軛梯度算法
2022-03-31 07:53:52于潔孟文輝
于潔,孟文輝
(西北大學(xué)數(shù)學(xué)學(xué)院,陜西 西安 710127)
1 引言
由于現(xiàn)代數(shù)據(jù)集的規(guī)模和復(fù)雜性激增,使用傳統(tǒng)的集中式算法優(yōu)化損失函數(shù)對(duì)集中服務(wù)器的性能要求非常高,甚至無法求解.而且目前許多大型工程規(guī)模的應(yīng)用程序中,數(shù)據(jù)集是以分散的方式在集群上收集和存儲(chǔ)的,典型的例子是用戶點(diǎn)擊量或搜索查詢記錄,因此開發(fā)利用分布式處理大型數(shù)據(jù)集的算法變得至關(guān)重要.
由于分布式優(yōu)化的重要性,已有很多關(guān)于海量數(shù)據(jù)集分布式算法的文獻(xiàn)問世.這些分布式算法分為兩類,一類算法是基于損失函數(shù)的一階導(dǎo)數(shù)信息,例如分布式梯度下降法[1-4],分布式對(duì)偶平均算法[5-6],分布式增廣拉格朗日算法[7-8]和分布式交替方向乘子法[9-11]以及其各種變體.雖然它們之間有很大差異,但基本步驟都可以歸結(jié)為先進(jìn)行局部的梯度下降,然后與主機(jī)器交換變量和信息平均.由于這些算法僅利用了損失函數(shù)的一階導(dǎo)數(shù)信息,導(dǎo)致對(duì)下降方向的曲率估計(jì)不準(zhǔn)確,通常收斂速度較慢.另一類算法是基于損失函數(shù)的二階導(dǎo)數(shù)信息來構(gòu)造牛頓步長,但由于牛頓步長的分布式近似很難設(shè)計(jì),基于真正二階導(dǎo)數(shù)信息的分布式牛頓算法是不可行的.目前,基于損失函數(shù)二階導(dǎo)數(shù)信息研究較多的是分布式牛頓類算法[12-15],此類算法比大多數(shù)一階方法具有更快的收斂速度,但計(jì)算目標(biāo)函數(shù)的二階信息計(jì)算量較大.
本文的算法思想來源于共軛梯度法.共軛梯度法只需利用一階導(dǎo)數(shù)的信息,克服了最速下降法收斂速度慢的缺陷,避免了牛頓法要計(jì)算Hesse矩陣并求逆的缺點(diǎn),因此共軛梯度法是求解大型線性方程組最有效的方法之一[16].然而,目前在分布式環(huán)境中對(duì)共軛梯度算法的研究較少,為豐富這一方面的文獻(xiàn),本文在共軛梯度法的基礎(chǔ)知識(shí)上設(shè)計(jì)一種分布式共軛梯度算法.特別地,共軛梯度法優(yōu)化正定二次函數(shù)具有二次終止性,本文主要利用該算法對(duì)線性回歸模型的二次損失函數(shù)進(jìn)行優(yōu)化.首先設(shè)計(jì)分布式共軛梯度算法的流程,其中子機(jī)器與主機(jī)器通過平均子機(jī)器上的信息互相通信,在每次迭代中進(jìn)行兩輪通信,且僅傳輸向量信息和標(biāo)量信息,沒有高階信息的傳輸,通信成本較低.其次從理論上證明該算法是線性收斂的.最后通過模擬實(shí)驗(yàn)發(fā)現(xiàn):分布式共軛梯度算法比ADMM[10]更快地趨于集中式算法,且其收斂速度隨樣本量的增加而變快,隨機(jī)器臺(tái)數(shù)的增加而減小;計(jì)算誤差隨樣本量的增加而減小,隨機(jī)器臺(tái)數(shù)的增加而增大.
2 分布式共軛梯度算法
本節(jié)詳細(xì)介紹對(duì)線性回歸模型利用分布式共軛梯度算法優(yōu)化其二次損失函數(shù)的具體流程.在每輪通信中,子機(jī)器與主機(jī)器相互交換消息,并且在兩輪通信之間,子機(jī)器僅基于它們的本地信息進(jìn)行計(jì)算,該本地信息包括本地?cái)?shù)據(jù)集和之前接收的消息.
線性回歸是一種簡單且應(yīng)用廣泛的統(tǒng)計(jì)模型,本文針對(duì)其損失函數(shù)設(shè)計(jì)了一種分布式共軛梯度算法.由線性回歸模型,生成N個(gè)樣本數(shù)據(jù){xi,yi}(i=1,2,···,N),
其中xi∈Rp,θ∈Rp,?i是均值為0,方差為1的獨(dú)立高斯隨機(jī)變量.
對(duì)回歸問題(1),典型的損失函數(shù)是均方誤差損失:
本文的目標(biāo)是最小化局部損失函數(shù)之和(總損失函數(shù)):
然而,在大數(shù)據(jù)環(huán)境下,集中式服務(wù)器的可靠性差,且成本過高.在分布式算法中,將樣本數(shù)據(jù){xi,yi}(i=1,···,N)平均分給m臺(tái)子機(jī)器 (假設(shè)N=nm),每臺(tái)子機(jī)器有n組數(shù)據(jù){xi,yi},則第j臺(tái)子機(jī)器上的損失函數(shù)為
分布式算法的目標(biāo)是最小化總損失函數(shù):
考慮無約束優(yōu)化方法共軛梯度法,迭代格式如下θ(k+1)=θ(k)+λ(k)p(k),其中p(k)為共軛方向,λ(k)為步長因子,通過精確或者非精確線性搜索得到.
下面基于上述算法過程設(shè)計(jì)分布式共軛梯度法求解(3)式,最大的不同之處在于步長因子λ(k)的分布式近似.在第k次迭代中(k=0,1,···),每臺(tái)子機(jī)器上的共軛方向法迭代公式為,其中p(k)為共軛方向,為步長因子.對(duì)于正定二次函數(shù)(2)式,精確線性搜索因子
對(duì)上式求極小值點(diǎn)得到
并分配給每臺(tái)子機(jī)器,這就構(gòu)成了第一輪通信.由主機(jī)器上的信息更新迭代點(diǎn)θ(k):
其中p(k)為當(dāng)前迭代的下降方向.
利用當(dāng)前迭代的全局梯度g(k),更新每臺(tái)子機(jī)器的梯度:將獲得的局部梯度傳送到主機(jī)器上,計(jì)算全局梯度:
并更新主機(jī)器上的下降方向:p(k+1)=?g(k+1)+β(k)p(k),其中β(k)是F-R公式:
再將g(k+1),p(k+1)傳播回每臺(tái)子機(jī)器,這就構(gòu)成了第k次迭代中的第二輪通信,具體通信方法如上圖1所示.如此往復(fù)循環(huán)迭代,直至求出符合終止條件的最優(yōu)解.
圖1 第k次迭代過程中機(jī)器之間的通信示意圖
1分布式共軛梯度算法Input:{xi,yi}(i=1,···,N),xi∈ Rp,yi是常數(shù).規(guī)定:Aj=n∑i=1 xixTi 是p階對(duì)稱正定矩陣,Bj=n∑i=1-yixTi ∈ Rp是行向量,j=1,2,···,m,N=nm.Output:θ(k):每次迭代的最優(yōu)解.1:initial θ(0):將第一臺(tái)子機(jī)器最小化(2)式的解作為初始迭代點(diǎn),發(fā)送給主機(jī)器,再傳送回每臺(tái)子機(jī)器;g(0)j =1 n(Ajθ(0)+Bj):計(jì)算每臺(tái)子機(jī)器上的初始梯度,發(fā)送給主機(jī)器;g(0)=1 m m∑j=1 g(0)j,p(0)=-g(0):主機(jī)器上計(jì)算全局初始梯度和初始下降方向,由主機(jī)器將g(0),p(0)傳播回每臺(tái)子機(jī)器.2:for k=0,1,···,do 3: if|g(k)|>? then 4: for j=1,2,···,m do 5: 計(jì)算每臺(tái)子機(jī)器上的步長:λ(k)j = (g(k))Tg(k)1 n(p(k))TAjp(k).6: end for 7: 將 λ(k)j 傳送給主機(jī)器,計(jì)算全局步長:λ(k)=1 m m∑j=1 λ(k)j,并分配給每臺(tái)子機(jī)器.8: 在主機(jī)器上更新迭代點(diǎn):θ(k+1)=θ(k)+λ(k)p(k).9: 更新每臺(tái)子機(jī)器的梯度:10: for j=1,2,···,m do 11: g(k+1)j =g(k)+1 nλ(k)Ajp(k).12: end for 13: 將更新好的梯度傳送給主機(jī)器,計(jì)算全局梯度:g(k+1)=1 m m∑j=1 g(k+1)j.14: 在主機(jī)器上計(jì)算:p(k+1)=-g(k+1)+β(k)p(k), β(k)=(g(k+1))Tg(k+1)(g(k))Tg(k).15: 并將g(k+1),p(k+1)傳播回每臺(tái)子機(jī)器.16: else 17: break 18: end if 19:end for
上述是分布式共軛梯度算法最小化二次損失函數(shù)的全部流程,如算法1所示,該算法僅利用了損失函數(shù)的一階導(dǎo)數(shù)信息,在每次迭代過程中機(jī)器之間執(zhí)行兩輪通信,子機(jī)器將本地步長和本地梯度傳輸給主機(jī)器,主機(jī)器平均化之后再發(fā)送到每臺(tái)子機(jī)器.該算法同時(shí)有計(jì)算簡單和通信成本較低的優(yōu)點(diǎn).下節(jié)將給出算法的收斂性證明.
3 收斂性分析
本節(jié)主要分析分布式共軛梯度算法在二次損失函數(shù)上的收斂性.理論上證明了對(duì)二次損失函數(shù)(3)式,在滿足子機(jī)器上的對(duì)稱正定矩陣相似時(shí),即
Aj≈Ak,j=k=1,2,···,m,
分布式共軛梯度算法具有線性收斂性.
對(duì)極小化問題(3),集中式服務(wù)器下的總損失函數(shù)為
由于A是正定對(duì)稱矩陣,從而AH=A,則上式中第二個(gè)不等式是由引理3.1得到.證畢.
經(jīng)過以上的理論分析可以證明分布式共軛梯度算法具有線性收斂速度,且當(dāng)β越小時(shí),即每臺(tái)子機(jī)器上的正定對(duì)稱矩陣Aj,j=1,2,···,m越相似,收斂速度越快.
4 模擬實(shí)驗(yàn)
本節(jié)主要論述分布式共軛梯度算法的初步實(shí)驗(yàn)結(jié)果.驗(yàn)證了分布式共軛梯度算法的誤差在一定的迭代次數(shù)后與集中式性能相匹配,且較之ADMM收斂速度更快.在與ADMM的對(duì)比實(shí)驗(yàn)中發(fā)現(xiàn),分布式共軛梯度法的誤差與收斂速度受機(jī)器中樣本量大小和機(jī)器臺(tái)數(shù)的影響,而ADMM的收斂速度對(duì)機(jī)器臺(tái)數(shù)并不敏感.
考慮使用合成數(shù)據(jù)集求解簡單的線性回歸模型,其中所有參數(shù)都可以被顯式控制.根據(jù)模型yi=
圖2展示了在d=10,N=6000,m=20時(shí),隨著迭代次數(shù)的增加,均方誤差逐漸減小,在迭代大約十次時(shí)收斂.為了對(duì)比,本文還實(shí)現(xiàn)了分布式ADMM[10],這是一種分布式優(yōu)化的標(biāo)準(zhǔn)方法.并且觀察到分布式共軛梯度算法比ADMM明顯在更少的迭代次數(shù)中匹配于集中式性能.
圖2 DCG與ADMM對(duì)比圖
圖3顯示了分布式共軛梯度算法和分布式ADMM在不同機(jī)器臺(tái)數(shù)m下隨樣本總量N增加的收斂行為.分布式共軛梯度算法的結(jié)果清楚地表明了線性收斂性,而且收斂速度隨著樣本總量N的增加而提高,誤差隨N增加而減小.隨機(jī)器臺(tái)數(shù)m的增加收斂速度變慢,誤差增大.(在m很大時(shí),有可能導(dǎo)致不收斂,這可能由于每臺(tái)子機(jī)器上樣本量過少的緣故.)相比之下,雖然增加樣本量N會(huì)提高ADMM的精度,但收斂速度較慢,并且收斂速度受機(jī)器臺(tái)數(shù)m的影響較小.
圖3 DCG和ADMM收斂性能與樣本量的關(guān)系圖
5 結(jié)論
本文提出一種分布式共軛梯度算法,該算法具有計(jì)算簡單和通信成本較低的優(yōu)點(diǎn).經(jīng)過理論分析表明,所提出的算法在滿足一定的條件下線性收斂.在合成數(shù)據(jù)集上,對(duì)線性回歸模型進(jìn)行模擬實(shí)驗(yàn),并與研究成熟的分布式ADMM算法做對(duì)比,結(jié)果發(fā)現(xiàn)本文所提出的算法能在更少迭代次數(shù)下匹配于集中式性能,并且收斂速度明顯快于ADMM.
由于個(gè)人電腦硬件設(shè)備的限制,文章中實(shí)驗(yàn)的數(shù)據(jù)量和維度都不足夠大,但實(shí)驗(yàn)結(jié)果可以同理到大數(shù)據(jù)環(huán)境下.本文基于簡單二次損失函數(shù)對(duì)分布式共軛梯度算法的性能做了研究,為未來將此算法擴(kuò)展到非二次函數(shù)上奠定了一定的基礎(chǔ).
