稀疏正則非凸優化問題之全局收斂分析

儲敏

(武漢大學數學與統計學院, 湖北武漢 430072)

1 引言

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

考慮如下非凸組合優化問題

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

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

2 預備知識

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

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

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

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

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

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

(i)?(0)=0;

(ii)?在(0,ζ) 上是一階連續可導的;

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

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

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

(b) 在dom?f內每個點都滿足Kurdyka-Lojasiewicz 不等式的正常下半連續函數, 稱為KL 函數.

3 模型及收斂性分析

首先, 縱觀全文對函數f和g做如下假設.

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

(ii)f和g是非負、正常、強制、半代數函數.

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

表1: 近端梯度算法

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

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

(ii)

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

進行化簡后可得到

利用f的Lipschitz 連續可微性, 得到

從而(i) 得證.

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

從而(ii) 得證.

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

另一方面, 由算法1 的一階優化條件, 得到

化簡得到

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

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

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

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

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

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

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

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

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

一方面, 由F的連續性, 得到其中是收斂到的序列, 由引理3.1, 得到{xki+1} 也收斂到.另一方面, 由F(·) 的下半連續性, 得到F(), 于是可以得到: 存在一個子列{xki} 收斂到, 且當得證.

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

其中F?:=F().

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

(a)xkN∈V;

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

4 數值試驗

考慮(1.1) 優化問題, 我們通過設計加L1,L2 正則化項的神經網絡做分類試驗, 來驗證算法的有效性.

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

圖1: 人工神經元模型

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

在不同數據集上, 采用L1+PG 和L2+GD 的模型進行神經網絡訓練, 可以看到L1+PG 模型的分類錯誤率均低于L2+GD 模型, 通過損失曲線的對比, 可以看出L1+PG 比L2+GD模型的訓練更加快速達到收斂.

圖2: CANCER 數據集上的錯誤率曲線

圖3: DIGITS 數據集上的錯誤率曲線

圖4: CANCER 數據集上的損失曲線

圖5: DIGITS 數據集上的損失曲線