求解二次損失函數優化問題的分布式共軛梯度算法

于潔,孟文輝

(西北大學數學學院,陜西 西安 710127)

1 引言

由于現代數據集的規模和復雜性激增,使用傳統的集中式算法優化損失函數對集中服務器的性能要求非常高,甚至無法求解.而且目前許多大型工程規模的應用程序中,數據集是以分散的方式在集群上收集和存儲的,典型的例子是用戶點擊量或搜索查詢記錄,因此開發利用分布式處理大型數據集的算法變得至關重要.

由于分布式優化的重要性,已有很多關于海量數據集分布式算法的文獻問世.這些分布式算法分為兩類,一類算法是基于損失函數的一階導數信息,例如分布式梯度下降法[1-4],分布式對偶平均算法[5-6],分布式增廣拉格朗日算法[7-8]和分布式交替方向乘子法[9-11]以及其各種變體.雖然它們之間有很大差異,但基本步驟都可以歸結為先進行局部的梯度下降,然后與主機器交換變量和信息平均.由于這些算法僅利用了損失函數的一階導數信息,導致對下降方向的曲率估計不準確,通常收斂速度較慢.另一類算法是基于損失函數的二階導數信息來構造牛頓步長,但由于牛頓步長的分布式近似很難設計,基于真正二階導數信息的分布式牛頓算法是不可行的.目前,基于損失函數二階導數信息研究較多的是分布式牛頓類算法[12-15],此類算法比大多數一階方法具有更快的收斂速度,但計算目標函數的二階信息計算量較大.

本文的算法思想來源于共軛梯度法.共軛梯度法只需利用一階導數的信息,克服了最速下降法收斂速度慢的缺陷,避免了牛頓法要計算Hesse矩陣并求逆的缺點,因此共軛梯度法是求解大型線性方程組最有效的方法之一[16].然而,目前在分布式環境中對共軛梯度算法的研究較少,為豐富這一方面的文獻,本文在共軛梯度法的基礎知識上設計一種分布式共軛梯度算法.特別地,共軛梯度法優化正定二次函數具有二次終止性,本文主要利用該算法對線性回歸模型的二次損失函數進行優化.首先設計分布式共軛梯度算法的流程,其中子機器與主機器通過平均子機器上的信息互相通信,在每次迭代中進行兩輪通信,且僅傳輸向量信息和標量信息,沒有高階信息的傳輸,通信成本較低.其次從理論上證明該算法是線性收斂的.最后通過模擬實驗發現:分布式共軛梯度算法比ADMM[10]更快地趨于集中式算法,且其收斂速度隨樣本量的增加而變快,隨機器臺數的增加而減小;計算誤差隨樣本量的增加而減小,隨機器臺數的增加而增大.

2 分布式共軛梯度算法

本節詳細介紹對線性回歸模型利用分布式共軛梯度算法優化其二次損失函數的具體流程.在每輪通信中,子機器與主機器相互交換消息,并且在兩輪通信之間,子機器僅基于它們的本地信息進行計算,該本地信息包括本地數據集和之前接收的消息.

線性回歸是一種簡單且應用廣泛的統計模型,本文針對其損失函數設計了一種分布式共軛梯度算法.由線性回歸模型,生成N個樣本數據{xi,yi}(i=1,2,···,N),

其中xi∈Rp,θ∈Rp,?i是均值為0,方差為1的獨立高斯隨機變量.

對回歸問題(1),典型的損失函數是均方誤差損失:

本文的目標是最小化局部損失函數之和(總損失函數):

然而,在大數據環境下,集中式服務器的可靠性差,且成本過高.在分布式算法中,將樣本數據{xi,yi}(i=1,···,N)平均分給m臺子機器 (假設N=nm),每臺子機器有n組數據{xi,yi},則第j臺子機器上的損失函數為

分布式算法的目標是最小化總損失函數:

考慮無約束優化方法共軛梯度法,迭代格式如下θ(k+1)=θ(k)+λ(k)p(k),其中p(k)為共軛方向,λ(k)為步長因子,通過精確或者非精確線性搜索得到.

下面基于上述算法過程設計分布式共軛梯度法求解(3)式,最大的不同之處在于步長因子λ(k)的分布式近似.在第k次迭代中(k=0,1,···),每臺子機器上的共軛方向法迭代公式為,其中p(k)為共軛方向,為步長因子.對于正定二次函數(2)式,精確線性搜索因子

對上式求極小值點得到

并分配給每臺子機器,這就構成了第一輪通信.由主機器上的信息更新迭代點θ(k):

其中p(k)為當前迭代的下降方向.

利用當前迭代的全局梯度g(k),更新每臺子機器的梯度:將獲得的局部梯度傳送到主機器上,計算全局梯度:

并更新主機器上的下降方向:p(k+1)=?g(k+1)+β(k)p(k),其中β(k)是F-R公式:

再將g(k+1),p(k+1)傳播回每臺子機器,這就構成了第k次迭代中的第二輪通信,具體通信方法如上圖1所示.如此往復循環迭代,直至求出符合終止條件的最優解.

圖1 第k次迭代過程中機器之間的通信示意圖

1分布式共軛梯度算法Input:{xi,yi}(i=1,···,N),xi∈ Rp,yi是常數.規定:Aj=n∑i=1 xixTi 是p階對稱正定矩陣,Bj=n∑i=1-yixTi ∈ Rp是行向量,j=1,2,···,m,N=nm.Output:θ(k):每次迭代的最優解.1:initial θ(0):將第一臺子機器最小化(2)式的解作為初始迭代點,發送給主機器,再傳送回每臺子機器;g(0)j =1 n(Ajθ(0)+Bj):計算每臺子機器上的初始梯度,發送給主機器;g(0)=1 m m∑j=1 g(0)j,p(0)=-g(0):主機器上計算全局初始梯度和初始下降方向,由主機器將g(0),p(0)傳播回每臺子機器.2:for k=0,1,···,do 3: if|g(k)|>? then 4: for j=1,2,···,m do 5: 計算每臺子機器上的步長:λ(k)j = (g(k))Tg(k)1 n(p(k))TAjp(k).6: end for 7: 將 λ(k)j 傳送給主機器,計算全局步長:λ(k)=1 m m∑j=1 λ(k)j,并分配給每臺子機器.8: 在主機器上更新迭代點:θ(k+1)=θ(k)+λ(k)p(k).9: 更新每臺子機器的梯度:10: for j=1,2,···,m do 11: g(k+1)j =g(k)+1 nλ(k)Ajp(k).12: end for 13: 將更新好的梯度傳送給主機器,計算全局梯度:g(k+1)=1 m m∑j=1 g(k+1)j.14: 在主機器上計算: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)傳播回每臺子機器.16: else 17: break 18: end if 19:end for

上述是分布式共軛梯度算法最小化二次損失函數的全部流程,如算法1所示,該算法僅利用了損失函數的一階導數信息,在每次迭代過程中機器之間執行兩輪通信,子機器將本地步長和本地梯度傳輸給主機器,主機器平均化之后再發送到每臺子機器.該算法同時有計算簡單和通信成本較低的優點.下節將給出算法的收斂性證明.

3 收斂性分析

本節主要分析分布式共軛梯度算法在二次損失函數上的收斂性.理論上證明了對二次損失函數(3)式,在滿足子機器上的對稱正定矩陣相似時,即

Aj≈Ak,j=k=1,2,···,m,

分布式共軛梯度算法具有線性收斂性.

對極小化問題(3),集中式服務器下的總損失函數為

由于A是正定對稱矩陣,從而AH=A,則上式中第二個不等式是由引理3.1得到.證畢.

經過以上的理論分析可以證明分布式共軛梯度算法具有線性收斂速度,且當β越小時,即每臺子機器上的正定對稱矩陣Aj,j=1,2,···,m越相似,收斂速度越快.

4 模擬實驗

本節主要論述分布式共軛梯度算法的初步實驗結果.驗證了分布式共軛梯度算法的誤差在一定的迭代次數后與集中式性能相匹配,且較之ADMM收斂速度更快.在與ADMM的對比實驗中發現,分布式共軛梯度法的誤差與收斂速度受機器中樣本量大小和機器臺數的影響,而ADMM的收斂速度對機器臺數并不敏感.

考慮使用合成數據集求解簡單的線性回歸模型,其中所有參數都可以被顯式控制.根據模型yi=+?i,生成N個訓練樣本{xi,yi}(i=1,2,···,N),其中{xi}由多元正態分布N(0,Σ)生成,xi∈R10,?i是均值為0,方差為1的相互獨立的高斯隨機變量,協方差矩陣Σ是Σii=i-1.2的對角陣,θ是全為1的向量.給定一組隨機生成的N個樣本{xi,yi},將之隨機平均分配給m臺子機器(假設N=nm).應用本文提出的分布式共軛梯度算法求解下列形式的均方誤差最小化問題:

圖2展示了在d=10,N=6000,m=20時,隨著迭代次數的增加,均方誤差逐漸減小,在迭代大約十次時收斂.為了對比,本文還實現了分布式ADMM[10],這是一種分布式優化的標準方法.并且觀察到分布式共軛梯度算法比ADMM明顯在更少的迭代次數中匹配于集中式性能.

圖2 DCG與ADMM對比圖

圖3顯示了分布式共軛梯度算法和分布式ADMM在不同機器臺數m下隨樣本總量N增加的收斂行為.分布式共軛梯度算法的結果清楚地表明了線性收斂性,而且收斂速度隨著樣本總量N的增加而提高,誤差隨N增加而減小.隨機器臺數m的增加收斂速度變慢,誤差增大.(在m很大時,有可能導致不收斂,這可能由于每臺子機器上樣本量過少的緣故.)相比之下,雖然增加樣本量N會提高ADMM的精度,但收斂速度較慢,并且收斂速度受機器臺數m的影響較小.

圖3 DCG和ADMM收斂性能與樣本量的關系圖

5 結論

本文提出一種分布式共軛梯度算法,該算法具有計算簡單和通信成本較低的優點.經過理論分析表明,所提出的算法在滿足一定的條件下線性收斂.在合成數據集上,對線性回歸模型進行模擬實驗,并與研究成熟的分布式ADMM算法做對比,結果發現本文所提出的算法能在更少迭代次數下匹配于集中式性能,并且收斂速度明顯快于ADMM.

由于個人電腦硬件設備的限制,文章中實驗的數據量和維度都不足夠大,但實驗結果可以同理到大數據環境下.本文基于簡單二次損失函數對分布式共軛梯度算法的性能做了研究,為未來將此算法擴展到非二次函數上奠定了一定的基礎.