稀疏正則非凸優(yōu)化問題之全局收斂分析

儲敏

(武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 湖北武漢 430072)

1 引言

近年來, 隨著數(shù)據(jù)量的加大和計(jì)算機(jī)性能的急速提升, 極大地促進(jìn)了以機(jī)器學(xué)習(xí)為主導(dǎo)的人工智能技術(shù)研究.然而, 當(dāng)前應(yīng)用數(shù)學(xué)家所關(guān)心的是如何把實(shí)際的問題進(jìn)行數(shù)學(xué)上的刻畫, 并且求出其顯示解或者數(shù)值解.以目前最流行的深度神經(jīng)網(wǎng)絡(luò)為例, 在訓(xùn)練集上, 我們可以把它歸納為一個(gè)非凸非光滑的優(yōu)化問題[1].同樣地, 在矩陣分解以及張量填充中, 其目標(biāo)函數(shù)也是非凸的.另一方面, 由于大數(shù)據(jù)的高維特性(觀測樣本量個(gè)數(shù)小于人們關(guān)心的屬性的維數(shù)), 使得很多傳統(tǒng)的數(shù)學(xué)工具、統(tǒng)計(jì)方法不再有效, 對所觀測到的大數(shù)據(jù)本身作更好的先驗(yàn)假設(shè), 則是有效處理大數(shù)據(jù)的關(guān)鍵.幸運(yùn)的是, 大多數(shù)的實(shí)際問題中造成某種結(jié)果的影響因素有可能有很多, 但是真正有顯著影響的因素實(shí)際上很少, 只需要很少的某些屬性就能較好的滿足于表征我們所關(guān)心的這些事物, 反映到數(shù)學(xué)思想方法上, 稀疏性這個(gè)合理的先驗(yàn)假設(shè)給處理大數(shù)據(jù)問題打開了一扇窗.例如, 在圖像處理領(lǐng)域, 近些年的發(fā)展很大程度上得益于提出:“自然圖像可以在某些變換下稀疏表示”這樣一個(gè)合理的假設(shè)[2].又例如, 在日常生活中,一個(gè)人的健康指標(biāo)通常只采用由少數(shù)的生物指標(biāo)來反映.由此, 尋求稀疏解不僅符合問題本身的需求同時(shí)也有益于節(jié)省存儲成本.

考慮如下非凸組合優(yōu)化問題

其中X是歐式空間Rd上的凸的緊集,f:X→R是一個(gè)光滑非凸函數(shù),r:X→R是一個(gè)凸的但非光滑的正則化項(xiàng).若: 稀疏l1正則化[3], 問題(1.1) 涵蓋了一系列非凸組合優(yōu)化問題.

例1給定一個(gè)n維序列(a1,b1),··· ,(an,bn), 其中ai∈Rd,bi∈R, 若令f(x)=其中c是偏差,?是Sigmoid 函數(shù), 即那么問題(1.1) 即化為感知機(jī)問題（非凸）; 若令在函數(shù)f和正則化項(xiàng)r間起到了平衡的作用, 這時(shí)問題(1.1) 即為著名的Lasso[3].

2 預(yù)備知識

對于實(shí)值函數(shù)f:X→R∪{+∞},f的定義域domf:=x→X:f(x)<+∞;f為正常函數(shù), 即為閉函數(shù), 即f是下半連續(xù)的.

定義2.1[4]給定一個(gè)正常函數(shù)f:X→R∪{+∞}, 對每個(gè)x∈dom(f),f在x處的Frchet 次微分記為f(x), 其定義為

定義2.2[5]給定一個(gè)正常函數(shù)f:X→R∪{+∞}, 對每個(gè)x∈dom(f),f在x處的次微分記為?f(x), 其定義為

定理2.1[5]令J(x,z) :=H(x,z)+f1(x)+f2(x), 其中f1:X→R∪{+∞} 是一個(gè)正常的下半連續(xù)的凸函數(shù),f2:X→R∪{+∞} 是一個(gè)正常的連續(xù)可微函數(shù),H也是連續(xù)可微函數(shù).那么?(x,z)∈X×X, 有

定義2.3[5]f的臨界點(diǎn){x|0 ∈?f(x)}, 滿足的必要非充分條件.

定義2.4[6](KL 函數(shù)) (a) 設(shè)若存在的某個(gè)鄰域U, 連續(xù)凹函數(shù)?:[0,ζ)→R+滿足

(i)?(0)=0;

(ii)?在(0,ζ) 上是一階連續(xù)可導(dǎo)的;

(iii) 任意z∈(0,ζ),(z)>0;

(iv) 任意x∈U∩[f(x)

則稱f:Rn→R∪+∞在x?滿足Kurdyka-Lojasiewicz 性質(zhì)[6].

(b) 在dom?f內(nèi)每個(gè)點(diǎn)都滿足Kurdyka-Lojasiewicz 不等式的正常下半連續(xù)函數(shù), 稱為KL 函數(shù).

3 模型及收斂性分析

首先, 縱觀全文對函數(shù)f和g做如下假設(shè).

(i)f是Lipschitz 連續(xù)可微函數(shù), Lipschitz 常數(shù)L> 0, 即?x,y∈X都有

(ii)f和g是非負(fù)、正常、強(qiáng)制、半代數(shù)函數(shù).

基于以上假設(shè), 給出如下近端梯度算法[7]

表1: 近端梯度算法

在這個(gè)部分, 分析算法1 的收斂性.有必要先對算法1 中的序列{xk} 的特性進(jìn)行分析.

引理3.1假設(shè)(i) 成立且算法1 產(chǎn)生的序列{xk} 滿足

(ii)

證(i) 首先定義如下函數(shù)

進(jìn)行化簡后可得到

利用f的Lipschitz 連續(xù)可微性, 得到

從而(i) 得證.

對于(ii), 將上(3.1) 式兩邊同時(shí)進(jìn)行求和, 得到

從而(ii) 得證.

對于(iii), 由?F(x) 的定義, 令

另一方面, 由算法1 的一階優(yōu)化條件, 得到

化簡得到

由(ii) 中的不等式(3.2), (iii) 得證.

為了證明算法1 的收斂性, 還需要如下定理.

定理3.1[8?10]假設(shè)(i) 成立且是算法1 產(chǎn)生的序列, 則{xk}收斂到F的臨界點(diǎn).

證為了證明算法1 的收斂性, 首先要證明以下三個(gè)條件.

(H1) (充分下降條件)?k>0, 存在a>0,F(xk)?F(xk+1)≥a||xk+1?xk||2;

(H2) (相對誤差條件)?k>0, 存在b>0, 存在使得

(H3) (連續(xù)條件)存在子列xki和聚點(diǎn)使得當(dāng)i→+∞,有xki→且F(xki)→F().事實(shí)上, 令a=μ, (H1) 很容易由引理3.1 得出.令易由引理3.1 得出.下面證明(H3).

由F(x) 的強(qiáng)制性, 知道{xk} 包含在水平集{xk∈X:F(xk)≤F(x1)} 中, 利用Bolzano-Weierstrass 定理, 得出存在子集記為xki收斂到某個(gè)聚點(diǎn).由xk+1的定義有

又由Φk的定義, 有由上可得F(xki+1)≤F().

一方面, 由F的連續(xù)性, 得到其中是收斂到的序列, 由引理3.1, 得到{xki+1} 也收斂到.另一方面, 由F(·) 的下半連續(xù)性, 得到F(), 于是可以得到: 存在一個(gè)子列{xki} 收斂到, 且當(dāng)?shù)米C.

回到算法1 的收斂性證明, 知道F(x) 是半代數(shù)的, 且是一個(gè)KL 函數(shù), 由KL 函數(shù)的性質(zhì)(見定義2.4), 存在ζ>0,的鄰域V和一個(gè)連續(xù)凹函?:[0,ζ)→R+, 對所有的x∈V, 有

其中F?:=F().

取r>0, 則Br()?V.已知存在子列{xki} 收斂到, 則意味著存在一個(gè)xkN, 使得

(a)xkN∈V;

通過(H1), (H2), (H3), (a), (b) 和(c), 利用文獻(xiàn)[10]的定理2.9, 可以得到{xk} 收斂到.

4 數(shù)值試驗(yàn)

考慮(1.1) 優(yōu)化問題, 我們通過設(shè)計(jì)加L1,L2 正則化項(xiàng)的神經(jīng)網(wǎng)絡(luò)做分類試驗(yàn), 來驗(yàn)證算法的有效性.

神經(jīng)網(wǎng)絡(luò)[11]的模型如圖1 所示, 一個(gè)神經(jīng)元對輸入信號X=[x1,x2,...,xn]的輸出為y=f(u+b), 其中公式中各字符含義如圖1 所示.神經(jīng)網(wǎng)絡(luò)的訓(xùn)練通常用誤差函數(shù)(也稱目標(biāo)函數(shù))E來衡量, 當(dāng)誤差函數(shù)小于設(shè)定的值時(shí)即停止神經(jīng)網(wǎng)絡(luò)的訓(xùn)練.誤差函數(shù)為衡量實(shí)際輸出向量Yk與期望向量Tk誤差大小的函數(shù), 常采用二乘誤差函數(shù)來定義為為訓(xùn)練樣本個(gè)數(shù).在模型訓(xùn)練時(shí), 如果參數(shù)過多, 模型過于復(fù)雜, 容易造成過擬合(overfit), 即模型在訓(xùn)練樣本數(shù)據(jù)上表現(xiàn)得很好, 但在實(shí)際測試樣本上表現(xiàn)得較差, 不具備良好的泛化能力.為了避免過擬合, 最常用的一種方法是使用使用正則化, 例如L1 和L2 正則化, 其中L1 正則化產(chǎn)生更加稀疏的權(quán)值.在誤差函數(shù)的基礎(chǔ)上加正則化項(xiàng)后的損失函數(shù)為

圖1: 人工神經(jīng)元模型

表2: L1+ 近端梯度下降算法與L2+ 梯度下降算法分類錯(cuò)誤率

在不同數(shù)據(jù)集上, 采用L1+PG 和L2+GD 的模型進(jìn)行神經(jīng)網(wǎng)絡(luò)訓(xùn)練, 可以看到L1+PG 模型的分類錯(cuò)誤率均低于L2+GD 模型, 通過損失曲線的對比, 可以看出L1+PG 比L2+GD模型的訓(xùn)練更加快速達(dá)到收斂.

圖2: CANCER 數(shù)據(jù)集上的錯(cuò)誤率曲線

圖3: DIGITS 數(shù)據(jù)集上的錯(cuò)誤率曲線

圖4: CANCER 數(shù)據(jù)集上的損失曲線

圖5: DIGITS 數(shù)據(jù)集上的損失曲線