基于Bandit反饋的在線分布式鏡面下降算法

朱小梅，李覺友

1. 重慶師范大學 數學科學學院，重慶 401331； 2. 重慶兩江新區博雅小學校，重慶 401121

隨著數據規模的爆炸式增長，集中式優化算法因受限于單機的計算瓶頸而難以求解大規模優化問題．而多機協作的分布式機制可以大大降低單機的計算負擔．同時，在分布式網絡中，節點之間通過相互協作，可以有效解決諸如智能電網、傳感器網絡等大規模問題，并能提高數據傳遞效率，增強網絡魯棒性[1]．但在應用中，分布式網絡通常是動態變化的，而在線學習具有實時更新模型的特性，能夠根據數據的變化動態地調整模型[2]，進而可高效地完成對大量實時數據的處理，已經在機器學習、在線推薦系統和資源分配等方面體現出了重要的應用價值。

然而，上述大多數算法都需要計算梯度．但在許多實際應用場景中，梯度信息往往難以獲取．因此，設計出一種免梯度計算的有效算法顯得非常有意義．受文獻[9]的啟發，本文提出了一種基于Bandit反饋的免梯度在線分布式鏡面下降算法．不同于ODMD算法，我們提出的算法只需要簡單計算函數值，主要是利用損失函數在一些隨機點的函數值信息去逼近損失函數的梯度，從而避免了直接計算損失函數的梯度．我們設計的算法主要有兩個優點：① 能有效解決梯度信息難以獲取的困難； ② 能有效處理約束集較復雜(如單純形約束集)的優化問題。

1 準備工作

1.1 圖論

1.2 Bregman散度

定義2[8](Bregman散度) 設h(·)是1-強凸函數，定義如下關于函數h的Bregman散度Dh(·，·)

Dh(x，y)=h(x)-h(y)-〈x-y，h(y)〉

Euclidean距離和Kullback-Leiber(KL)散度為兩種常用的Bregman散度。

結合定義1和2可以得到有關Bregman散度的一個重要性質[8]

(1)

(2)

1.3 Bandit反饋

現有在線分布式算法大多是基于完全信息設計的，即節點可以獲得其決策空間中任何一個位置的梯度信息．而在許多應用場景中，節點一般獲得的是帶噪音的、有缺漏或有限的信息反饋，稱這種不能直接獲得損失函數梯度的情形為Bandit反饋機制[9]，即節點只能訪問自身損失函數在一些隨機點上的函數值，但并不知道其梯度信息．眾所周知，大多數優化算法的設計是基于損失函數的梯度設計的，而在Bandit反饋中，面臨著梯度信息不可用的問題．為此，我們設計了僅利用損失函數值來逼近梯度的Bandit算法．下面給出根據函數在隨機點上的函數值來近似估計其梯度的一些結果。

(3)

其中U(B)表示服從單位球B={x∈Rm|‖x‖≤1}的均勻分布，E[·]表示期望。

引理2[9]設S={x∈Rm|‖x‖=1}表示Rm中的單位球面，有以下結果：

2 問題與算法

2.1 問題

考慮圖G=(V，E)上的在線分布式凸優化問題如下

(4)

(5)

假設2對?i∈V和?t∈{1，…，T}，fi，t(·)在χ上是G-Lipschitz連續的，即對?x，y∈χ，有|fi，t(x)-fi，t(y)|≤G‖x-y‖。

由假設2知fi，t(·)的次梯度fi，t(·)在χ上是一致有界的，即‖fi，t‖≤G。

2.2 基于Bandit反饋的在線分布式鏡面下降算法

由光滑化函數的定義(3)，我們給出問題(4)中節點i在時刻t的損失函數fi，t的一個光滑化函數

(6)

(7)

在時刻t，只有xi，t被確定后才可以獲得fi，t，進而才能估計fi，t(xi，t±ξui，t)，其中ui，t～U(S)。

(8)

(9)

算法1ODMD-B算法

1) 輸入：最大迭代次數T，步長ηt，收縮系數α，光滑化參數ξ；

2) 初始化：xi，1∈(1-α)χ，yi，1=xi，1，?i∈V；

3) fort=1，…，Tdo

4) fori=1，…，Ndo

5) 利用決策xi，t，觀測局部即時損失函數fi，t(x)；

8) end for

9) end for

3 收斂性分析

這一部分主要論述本文提出的ODMD-B算法在局部損失函數為凸時的Regret界．分析思路如下：首先，估計出各節點的網絡化誤差，見引理4； 然后，引入一個輔助函數并給出一個重要的引理，見引理5； 最后，根據已建立的結果得出主要結果。

引理3[8]如果假設1和2均成立，且Dh(x，y)關于第二個變量y是凸的，則

(10)

引理4如果假設1和2均成立，序列{xi，t}是由算法1迭代產生的，則對任意的i∈V和t≥1，有

(11)

證根據算法1的步7)和引理1，有

由(1)式可得

(12)

(13)

由(13)式和假設1可得

(14)

于是由(13)式和(14)式有

利用雙隨機矩陣A的性質[8]，即矩陣A滿足

(15)

這樣有

(16)

為了證明定理1的結果，對任意的x∈χ，作如下輔助函數

(17)

引理5如果假設1和2均成立，序列{xi，t}是由算法1迭代產生的，則

(18)

(19)

接下來對(19)式最后一個不等式右邊的三項分別進行估計．對第一項，根據算法1的步8和引理4，有

(20)

對第二項，由(9)式有

(21)

其中(21)式的最后一個不等式由均值不等式得到．對第三項，根據引理1和(1)式，有

(22)

最后，將(20)-(22)式代入(19)式，且在(19)式中對t=1，…，T求和，然后再對i=1，…，N求和，最后利用引理3可證得(18)式成立。

(23)

其中

證根據Regret界的定義(5)式及ft的G-Lipschitz連續性，有

(24)

在(24)式中，利用引理4，可得

(25)

在(25)式中，先對t=1，…，T求和，然后再對i=1，…，N求和，可得

(26)

(27)

從而

(28)

(29)

從而由(29)式可得

(30)

根據(28)式和(30)式，由(26)式右邊的項得

(31)

由Fi，t(·)的定義，有

(32)

(33)

對(26)式取期望，結合(31)式和(33)式，再根據引理5，有

(34)

4 數值實驗

為了說明算法的有效性，考慮一個不對股票市場進行任何統計假設的投資組合選擇模型，被稱為“通用投資組合選擇”模型，它在在線學習中受到了特別的關注．下面給出一個投資組合選擇模型[10]

(35)

其中q=1，…，m．對于ODMD-B算法的性能度量，考慮平均Regret界．另外，將本文提出的ODMD-B算法與文獻[8]提出的ODMD算法進行數值對比。

首先，考慮不同的問題維數對ODMD-B算法性能的影響．圖1a和圖1b分別表示N=10，m=50和N=10，m=100的平均Regret界隨著迭代次數變化的演化圖．從圖1a和圖1b可以看出，本文提出的ODMD-B算法與文獻[8]提出的ODMD算法都可以收斂．但ODMD-B算法的早期收斂速度稍微慢于ODMD算法，這是因為ODMD-B算法只使用了函數值信息，而ODMD算法是直接使用了梯度信息．但隨著迭代次數增大，ODMD-B算法的平均Regret界大致接近ODMD算法的平均Regret界．另外，對比圖1a和圖1b中的ODMD-B算法，當T=700時，m=50和m=100平均Regret界分別為0.020 52和0.027 39，僅相差0.007左右．這表明問題維數對所提算法性能的影響并不大，這主要是因為此問題在迭代過程中能夠求得顯示解。

然后，考慮不同的節點個數對ODMD-B算法性能的影響．圖1c和圖1d分別表示N=50，m=100和N=100，m=100的平均Regret界隨著迭代次數變化的演化圖．圖1c和圖1d進一步表明兩種算法的平均Regret界隨著迭代次數的增加而趨于一致．另外，對比圖1c和圖1d可以發現，隨著節點個數的增加，兩種算法的平均Regret界隨之增加．相比ODMD算法，本文所提ODMD-B算法僅僅使用了函數值信息。

圖1 ODMD-B算法與ODMD算法平均Regret界的比較

5 結論