李德權(quán)，王俊雅，馬 馳，周躍進(jìn)

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232000)(*通信作者電子郵箱784836893@qq.com)

0 引言

近年來, 網(wǎng)絡(luò)和分布式計(jì)算的迅猛發(fā)展造就了從大型集成電路計(jì)算機(jī)到分布式網(wǎng)絡(luò)工作站的一個(gè)躍變，這使得分布式網(wǎng)絡(luò)受到了越來越多的重視，并在傳感器網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)和智能電網(wǎng)等多個(gè)方面具有廣泛的應(yīng)用前景[1-3]。分布式網(wǎng)絡(luò)中的個(gè)體通過相互協(xié)調(diào)合作, 可以有效解決各種大規(guī)模復(fù)雜現(xiàn)實(shí)問題，提高數(shù)據(jù)傳遞效率，增強(qiáng)網(wǎng)絡(luò)魯棒性。文獻(xiàn)[4]基于分布式隨機(jī)梯度下降算法建立模型，不僅更好地利用了全局?jǐn)?shù)據(jù)信息，而且提高了分布式隨機(jī)梯度下降算法的收斂速度和性能。文獻(xiàn)[5]提出了基于Push-sum的分布式對(duì)偶平均算法解決優(yōu)化問題，但并不能實(shí)時(shí)處理網(wǎng)絡(luò)數(shù)據(jù)流，造成網(wǎng)絡(luò)中時(shí)間和資源浪費(fèi)，成本代價(jià)高。因?yàn)樵趯?shí)際應(yīng)用中，分布式網(wǎng)絡(luò)一般都運(yùn)行在動(dòng)態(tài)環(huán)境下，如可再生能源系統(tǒng)的調(diào)度和傳感器觀測(cè)是時(shí)變的，其不確定性對(duì)整個(gè)網(wǎng)絡(luò)的成本函數(shù)造成重大影響，導(dǎo)致建立的優(yōu)化問題更加復(fù)雜。為了解決這一問題，本文研究基于在線的分布式優(yōu)化算法，在線分布式優(yōu)化算法不僅有效提高了算法的魯棒性，且在機(jī)器學(xué)習(xí)和網(wǎng)絡(luò)數(shù)據(jù)流實(shí)時(shí)處理方面有著重要應(yīng)用[6-7]。作為衡量在線優(yōu)化算法性能的一個(gè)重要指標(biāo)，Regret界刻畫了隨時(shí)間推移的累積成本與最佳固定決策所產(chǎn)生的成本之間的差值，因此在線優(yōu)化算法的優(yōu)劣可由Regret界的大小進(jìn)行判斷。

在強(qiáng)連通網(wǎng)絡(luò)環(huán)境下，本文基于在線分布式對(duì)偶平均(Online Distributed Dual Averaging， ODDA)算法以Regret界作為底層網(wǎng)絡(luò)連通性的函數(shù)[8]，突出了網(wǎng)絡(luò)拓?fù)渑c在線算法之間的聯(lián)系，并廣泛應(yīng)用于高性能網(wǎng)絡(luò)的在線設(shè)計(jì)、信號(hào)處理、分布式控制等方面[9-10]。為了實(shí)現(xiàn)分布式對(duì)偶平均，文獻(xiàn)[5]要求網(wǎng)絡(luò)中的節(jié)點(diǎn)基于Push-sum算法達(dá)成一致性，本質(zhì)上是非線性算法，這就為求解帶來了困難, 而ODDA采用的是線性一致性算法。然而，和常用的分布式次梯度算法相比，ODDA是典型的一階分布式優(yōu)化算法，收斂速度較慢，對(duì)于一般凸優(yōu)化問題僅具有次線性收斂速率[11-12]。為了及時(shí)處理分析網(wǎng)絡(luò)數(shù)據(jù)流，提高收斂速率，改進(jìn)Regret界，本文將在線分布式對(duì)偶平均(ODDA)算法與添邊方法相結(jié)合，對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行優(yōu)化設(shè)計(jì)以實(shí)現(xiàn)算法更快的收斂速度，設(shè)計(jì)了一種改進(jìn)的快速一階分布式在線對(duì)偶平均優(yōu)化(Fast first-order Online Distributed Dual Average optimization， FODD)算法，并對(duì)其性能進(jìn)行了理論分析。

1 模型建立

1.1 圖論

網(wǎng)絡(luò)模型 個(gè)體或節(jié)點(diǎn)間的信息交換可建模成網(wǎng)絡(luò)Gt(V,Et,Pt)，其中：V={1,2,…,n}表示個(gè)體集合，Et?V×V表示網(wǎng)絡(luò)中所有邊構(gòu)成的集合，Pt表示Gt所對(duì)應(yīng)的權(quán)重矩陣。l～(i,j)∈Et表示t時(shí)刻連接節(jié)點(diǎn)i和j的第l條邊，Ni={j|(i,j)∈Et}∪{i}表示節(jié)點(diǎn)i在t時(shí)刻的鄰居集合。若任意兩個(gè)有序節(jié)點(diǎn)之間都存在一條路徑，則稱圖Gt是連通的。本文假設(shè)Gt任意時(shí)刻都是連通的，且邊有先后順序。

權(quán)重矩陣Pt為網(wǎng)絡(luò)拓?fù)鋱DGt所對(duì)應(yīng)的權(quán)重矩陣，且若(i,j)∈Et，(Pt)ij>0，否則(Pt)ij=0。本文的權(quán)重矩陣是雙隨機(jī)對(duì)稱矩陣，即滿足：

1.2 分布式在線優(yōu)化模型

分布式在線優(yōu)化算法中，t=0,1,…,T表示迭代次數(shù)，網(wǎng)絡(luò)中的節(jié)點(diǎn)i∈V在每次迭代t時(shí)給出一個(gè)本地估計(jì)，記作xi(t)，進(jìn)而對(duì)未知的本地凸損失函數(shù)ft,i(xi(t))進(jìn)行觀測(cè)。

本文考慮如下分布式凸優(yōu)化問題：

(1)

s.t.x∈χ

其中:ft,i(xi):Rd→R是僅為節(jié)點(diǎn)i∈V所知道的局部凸損失函數(shù)，x=(x1,x2,…,xn)∈χ表示所有節(jié)點(diǎn)本地估計(jì)的集合，χ是一個(gè)凸緊集。

為了衡量分布式在線學(xué)習(xí)優(yōu)化算法，對(duì)?t=0,1,…,T通常用如下兩類Regret界進(jìn)行刻畫。第一類是分布式在線Regret界：

(2)

(3)

在線優(yōu)化的目的是縮小Regret界，即隨著時(shí)間推移，盡可能縮小累積成本與最佳固定決策所產(chǎn)生的成本之間的差額。當(dāng)?shù)螖?shù)T→∞，RT/T→0是次線性的，說明在線學(xué)習(xí)算法的解在漸近意義上收斂到全局網(wǎng)絡(luò)最優(yōu)解，即RT=Ο(T)。

2 問題描述

2.1 連通度不斷增長(zhǎng)的進(jìn)化網(wǎng)絡(luò)

文獻(xiàn)[16-17]研究表明，ODDA的收斂速度與網(wǎng)絡(luò)拓?fù)涞拇鷶?shù)連通性有關(guān)。由文獻(xiàn)[17]的加邊方法，本文通過對(duì)底層網(wǎng)絡(luò)添邊，建立連通度不斷增長(zhǎng)的進(jìn)化網(wǎng)絡(luò)模型。

Gt是隨時(shí)間t單調(diào)遞增、連通度不斷增長(zhǎng)的進(jìn)化網(wǎng)絡(luò)：

0<λn-1(L0)≤λn-1(L1)≤…≤λn-1(LT)

由Perron矩陣Pt可得：

σ2(P0)≥σ2(P1)≥…≥σ2(PT)

(4)

其中σ2(Pt)是Pt的第二大奇異值，Pt也可以表示為Gt圖結(jié)構(gòu)[16]：

(5)

其中：δmax是Gt的最大度，Pt是半正定的。

2.2 選邊

由于代數(shù)連通度在邊集中單調(diào)遞增，通過添邊可以獲得連接良好的網(wǎng)絡(luò)拓?fù)洹１疚倪x邊方法是通過尋找拉普拉斯矩陣中零元素的位置，刪除因自身和方向性導(dǎo)致多余的邊來確定候選邊集，然后選擇任意兩個(gè)未連接的節(jié)點(diǎn)進(jìn)行添邊。

對(duì)初始圖G0添邊得到圖的拉普拉斯矩陣為：

(6)

其中：K=n(n-1)/2-m0表示可以添加到G0的候選邊集數(shù)量，它是完全圖邊的數(shù)量n(n-1)/2和初始圖G0邊的數(shù)量m0的差；wl表示是否選擇第l條候選邊的布爾變量，如果選擇候選邊l，則wl=1，否則wl=0;al表示選邊l所對(duì)應(yīng)的邊向量。

添邊使網(wǎng)絡(luò)具有更好的連通性，但容易消耗更多的網(wǎng)絡(luò)資源。因此，進(jìn)一步提出如下選邊優(yōu)化問題，達(dá)到網(wǎng)絡(luò)連通性和資源消耗的最佳平衡：

(7)

s.t.w∈C1或w∈C2

其中：P(w)：=I-(1/n)L(w);C1={w|w∈[0,1]K}，當(dāng)邊數(shù)為k時(shí)，C2={w|w∈C1,1Tw=k};c=[c1,c2,…,cK]T，cl表示已知的第l條邊成本；r>0表示衡量達(dá)到大的網(wǎng)絡(luò)連通性和消耗小的網(wǎng)絡(luò)資源的相關(guān)重要性的正則化參數(shù)。

2.3 添邊

經(jīng)過選邊后，隨時(shí)間t不斷在網(wǎng)絡(luò)上添加被選擇的邊，以生成代數(shù)連通度不斷增長(zhǎng)的進(jìn)化網(wǎng)絡(luò)，由此產(chǎn)生網(wǎng)絡(luò)添邊問題。為便于分析，假設(shè)隨著時(shí)間增加每次網(wǎng)絡(luò)最多只增加一條邊[19-21]。則圖的拉普拉斯矩陣的動(dòng)力模型[17]為：

(8)

3 FODD算法

本章將文獻(xiàn)[8]中的在線分布式對(duì)偶平均方法與文獻(xiàn)[17]中提出的增加網(wǎng)絡(luò)連通性的加邊方法相結(jié)合，提出FODD算法來解決問題(1)中的優(yōu)化問題。

3.1 FODD算法

算法1 FODD算法。

輸入：節(jié)點(diǎn)數(shù)n(?i∈V,V={1,2,…,n})，最大迭代次數(shù)T，參數(shù){α(t)}；

1)

生成初始圖G

2)

根據(jù)選邊優(yōu)化的極小問題確定候選添邊集w

3)

給出初值：xi(1)∈χ，zi(1)=0，?i∈V

4)

計(jì)算次梯度gi(t)∈?ft,i(xi(t))，?i∈V

5)

fort=1:Tdo

6)

if |wt|>0

7)

根據(jù)候選邊集wt，計(jì)算連通度增加最大的邊lt

8)

9)

10)

wt+1=wt-lt

11)

end

12)

13)

14)

15)

end for

(9)

分別表示分布式在線對(duì)偶平均算法中對(duì)偶變量和次梯度的平均值。而

(10)

表示算法中的原始變量。

4 FODD算法的收斂性分析

本章將給出增長(zhǎng)的代數(shù)連通度與Regret界之間的關(guān)系。為進(jìn)一步分析，引進(jìn)下面幾個(gè)引理。

引理1[8]設(shè)網(wǎng)絡(luò)中每個(gè)個(gè)體i的損失函數(shù)ft,i是L-lipschitz連續(xù)，即:

ft,i(x)-ft,i(y)≤L‖x-y‖2; ?x,y∈χ

則對(duì)序列xi(t)和zi(t)，Regret界滿足下面不等式：

(11)

引理2[17]對(duì)雙隨機(jī)時(shí)變矩陣φ(t,s)=PtPt-1×…×Ps(s≤t)，式(12)成立：

(12)

其中σ2(P)表示矩陣P的第二大奇異值。

此外，基于引理2，文獻(xiàn)[17]研究表明：Regret界與矩陣φ(t,s)的譜密切相關(guān)且成立：

進(jìn)一步地，對(duì)滿足式(8)的動(dòng)態(tài)網(wǎng)絡(luò)有如下結(jié)論：

引理3[17]對(duì)?i∈[n]，?t=0,1,…,T，zi(0)=0，可得Regret界：

(13)

δ∈N+

其中：β是衡量σ2(Pt)和σ2(P0)比值的變量，而δ用來刻畫所添的邊與網(wǎng)絡(luò)模型快速混合所消耗的時(shí)間。

基于引理1給出了Regret約束，為定理1的證明作了準(zhǔn)備，可得到如下關(guān)于FODD算法Regret界的重要結(jié)論:

(14)

證明 由引理1和引理3得：

則對(duì)?i∈[n]，下式成立：

定理2 在定理1的證明下，有以下等式成立：

(15)

證明 由ft(x(t))的凸性可知:

進(jìn)而可得：

則對(duì)平均Regret界有：

(16)

證明 由文獻(xiàn)8的定理2可得靜態(tài)網(wǎng)絡(luò)的Regret界：

又根據(jù)文獻(xiàn)16的定理2可知:

故可得靜態(tài)網(wǎng)絡(luò)情形下的Regret界收斂速度為：

(17)

證明 由定理1易證。

由推論1和推論2對(duì)比可知：式(17)的第二項(xiàng)刻畫了不斷增長(zhǎng)的代數(shù)連通度。當(dāng)β*=1時(shí)，在代數(shù)連通度不斷增加的網(wǎng)絡(luò)拓?fù)湎碌腞egret界(17)變成了靜態(tài)網(wǎng)絡(luò)下的Regret界(16)；同時(shí)，當(dāng)0<β*<1時(shí)，網(wǎng)絡(luò)拓?fù)涞拇鷶?shù)連通度不斷增長(zhǎng)，此時(shí)Regret界(17)的上界比(16)更小，從而與分布式在線對(duì)偶平均算法相比，所提算法1在代數(shù)連通度不斷增長(zhǎng)的網(wǎng)絡(luò)中計(jì)算更為精確。

5 數(shù)值實(shí)驗(yàn)

本章通過數(shù)值實(shí)驗(yàn)來驗(yàn)證FODD算法的性能，考慮具有5個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)，任意連接2個(gè)未連接的節(jié)點(diǎn)，生成加邊后的網(wǎng)絡(luò)拓?fù)鋱D，如圖1。

圖1 加邊后的網(wǎng)絡(luò)拓?fù)鋱D

圖2表示不使用加邊方法時(shí)所有個(gè)體的狀態(tài)軌跡圖。在ODDA算法[8]的作用下，當(dāng)?shù)螖?shù)T到達(dá)200時(shí)，在誤差允許的范圍內(nèi)，網(wǎng)絡(luò)中所有個(gè)體的狀態(tài)最終達(dá)成一致，其狀態(tài)最優(yōu)值在36的鄰域內(nèi)。圖3表示通過圖1所示的加邊方法后所有個(gè)體的狀態(tài)軌跡圖。在本文FODD算法(即加邊后的ODDA算法)的作用下，當(dāng)?shù)螖?shù)T僅達(dá)到50時(shí)，網(wǎng)絡(luò)中所有個(gè)體的狀態(tài)值已達(dá)成一致，其狀態(tài)最優(yōu)值也在36的鄰域內(nèi)。圖2和圖3對(duì)比表明：網(wǎng)絡(luò)中所有個(gè)體狀態(tài)都達(dá)到一致，但使用加邊方法后，網(wǎng)絡(luò)中個(gè)體的收斂速度更快，網(wǎng)絡(luò)中占用的時(shí)間和資源更少，成本更低，驗(yàn)證了本文所提FODD算法(即加邊后的ODDA算法)的收斂速度比ODDA算法更快。

圖2 ODDA所有個(gè)體狀態(tài)軌跡

圖3 FODD算法所有個(gè)體狀態(tài)軌跡

圖4表示ODDA算法與本文FODD算法作用下的平均損失性能對(duì)比，可以看出：本文FODD算法的全局目標(biāo)函數(shù)的平均損失性能趨于零的速度，明顯快于未加邊的ODDA算法。即在相同網(wǎng)絡(luò)環(huán)境下，使用加邊方法可使整個(gè)網(wǎng)絡(luò)以更快的收斂速率實(shí)現(xiàn)優(yōu)化目標(biāo)，解決優(yōu)化問題。

圖5表示ODDA算法與本文FODD算法作用下的平均差異性能對(duì)比，可以看出：不加邊的ODDA在在線學(xué)習(xí)中保持著較高的一致性，而較高的一致性可能會(huì)遠(yuǎn)離真實(shí)值，產(chǎn)生較大的平均差異，而FODD算法的平均差異明顯小于未加邊的ODDA算法，一致性更趨于真實(shí)值。此外，當(dāng)?shù)螖?shù)T到達(dá)100時(shí)，F(xiàn)ODD算法全局目標(biāo)函數(shù)的平均差異已經(jīng)趨近于零，明顯快于未加邊的ODDA算法平均差異的收斂速度。圖4、5進(jìn)一步表明：與ODDA算法相比，本文的FODD算法具有更好的收斂性能。

圖4 平均損失性能對(duì)比

圖5 平均差異性能對(duì)比

下面是Regret與平均Regret收斂速度在靜態(tài)網(wǎng)絡(luò)下和動(dòng)態(tài)網(wǎng)絡(luò)下的對(duì)比：

1)RT(x*,xi)：

靜態(tài)網(wǎng)絡(luò)拓?fù)涫諗克俣龋?/p>

動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涫諗克俣龋?/p>

靜態(tài)網(wǎng)絡(luò)拓?fù)涫諗克俣龋?/p>

動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涫諗克俣龋?/p>

可以看出動(dòng)態(tài)網(wǎng)絡(luò)情形下的Regret和平均Regret收斂速度明顯快于靜態(tài)網(wǎng)絡(luò)情形下的Regret和平均Regret收斂速度。

6 結(jié)語(yǔ)