基于Bandit反饋的分布式在線對(duì)偶平均算法

朱小梅

（重慶師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，重慶 401331）

引言

分布式優(yōu)化理論及應(yīng)用是目前系統(tǒng)和控制科學(xué)的重要研究方向之一，在分布式網(wǎng)絡(luò)中，節(jié)點(diǎn)之間通過相互協(xié)調(diào)合作，可以有效解決如智能電網(wǎng)、傳感器網(wǎng)絡(luò)等大規(guī)?，F(xiàn)實(shí)問題，并能提高數(shù)據(jù)傳遞效率，增強(qiáng)網(wǎng)絡(luò)魯棒性［1-2］。但在實(shí)際應(yīng)用中，分布式網(wǎng)絡(luò)一般都運(yùn)行在動(dòng)態(tài)環(huán)境下，分布式優(yōu)化算法不能實(shí)時(shí)處理網(wǎng)絡(luò)數(shù)據(jù)流，而在線學(xué)習(xí)能夠根據(jù)數(shù)據(jù)的變化動(dòng)態(tài)地調(diào)整模型［3-4］，進(jìn)而更高效地完成對(duì)大量實(shí)時(shí)數(shù)據(jù)的處理，并且分布式在線優(yōu)化算法已經(jīng)在機(jī)器學(xué)習(xí)、在線推薦系統(tǒng)和資源分配等方面有著重要的應(yīng)用價(jià)值。

分布式優(yōu)化算法已成為有效求解大規(guī)模優(yōu)化問題的熱點(diǎn)算法之一?，F(xiàn)有的分布式優(yōu)化算法主要分為三類：第一類是文獻(xiàn)［5］最早提出的一種分布式次梯度算法來求解無約束的分布式優(yōu)化問題，第二類是文獻(xiàn)［6］提出的一種分布式對(duì)偶平均算法，給出算法的收斂性，并得出了收斂率依賴于網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu)的結(jié)論，第三類是文獻(xiàn)［7］基于拉格朗日對(duì)偶方法提出的分布式原始對(duì)偶算法來求解一類帶約束的優(yōu)化問題。雖然文獻(xiàn)［6］提出的分布式對(duì)偶平均算法已經(jīng)成為可以解決大規(guī)模問題的熱點(diǎn)算法，但由于環(huán)境的不確定性以及目標(biāo)函數(shù)具有時(shí)變性和不確定性，導(dǎo)致分布式優(yōu)化算法并不能對(duì)網(wǎng)絡(luò)中產(chǎn)生的大量分布式數(shù)據(jù)流進(jìn)行實(shí)時(shí)處理，這造成網(wǎng)絡(luò)資源和時(shí)間的浪費(fèi)。針對(duì)上面的情形，一種有效的解決方法是在線學(xué)習(xí)，因?yàn)樵诰€學(xué)習(xí)可以利用時(shí)變的目標(biāo)函數(shù)來表示多個(gè)體網(wǎng)絡(luò)系統(tǒng)的不確定性，同時(shí)還可以方便地對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的動(dòng)態(tài)數(shù)據(jù)流進(jìn)行實(shí)時(shí)處理。最近，對(duì)于成本和網(wǎng)絡(luò)結(jié)構(gòu)不確定的凸優(yōu)化問題，文獻(xiàn)［8］提出了分布式加權(quán)對(duì)偶平均算法。李德權(quán)等人提出的一種快速的分布式在線對(duì)偶平均算法，即通過對(duì)底層網(wǎng)絡(luò)依次添邊，提高了分布式在線優(yōu)化算法的收斂速率［9］。為更好的解決多智能體的在線優(yōu)化問題，文獻(xiàn)［10］設(shè)計(jì)了Nesterov對(duì)偶平均算法的兩個(gè)去中心化的隨機(jī)變體，即SODA-C和SODA-PS。文獻(xiàn)［11］考慮了正則化隨機(jī)學(xué)習(xí)和在線優(yōu)化問題，開發(fā)了一種正則化的對(duì)偶平均算法，可以在在線環(huán)境中更有效的利用正則化結(jié)構(gòu)。這充分說明分布式在線對(duì)偶平均方法可以有效的解決分布式在線優(yōu)化問題。

現(xiàn)有的分布式在線對(duì)偶平均算法都是基于目標(biāo)函數(shù)的梯度可以有效計(jì)算的情況，但在現(xiàn)實(shí)生活中，梯度信息一般獲取困難。由此看來，現(xiàn)有的分布式在線對(duì)偶平均算法面臨著一個(gè)梯度計(jì)算瓶頸。因此，設(shè)計(jì)出一種無梯度計(jì)算方法是十分有價(jià)值的。受文獻(xiàn)［12］的啟發(fā)，本文提出了一種基于Bandit反饋的分布式在線對(duì)偶平均算法。不同于分布式在線對(duì)偶平均算法，本文提出的算法只需要計(jì)算損失函數(shù)的值，即主要是利用損失函數(shù)在一些隨機(jī)點(diǎn)的函數(shù)值信息去逼近損失函數(shù)原來的梯度信息，從而避免了直接計(jì)算損失函數(shù)的梯度。

1 準(zhǔn)備工作

1.1圖論

設(shè)G=（v，ε）表示一個(gè)無向圖，其中v=｛1，2，…，n｝表示由n個(gè)節(jié)點(diǎn)構(gòu)成的集合，ε?v×v表示相鄰節(jié)點(diǎn)構(gòu)成的邊集，邊（i，j）∈ε表示節(jié)點(diǎn)i可以從節(jié)點(diǎn)j接收數(shù)據(jù)信息。并記Ni=｛j|（i，j）∈ε｝表示節(jié)點(diǎn)i所有鄰居構(gòu)成的集合。非負(fù)矩陣A為圖G=（v，ε）的權(quán)重矩陣，滿足［A］ij＞0，當(dāng)且僅當(dāng) （i，j）∈ ε，否則［A］ij=0。

假設(shè)1［2］設(shè)圖G=（v，ε）是連通的，非負(fù)矩陣A∈Rn×n為圖G=（v，ε）的權(quán)重矩陣，設(shè)權(quán)重矩陣是雙隨機(jī)的，即

1.2 Bandit反饋

在已有的分布式在線對(duì)偶平均算法的研究中，節(jié)點(diǎn)之間都是通過梯度信息進(jìn)行通信反饋的，但在實(shí)際應(yīng)用場(chǎng)景中，更一般的情況是不能夠直接得到梯度信息的，所以本文提出了一種新的梯度信息反饋的改進(jìn)方法，即Bandit反饋，該方法只顯示當(dāng)前時(shí)刻的損失函數(shù)的值，而不是顯示整個(gè)函數(shù)的值。在Bandit設(shè)置中，節(jié)點(diǎn)只能訪問一些點(diǎn)上的代價(jià)函數(shù)上的值并且不知道函數(shù)的梯度。由于大多數(shù)優(yōu)化算法需要相關(guān)函數(shù)的梯度，因此，下面給出根據(jù)函數(shù)在有限點(diǎn)上的函數(shù)值來估計(jì)梯度的一些結(jié)果。

給定一個(gè)函數(shù)fi，t（x）：Rm→R，對(duì)?x∈（1-ξ）χ，χ?Rm及某個(gè)很小的數(shù)δ＞0，定義fi，t（x）的一個(gè)光滑化近似函數(shù)，如下［8］

為梯度估計(jì)，其中u是滿足均勻分布的隨機(jī)向量。

引理 1［13］（I）即使fi，t（x）不可微，均勻光滑化函數(shù)^f i，t（x）在 （1-ξ）χ是可微的，對(duì) ?x∈ （1-ξ）χ有

（II）若fi，t（x）在 χ上是凸的，則^fi，t（x）在 （1-ξ）χ上也是凸的，且對(duì) ?x∈ （1-ξ）χ，fi，t（x）≤^fi，t（x）。

（III）若fi，t（x）在 χ上是 L-Lipschitz連續(xù)的，則）在 （1-ξ）χ上也是 L-Lipschitz連續(xù)的，且對(duì) ?x∈ （1-ξ）χ有）≤Lδ。

（IV）若fi，t（x）在 χ上是 L-Lipschitz連續(xù)的，則對(duì)?x∈ （1-ξ）χ有mL。

2 問題與算法

2.1問題

考慮圖G=（v，ε）上的分布式在線凸優(yōu)化問題，如下

本文的最終目標(biāo)是得到一系列的決策點(diǎn)｛xi，t｝使得對(duì)于每一個(gè)節(jié)點(diǎn)i∈v與最佳的固定決策點(diǎn)x*的Regret界［14］。

假設(shè)2（I）對(duì)任意的i∈v和任意的t∈｛1，2，…，T｝，fi，t（x）在 χ是 L-Lipschitz連續(xù)的，即對(duì)任意的x∈ χ和y∈ χ都有）-fi，t（y）Lx-y。

（II）存在正常數(shù)r和R使得rB?χ?RB，其中B=｛x∈x≤1｝。

由假設(shè) 2知，fi，t（·）的次梯度 ▽fi，t（·）在上是一致有界的，即 ▽fi，t≤L。

2.2 基于Bandit反饋的分布式在線對(duì)偶平均算法

算法1DODA-B算法

1.輸入：最大迭代輪數(shù)T，步長(zhǎng)αt，收縮系數(shù)ξ，光滑化參數(shù)δ和近端函數(shù)ψ（·）；

2.初始化：xi，1∈ （1-ξ）χ，?i∈v，zi，1=0；

3.fort=1，2，…，Tdo

4.fori=1，2，…，ndo

5.觀測(cè)fi，t（·），由式（2）計(jì)算梯度估計(jì)^gi，t；

8.輸出：xi，t+1；

9.end for

10.end for

注記：（I）算法1給出了所提算法的偽代碼，每個(gè)節(jié)點(diǎn)i都有如下兩個(gè)局部序列：局部原始決策變量序列｛xi，t｝?χ，局部對(duì)偶變量序列 ｛zi，t｝?（1-ξ）χ，通過算法1的步6和步7更新。

（II）算法1中的步7中的 Πψ（1-ξ）χ（·）是在 （1-ξ）χ上的正則投影，這個(gè)投影可以表示為

其中ψ（x）是一個(gè)近端函數(shù)。

3 收斂性分析

這部分提出一個(gè)帶兩點(diǎn)梯度估計(jì)的在線分布式對(duì)偶平均算法來解決所考慮的優(yōu)化問題，然后給出Regret界。下面主要陳述對(duì)算法1的主要結(jié)果。下面的定理描述基于一些特別選擇的步長(zhǎng)，壓縮系數(shù)和光滑化參數(shù)等等。首先給出幾個(gè)重要的引理：

引理2［13］對(duì)任意的常數(shù)k∈ ［0，1），且s≤T∈R+，有

引理3［15］設(shè)假設(shè)1成立，則存在常數(shù) λ∈ （0，1）及C＞0，對(duì) ?i，j∈v，?t≥1有

引理4設(shè)假設(shè)1-2成立，對(duì)任意的i∈v和t∈R+，｛zi，t｝是由算法 1產(chǎn)生的序列，則

再對(duì)式（10）兩邊取對(duì)偶范數(shù)可得

第二個(gè)不等式由引理1的（IV）和引理3得到。

引理5設(shè)假設(shè)1-2成立，｛xi，t｝是由算法1產(chǎn)生的序列，則對(duì)任意的i∈v，x*∈（1-ξ）χ有

證明根據(jù)fi，t（x）的L-Lipschitz連續(xù)性，對(duì)x*∈（1-ξ）χ和由 φ（t）=，αt）定義的序列 ｛φ（t）｝，有

將（13）式右邊最后一個(gè)等式的第一項(xiàng)重新寫為

根據(jù)引理1的（III）可知

從而在式（19）兩邊對(duì)t=1，2，…，T求和得

于是將式（23）代入式（18）可得

由式（17）和式（24）可得

于是將式（26）代入式（13）可得

將引理4代入上式即可得結(jié)論，式（12）得證。

定理1設(shè)假設(shè)1-2成立，對(duì)任意的T∈ R+，｛x｝是由算法 1產(chǎn)生的序列，取 α=，δ，ξ=i，tt，ψ（x）≤D2，有

從而結(jié)論得以證明。

注記：定理1的結(jié)果表明，算法1的收斂速度是O（Tmax｛k，1-k｝），當(dāng)k=時(shí)，算法1的收斂速度與已往的分布式在線對(duì)偶平均算法的收斂速度同階。通過對(duì)比，本文所提出的算法1只需要計(jì)算損失函數(shù)的函數(shù)值，避免了花費(fèi)較大的梯度計(jì)算，從而節(jié)省了計(jì)算成本，并且算法適用范圍更加廣泛。

4 數(shù)值模擬計(jì)算

在本節(jié)中，考慮一個(gè)分布式在線傳感器問題，對(duì)于每個(gè)節(jié)點(diǎn)i∈v都有自己的測(cè)量方程qi，t=Uix+ei，t，其中qi，t∈Rn，Ui∈Rn×m是測(cè)量數(shù)據(jù)，x∈Rm是未知的，ei，t∈Rn是未知的噪音，問題最終的目標(biāo)在于估計(jì)x，使用所提出的DODA-B算法去解決如下問題［16］

考慮一個(gè)節(jié)點(diǎn)n的隨機(jī)網(wǎng)絡(luò)，對(duì)于任意的節(jié)點(diǎn)i∈v。假設(shè) χ=Rm，實(shí)矩陣Ui∈ Rn×m且qi，t∈ Rn在（0，2）中產(chǎn)生，設(shè)ui，t是在歐式單位球S上隨機(jī)產(chǎn)生，且服從均勻分布。取T=500，R=5，，λ=0.5，步長(zhǎng)α=。取光滑參數(shù)δ，壓縮系數(shù)ξ=?？紤]平t均Regret界，將本文的DODA-B算法與現(xiàn)有的DODA算法進(jìn)行對(duì)比。

圖1和圖2表示節(jié)點(diǎn)總數(shù)n分別為50和100的平均Regret界的演化圖。根據(jù)定理1的理論結(jié)果分析，可以從圖1觀察到，當(dāng)?shù)鷷r(shí)間T達(dá)到100時(shí)，兩種算法的平均Regret界均會(huì)收斂到0，并且DODA-B算法的收斂率和DODA算法收斂率同階，因?yàn)樗鼈儍H相差一個(gè)由函數(shù)值信息近似梯度信息產(chǎn)生的光滑化誤差項(xiàng)。另外，從圖2可以觀察到，當(dāng)節(jié)點(diǎn)n=100時(shí)，也可以得到同樣的結(jié)果。

圖1 DODA-B與DODA算法平均化Regret界的比較（n=50）

圖2 DODA-B與DODA算法平均化Regret界的比較（n=100）

5 結(jié)論

針對(duì)分布式在線優(yōu)化中一類損失函數(shù)梯度難以獲取的問題，通過Bandit設(shè)置，本文提出了一種基于Bandit反饋的分布式在線對(duì)偶平均（DODA-B）算法，將DODA算法改進(jìn)成無梯度的DODA-B算法。理論分析表明，DODA-B算法具有O(Tmax{k，1-k})的Regret界。數(shù)值模擬計(jì)算結(jié)果進(jìn)一步表明兩種算法的收斂率同階，并且DODA-B算法僅僅用到計(jì)算量較小的函數(shù)值信息，這要比DODA算法更節(jié)約成本。未來可以將所提的DODA-B算法推廣到有向網(wǎng)絡(luò)中，或推廣到時(shí)變網(wǎng)絡(luò)中。