朱小梅

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

引言

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

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

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

1 準備工作

1.1圖論

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

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

1.2 Bandit反饋

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

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

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

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

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

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

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

2 問題與算法

2.1問題

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

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

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

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

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

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

算法1DODA-B算法

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

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

3.fort=1，2，…，Tdo

4.fori=1，2，…，ndo

5.觀測fi，t（·），由式（2）計算梯度估計^gi，t；

8.輸出：xi，t+1；

9.end for

10.end for

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

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

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

3 收斂性分析

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

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

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

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

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

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

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

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

將（13）式右邊最后一個等式的第一項重新寫為

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

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

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

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

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

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

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

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

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

4 數(shù)值模擬計算

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

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

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

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

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

5 結(jié)論

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