自適應(yīng)Frank-Wolfe算法及其在矩陣填充上的應(yīng)用

汪麗琴，喻高航，張亮亮

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

1 低秩矩陣填充模型

(1)

式中，δ表示對(duì)Z的秩的假設(shè)置信度，通常取某個(gè)正整數(shù)。模型(1)綜合考慮了無噪音和有噪音的情況。由于秩函數(shù)是非凸且非連續(xù)的，計(jì)算模型(1)十分困難。Fazel[5]證明核范數(shù)在單元球上是秩的最緊凸松弛替代，隨后，Candès和Recht[6]提出使用矩陣核范數(shù)代替秩來解矩陣填充問題，得到模型：

(2)

2 Frank-Wolfe算法

(3)

給出Frank-Wolfe算法。

算法1 用于解決問題(3)的標(biāo)準(zhǔn)Frank-Wolfe算法輸入:x0∈,最大迭代步數(shù)K 當(dāng)k=1,2,…,K時(shí),(1)計(jì)算sk-1=argmins∈(2)搜索方向dfw=sk-1-xk-1(3)更新xk=xk-1+γdfw,其中γ∈[0,1]輸出:xK

針對(duì)步驟3中步長的選取，本文使用精確線搜索策略，即γ=argminγ∈[0,1]f(xk+γdfw)。

由于核范數(shù)的對(duì)偶范數(shù)是算子范數(shù)，即‖Y‖=max‖X‖*≤1〈X,Y〉，因此最優(yōu)化問題

minX〈X,Y〉 s.t.‖X‖*≤1

2.1 CGS算法

Lan等[8]使用Nesterov加速方法，提出FW算法的改進(jìn)算法CGS。

算法2 FW算法的變體CGS算法輸入:x0∈,最大迭代步數(shù)K 取βk∈R++,γk∈[0,1],和ηk∈R+,k=1,2,…,令y0=x0 當(dāng)k=1,2,…,K時(shí),(1)計(jì)算zk=(1-γk)yk-1+γkxk-1(2)計(jì)算xk=CndG f'(zk),xk-1,βk,ηk (3)更新yk=(1-γk)yk-1+γkxk輸出:yK 子程序xk=CndG f'(zk),xk-1,βk,ηk 的步驟如下:(1)初始化g=f'(zk),u=xk-1,β=βk,η=ηk(2)令u1=u和t=1(3)令vt為子問題Vg,u,β(ut)maxx∈的最優(yōu)解(4)如果Vg,u,β(ut)≤η,則令xk=ut,并跳轉(zhuǎn)到步驟7,否則,進(jìn)入步驟5(5)令ut+1=(1-αt)ut+αtυt,其中αt=min1,<β(u-ut)-g,υt-ut>β‖υt-ut‖2 (6)令t=t+1,并跳轉(zhuǎn)到步驟3(7)返回xk

2.2 In-Face步驟

對(duì)于矩陣填充問題，F(xiàn)W算法的一個(gè)不足之處在于其中間解決方案的秩通常穩(wěn)定增長，并在終止時(shí)產(chǎn)生一個(gè)高秩的解決方案，這對(duì)于大規(guī)模問題[13]可能在時(shí)間和空間成本上非常昂貴。

隨后，F(xiàn)reund等[9]提出加In-Face步驟的拓展FW算法IF-(0,∞)，In-Face步驟是遠(yuǎn)離步驟的推廣，遠(yuǎn)離步驟的具體細(xì)節(jié)見文獻(xiàn)[14-15]。In-Face步驟沿著包含當(dāng)前迭代的最小面選擇最佳下降方向，通過沿著最小面移動(dòng)到可行域的邊界以達(dá)到低維面。該算法保持了低秩結(jié)構(gòu)，且不會(huì)影響收斂。對(duì)于問題(2)，如文獻(xiàn)[9]所述，包含點(diǎn)Xk核范數(shù)球NN(0,δ)的最小面由下列集合給出：

其中，Xk具有秩為r的薄SVDUΣVT，M為滿足tr(M)=δ的半正定矩陣。薄SVD表示具有嚴(yán)格正奇異值的SVD，即，如果A=UΣVT是薄SVD且rank(A)=r，則U∈Rm×r，Σ∈Rr×r，V∈Rn×r。

本文考慮文獻(xiàn)[9]中描述的由遠(yuǎn)離策略得到的In-Face步驟，它使用的方向如下：

3 自適應(yīng)FW算法及其收斂性分析

為了提高FW算法的收斂率并降低迭代過程中的計(jì)算成本，本文提出嵌入秩下降步驟的矩陣填充問題的IF-CGS算法。

算法3 IF-CGS算法輸入:初始迭代點(diǎn)x0∈,超參數(shù)c>0,最大迭代步數(shù)K 取βk∈R++,γk∈[0,1],和ηk∈R+,k=1,2,…,令y0=x0 當(dāng)k=1,2,…,K時(shí),(1)當(dāng)yk-1在NN(0,δ-c)內(nèi)部時(shí),計(jì)算CGS:zk=(1-γk)yk-1+γkxk-1xk=CndG f'(zk),xk-1,βk,ηk yk=(1-γk)yk-1+γkxk(2)當(dāng)yk-1在NN(0,δ-c)外部時(shí),計(jì)算遠(yuǎn)離方向滿足yk-1+dk∈Aff D(yk-1) 和?f(yk-1)Tdk<0如果dk不存在,則跳轉(zhuǎn)到步驟1,計(jì)算CGS,否則,進(jìn)入步驟3(3)αstopk=argmaxα{α︰yk-1+αdk∈D(yk-1)}yAk-1yk-1+αstopkdk(4)如果f(yAk-1)≤f(yk-1),則進(jìn)入步驟5,否則,跳轉(zhuǎn)到步驟1(5)更新yk=yAk-1輸出:yK

步驟1進(jìn)行CGS計(jì)算，當(dāng)秩增長到一定程度時(shí)執(zhí)行步驟2，計(jì)算In-Face步驟下的迭代點(diǎn)更新，并在In-Face步驟和CGS步驟進(jìn)行選擇，若In-Face步驟下的目標(biāo)值小于上一次迭代的目標(biāo)值，則執(zhí)行In-Face步驟，否則執(zhí)行CGS步驟。在加In-Face步驟的CGS算法的框架下，接受任何不增加目標(biāo)函數(shù)值的降秩步驟，允許算法維持較低秩的SVD，并且允許算法跳過不必要的CGS計(jì)算。

對(duì){βk}，{γk}和{ηk}提供一種參數(shù)設(shè)置，得到其收斂性結(jié)果。

定理1如果IF-CGS算法中的參數(shù){βk}，{γk}和{ηk}設(shè)置如下：

證明當(dāng)下一個(gè)迭代點(diǎn)由步驟1選取，則有

4 數(shù)值實(shí)驗(yàn)與分析

分別使用FW，IF-(0,∞)，CGS，IF-CGS算法進(jìn)行數(shù)值實(shí)驗(yàn)，從數(shù)據(jù)恢復(fù)精度和運(yùn)行時(shí)間進(jìn)行性能分析。

4.1 合成數(shù)據(jù)

表1 中大型規(guī)模合成數(shù)據(jù)的參數(shù)設(shè)置

抽取觀察數(shù)據(jù)的50%作為訓(xùn)練集，剩下的50%作測試集，例1運(yùn)行150 s，例2 運(yùn)行250 s，例3 運(yùn)行500 s，超參數(shù)c設(shè)置為0.5，使用目標(biāo)值和測試均方根誤差(Root Mean Squared Error，RMSE)作為評(píng)估標(biāo)準(zhǔn)，用于衡量預(yù)測值與真實(shí)值之間的偏差，

實(shí)驗(yàn)結(jié)果如圖1和圖2所示。

圖1 不同算法目標(biāo)值隨運(yùn)行時(shí)間變化的情況

圖2 不同算法測試RMSE隨運(yùn)行時(shí)間變化的情況

從圖1和圖2可以看出，IF-CGS算法降低目標(biāo)值和測試RMSE的速度比其他方法快，解的精度也高于其他方法。在初始迭代階段，IF-CGS算法迭代點(diǎn)在NN(0,δ-c)內(nèi)部執(zhí)行CGS計(jì)算，所以IF-CGS算法與CGS算法基本是同步的，當(dāng)IF-CGS算法迭代點(diǎn)達(dá)到NN(0,δ-c)外部時(shí)，開始在In-Face步驟與CGS步驟中進(jìn)行選擇，執(zhí)行In-Face步驟能夠減少迭代成本，所以，相比CGS算法，IF-CGS算法的收斂速度更快。

4.2 Movielens-10M數(shù)據(jù)集

表3 Movielens-10M數(shù)據(jù)集實(shí)驗(yàn)中，不同算法的性能指標(biāo)

5 結(jié)束語

Frank-Wolfe算法的變體CGS算法解矩陣填充問題的一個(gè)不足之處在于其中間解的秩通常會(huì)穩(wěn)定增長，并在終止時(shí)達(dá)到高秩的解。本文針對(duì)這個(gè)不足，嵌入秩下降步驟，提出求解低秩矩陣填充問題的IF-CGS算法。所提算法在保持線性收斂的同時(shí)減少迭代成本，有效解決了大規(guī)模的低秩矩陣填充問題。但是，In-Face步驟確定最大可行步長時(shí)需要進(jìn)行多次SVD更新，導(dǎo)致昂貴的中間迭代，針對(duì)秩下降步驟的選取問題展開進(jìn)一步研究是有意義的。