一類(lèi)最小二乘的自動(dòng)調(diào)參問(wèn)題的求解算法

運(yùn)用APGnc+算法思想，求解最小二乘自動(dòng)調(diào)參問(wèn)題.以MNIST數(shù)據(jù)集為基礎(chǔ)，考察最小二乘自動(dòng)調(diào)參在分類(lèi)問(wèn)題中的應(yīng)用.此外，數(shù)值實(shí)驗(yàn)結(jié)果表明本文的算法比已有的方法快.

最小二乘自動(dòng)調(diào)參; KL性質(zhì); APGnc+算法

O221.1

A

0812-06

06.011

本文考慮最小二乘自動(dòng)調(diào)參問(wèn)題

minω∈RnF（ω）：=ψ（θls（ω））+r（ω），

（1）

這里

r（ω）：Rn→R∪{+∞}是防止過(guò)度擬合的正則化函數(shù)[1-3].一般有3種形式：

1） r（ω）=λ1‖ω‖1（Lasso），

2） r（ω）=λ22‖ω‖22（Ridge Regression），

3） r（ω）=λ1‖ω‖1+λ22‖ω‖22（Elastic Net），

其中λ1和λ2為正則化參數(shù).問(wèn)題（1）中

ψ（θls（·））：Rn→R是光滑的非凸函數(shù)，θls（·）：Rn→Rn×m是帶有超參數(shù)向量的最小二乘問(wèn)題的解

θls（ω）：=A（ω）B（ω）=（A（ω）TA（ω））-1A（ω）TB（ω），

其中，參數(shù)矩陣A（ω）∈Rk×n，B（ω）∈Rk×m，A（ω）為Moore-Penrose廣義逆.

該最小二乘問(wèn)題的形式為

minθ∈Rn×m

‖A（ω）θ-B（ω）‖2F，

（2）

‖·‖F(xiàn)為F-范數(shù).

據(jù)我們所知，關(guān)于求解最小二乘自動(dòng)調(diào)參問(wèn)題，已有的研究成果還較少.文獻(xiàn)[4]引入了近端梯度算法[5]的思想，給出求解最小二乘自動(dòng)調(diào)參問(wèn)題的算法.此外，以分類(lèi)問(wèn)題為例，表明了最小二乘自動(dòng)調(diào)參相較于一般的最小二乘法的優(yōu)越性，特別是可以將測(cè)試誤差減半.最小二乘自動(dòng)調(diào)參問(wèn)題具備應(yīng)用價(jià)值，如文獻(xiàn)[6]給出了最小二乘自動(dòng)調(diào)參求解卡爾曼光滑器中的參數(shù)擬合問(wèn)題的應(yīng)用.

當(dāng)θls（ω）=ω時(shí)，問(wèn)題（1）轉(zhuǎn)變?yōu)樽畛Ｒ?jiàn)的非凸非光滑復(fù)合函數(shù)

minω∈Rn J（ω）：=ψ（ω）+r（ω）.

（3）

近年來(lái)，非凸非光滑問(wèn)題（3）受到廣泛的關(guān)注和研究，并在多個(gè)領(lǐng)域獲得應(yīng)用.例如，求解統(tǒng)計(jì)學(xué)和壓縮感知問(wèn)題[7]、圖像處理問(wèn)題[8-9]和機(jī)器學(xué)習(xí)中的邏輯回歸問(wèn)題[10]等.針對(duì)此類(lèi)問(wèn)題，許多學(xué)者提出了多種不同的算法，包括非凸優(yōu)化的慣性近端算法（iPiano）[11]、一般迭代收縮和閾值算法（GIST）[7]以及ADMM算法[12-13]等.此外，文獻(xiàn)[14]中提出了mAPG算法和nmAPG算法，通過(guò)利用KL性質(zhì)[15]，證明了對(duì)于非凸問(wèn)題，2種算法以次線(xiàn)性和線(xiàn)性速度收斂到臨界點(diǎn).然而，mAPG算法和nmAPG算法需要2次近端梯度步驟，這相對(duì)于原始APG算法[16]的計(jì)算復(fù)雜度增加了一倍.針對(duì)這一問(wèn)題，文獻(xiàn)[17]給出了niAPG算法，該算法只需1次近端梯度步驟，從而提高了算法速度.此外，文獻(xiàn)[18]在niAPG算法的基礎(chǔ)上，提出了一種對(duì)非凸問(wèn)題更直觀(guān)的動(dòng)量步長(zhǎng)選擇的APGnc+算法.

受文獻(xiàn)[4，18]的啟發(fā)，將APGnc+算法的思想應(yīng)用于求解最小二乘自動(dòng)調(diào)參問(wèn)題，力爭(zhēng)進(jìn)一步提升計(jì)算速度.

1 計(jì)算方法

首先，給出本文所需基本假設(shè)（H1）～（H3）和預(yù)備知識(shí).記‖·‖為Rn范數(shù).

（H1） 目標(biāo)函數(shù)F（·）滿(mǎn)足infω∈RnF（ω）gt;-∞且下水平集{ω∈Rn：F（ω）≤α，α∈R}有界;

（H2） 正則化函數(shù)r（·）滿(mǎn)足下半連續(xù)且函數(shù)ψ（θls（·））＼，r（·）滿(mǎn)足KL性質(zhì);

（H3） ψ（θls（·））滿(mǎn)足Lipschitz連續(xù)，即存在Lgt;0，使得

‖ωψ（θls（ω））-yψ（θls（y））‖≤L‖ω-y‖， ω，y∈Rn.

定義擴(kuò)展實(shí)值函數(shù)f：Rn→（-∞，+∞]的有效域dom f={ω∈Rn：f（ω）lt;∞}非空，則稱(chēng)f是正常函數(shù).若函數(shù)f滿(mǎn)足對(duì)任意的c∈R，集合{ω∈Rn：f（ω）≤c}都是閉集，則稱(chēng)f是閉函數(shù).

定義 1.1（次微分）[18]

正常下半連續(xù)函數(shù)f（·）在ω∈dom f處的Frechét次微分f是u∈Rn的集合，滿(mǎn)足

limz≠ωinfz→ωf（z）-f（ω）-uT（z-ω）‖z-ω‖≥0.

f（·）在ω∈dom f處的極限次微分f是f的閉包且滿(mǎn)足

{u：（ωk，f（ωk））→（ω，f（ω）），f（ωk）uk→u}.

定義 1.2（臨界點(diǎn)）[18]

點(diǎn)ω∈Rn為f（·）的臨界點(diǎn)當(dāng)且僅當(dāng)0∈f（ω）.

定義 1.3（距離）[18]

點(diǎn)ω∈Rn到閉集ΩRn的距離定義為

distΩ（ω）：=miny∈Ω‖y-ω‖.

定義 1.4（鄰近算子）[5]

正常下半連續(xù)函數(shù)f（·）在點(diǎn)v∈Rn處的鄰近算子定義為

proxη，f（v）：=argminω∈Rn（f（ω）+12η‖ω-v‖2），

其中，ηgt;0.

引理 1.5（一致KL性質(zhì)）[15] 設(shè)Ω是緊集，且f（·）是正常下半連續(xù)函數(shù). 假設(shè)f（·）在Ω上為常數(shù)且在Ω上的每個(gè)點(diǎn)處都滿(mǎn)足KL性質(zhì)，則存在ε， δgt;0， 使得對(duì)任意∈Ω和所有滿(mǎn)足以下條件的ω：

ω∈{ω∈Rn：distΩ（ω）lt;ε}∩[ω：f（）lt;f（ω）lt;f（）+δ]，

有

′（f（ω）-f（））distf（ω）（0）≥1，

其中，函數(shù)：[0，δ）→R+的形式為（t）=cltl，cgt;0且l∈（0，1].

下面，受文獻(xiàn)[4，18]的啟發(fā)，應(yīng)用APGnc+算法的思想給出求解最小二乘自動(dòng)調(diào)參問(wèn)題的計(jì)算方法，記為算法A.其中，k為算法迭代次數(shù)，η為步長(zhǎng).算法A的步驟如下：

輸入：ω0∈Rn，y1=ω0∈Rn，β，t∈（0，1），ηlt;1L，最大迭代次數(shù)niter.

for k=1，2，…，niter

步驟1：解決最小二乘問(wèn)題

θls（yk）=（A（yk）TA（yk））-1A（yk）TB（yk）;

步驟2：計(jì)算梯度gyk=ykψ（θls（yk））;

步驟3：計(jì)算ωk=proxη，r（yk-ηgyk）;

步驟4：計(jì)算vk=ωk+β（ωk-ωk-1）;

if F（ωk）≤F（vk）

步驟5：yk+1=ωk;

步驟6：β=tβ;

else

步驟7：yk+1=vk;

步驟8：β=min{β/t，1};

end if

步驟9：k=k+1;

end for

為分析算法A的收斂性，先給出以下引理.

引理 1.6

假設(shè)（H3）成立，則對(duì)任意的ω，y∈Rn，有

F（ω）≤Q（ω，y），

（4）

其中

Q（ω，y）：=ψ（θls（y））+[yψ（θls（y））]T（ω-y）+L2‖ω-y‖2+r（ω）.

（5）

證明

對(duì)任意ω，y∈Rn，構(gòu)造函數(shù)

h（t）：=ψ[θls（y+t（ω-y））].

在上式中，關(guān)于t求導(dǎo)可得

h′（t）=y+t（ω-y）ψ[θls（y+t（ω-y））]T（ω-y），

則

h′（t）-h′（0）={y+t（ω-y）ψ[θls（y+t（ω-y））]-yψ（θls（y））}T（ω-y）.

（6）

由假設(shè)（H3）成立，則有

‖y+t（ω-y）ψ[θls（y+t（ω-y））]-yψ（θls（y））‖≤L‖t（ω-y）‖，

（7）

將（7）式代入（6）式中，容易推出

h′（t）-h′（0）≤Lt‖ω-y‖2.

（8）

此外，由牛頓-萊布尼茲公式和（8）式，可得

ψ（θls（ω））=h（1）=h（0）+∫10h′（t）dt≤

h（0）+∫10（h′（0）+Lt‖ω-y‖2）dt=

h（0）+h′（0）+L2‖ω-y‖2=

ψ（θls（y））+[yψ（θls（y））]T（ω-y）+L2‖ω-y‖2.

在上述不等式兩端同時(shí)加上r（ω），由（1）和（5）式，可得（4）式成立.

引理 1.7

假設(shè)（H3）成立，則對(duì)任意的ηgt;0，y∈Rn且ω=proxη，r[y-ηyψ（θls（y））]，有

F（ω）≤F（y）-（12η-L2）‖ω-y‖2.

（9）

證明

由鄰近算子的定義，可得

ω=argmin∈Rn{r（）+12η‖-y+ηyψ（θls（y））‖2}=

argmin∈Rn{r（）+[yψ（θls（y））]T（-y）+12η‖-y‖2}.

由最優(yōu)性條件，可得

r（ω）+[yψ（θls（y））]T（ω-y）+12η‖ω-y‖2≤r（y）.

（10）

由假設(shè)（H3）成立，結(jié)合（4）和（10）式，可得

F（ω）≤ψ（θls（y））+[yψ（θls（y））]T（ω-y）+L2‖ω-y‖2+r（ω）≤

ψ（θls（y））+[yψ（θls（y））]T（ω-y）+L2‖ω-y‖2+r（y）-

[yψ（θls（y））]T（ω-y）-12η‖ω-y‖2=

F（y）-（12η-L2）‖ω-y‖2.

由此可得，（9）式成立.

基于以上引理，分析算法A生成的序列{ωk}有極限點(diǎn).

引理 1.8

假設(shè)（H1）～（H3）成立且步長(zhǎng)ηlt;1L.由算法A所生成的序列{ωk}滿(mǎn)足：

（a） {ωk}是有界序列;

（b） {ωk}的極限點(diǎn)集Ω是一個(gè)緊集，且在該緊集上的目標(biāo)函數(shù)F（·）為常值;

（c） 極限點(diǎn)集Ω中所有元素都是F（·）的臨界點(diǎn).

證明

（a） 在（9）式中，令ω=ωk且y=yk，可得

F（ωk）≤F（yk）-（12η-L2）‖ωk-yk‖2.

（11）

由于ηlt;1L，則有F（ωk）≤F（yk）.

由算法A中的步驟5～8，可以保證F（yk+1）≤F（ωk），則對(duì)所有的kgt;0，下列不等式成立

F（yk+1）≤F（ωk）≤F（yk）≤F（ωk-1）.

（12）

由假設(shè)（H1）和（12）式，可知F（ωk），F(xiàn)（yk）≥inf F≥-∞，故序列{F（ωk）}＼，{F（yk）}收斂于同一個(gè)極限F*，即

limk→∞ F（ωk）=limk→∞ F（yk）=F*.（13）

此外，對(duì)所有的kgt;0，有F（ωk）≤F（ω0）且F（yk）≤F（ω0）.由函數(shù)F（·）的下水平集有界，故序列{ωk}和{yk}是有界的.

（b） 由集合Ω是序列{ωk}的極限點(diǎn)集，可得Ω是閉集.結(jié)合序列{ωk}是有界的，可得{ωk}的極限點(diǎn)集Ω有界.由集合Ω是閉集并且有界，可得Ω是Rn中的緊集.

下面，證明目標(biāo)函數(shù)F（·）在緊集Ω上為常值.

由（11）和（12）式，容易推出

（12η-L2）‖yk-ωk‖2≤F（yk）-F（ωk）

≤F（yk）-F（yk+1）.

（14）

在（14）式兩邊，關(guān)于k求和可得

∑∞k=1（12η-L2）‖yk-ωk‖2≤F（y1）-inf F≤∞.

（15）

根據(jù)正項(xiàng)級(jí)數(shù)的性質(zhì)，由（15）式可得：當(dāng)k→∞時(shí)，‖yk-wk‖→0.此外，由算法A中步驟3的最優(yōu)性條件，可得

-ykψ（θls（yk））-1η（ωk-yk）∈r（ωk），

上式兩端同時(shí)加上ωkψ（θls（ωk）），可得

ωkψ（θls（ωk））-ykψ（θls（yk））-1η（ωk-yk）∈F（ωk）.

（16）

令

uk：=ωkψ（θls（ωk））-ykψ（θls（yk））-1η（ωk-yk），由假設(shè)（H3），可得

‖uk‖≤（L+1η）‖yk-ωk‖.

（17）

考慮任意極限點(diǎn)z′∈Ω.令ωk→z′且yk→z′（k→∞）.根據(jù)鄰近算子的定義，容易推出

[ykψ（θls（yk））]T（ωk-yk）+12η‖ωk-yk‖2+r（ωk）≤

[ykψ（θls（yk））]T（z′-yk）+12η‖z′-yk‖2+r（z′）.

在上述不等式兩端同時(shí)取極限，可得

limk→∞ sup r（ωk）≤r（z′）.另一方面，函數(shù)r（·）滿(mǎn)足下半連續(xù)性，即

limk→∞" inf r（ωk）≥r（z′），

故

limk→∞ r（ωk）=r（z′）.

結(jié)合函數(shù)ψ（θls（·））的連續(xù)性

limk→∞ ψ（θls（ωk））=ψ（θls（z′）），容易推出

limk→∞ F（ωk）=F（z′）.

（18）

由（13）式可得，對(duì)任意的z′∈Ω，有

limk→∞ F（ωk）=F*F（z′）=F*.

因此，F(xiàn)在緊集Ω上的值保持不變.

（c） 由（16）～（18）式，可得k→∞時(shí)，uk→0且對(duì)所有z′∈Ω，有0∈F（z′）成立，即極限點(diǎn)集Ω中所有元素都是F（·）的臨界點(diǎn).

基于定理1.8，根據(jù)文獻(xiàn)[14]中的方法，可以得到算法A的收斂性.

定理 1.9[14]

假設(shè)（H1）～（H3）成立且對(duì)所有的ω∈Ω，有F（ω）≡F*.記zk：=F（ωk）-F*且cgt;0.當(dāng)步長(zhǎng)ηlt;1L時(shí)，序列{zk}在k0足夠大時(shí)滿(mǎn)足：

（a） 如果l=1，則zk在有限步內(nèi)減少為零;

（b） 如果l∈[12，1），則

zk≤（c2d11+c2d1）k-k0zk0， d1=（1η+L）212η-L2;

（c） 如果l∈（0，12），則

zk≤（c（k-k0）d2（1-2l））11-2l，d2=min{12cd1，c1-2l（22l-12l-2-1）z2l-1k0}.

定理1.9描述了算法A的3種收斂形式：參數(shù)l=1，迭代在有限步內(nèi)結(jié)束;參數(shù)l∈[12，1），收斂速度通常是線(xiàn)性的;參數(shù)l∈（0，12），收斂速度為次線(xiàn)性速度.

2 數(shù)值實(shí)驗(yàn)

下面考慮文獻(xiàn)[4]中給出最小二乘自動(dòng)調(diào)參在多分類(lèi)問(wèn)題中的應(yīng)用，測(cè)試了算法A的性能.以MNIST手寫(xiě)數(shù)字?jǐn)?shù)據(jù)集為數(shù)值實(shí)驗(yàn)數(shù)據(jù)，數(shù)值實(shí)驗(yàn)結(jié)果表明，本文所給出的算法相較于文獻(xiàn)[4]中的算法具有更快的收斂速度.本節(jié)所有的數(shù)值實(shí)驗(yàn)均是在Matlab R2022a，12th Gen Intel（R） Core（TM） i-12500H 2.50 GHz環(huán)境下執(zhí)行.

首先，給出所用的目標(biāo)函數(shù)，并對(duì)其中所用到的超參數(shù)進(jìn)行說(shuō)明.

minω∈Rn F（ω）：=1N∑Ni=1{-ai[（A（ω）TA（ω））-1A（ω）TB（ω）]bTi+

log（∑ml=1eai[（A（ω）TA（ω））-1A（ω）TB（ω）]l）}+0.01‖ω‖2，

i=1，2，…，N， l=1，2，…，m，

（19）

其中，ai表示矩陣A（ω）的第i行，bi表示矩陣B（ω）的第i行.

模型中參數(shù)矩陣A（ω）和B（ω）的形式為

A（ω）=a1akeω1R1eω2R2，

B（ω）=y1yk00，

其中R1、R2是正則化矩陣，形式為

R1=I， R2=G.

矩陣R1為單位矩陣，R2∈R1 512×784為關(guān)聯(lián)矩陣.正則化超參數(shù)（ω1，ω2）分別對(duì)R1和R2進(jìn)行加權(quán).向量a1，a2，…，ak∈R1×784為樣本數(shù)據(jù)，向量y1，y2，…，yk∈R1×10為對(duì)應(yīng)標(biāo)簽.

下面，使用MNIST手寫(xiě)數(shù)字?jǐn)?shù)據(jù)集進(jìn)行數(shù)值實(shí)驗(yàn).該數(shù)據(jù)集中包含50 000個(gè)訓(xùn)練數(shù)據(jù)點(diǎn)和10 000個(gè)測(cè)試數(shù)據(jù)點(diǎn).該數(shù)據(jù)集共有10個(gè)類(lèi)別，分別對(duì)應(yīng)數(shù)字0～9.首先，運(yùn)行ADMM算法[12-13]得到問(wèn)題（19）的全局最優(yōu)解.當(dāng)算法A中的目標(biāo)函數(shù)值與ADMM算法所得最優(yōu)值的相對(duì)變化小于10-5或迭代次數(shù)超過(guò)1 000次時(shí)，算法終止.應(yīng)用算法A和文獻(xiàn)[4]中的算法測(cè)試了9組不同大小的數(shù)據(jù)，范圍從3 500個(gè)數(shù)據(jù)到35 000個(gè)數(shù)據(jù)，并將得到的數(shù)值結(jié)果匯總在表1中，其中包括驗(yàn)證損失、測(cè)試誤差和實(shí)驗(yàn)所用時(shí)間，其結(jié)果為10次實(shí)驗(yàn)的平均值.

從表1中可以看出，在驗(yàn)證損失和測(cè)試誤差相差不大的情況下，算法A的計(jì)算用時(shí)明顯低于文獻(xiàn)[4]中算法的計(jì)算用時(shí).因此，數(shù)值實(shí)驗(yàn)結(jié)果表明，2種算法都有效，且在測(cè)試誤差相差不大的同時(shí)，算法A的性能明顯優(yōu)于文獻(xiàn)[4]中的算法.

參考文獻(xiàn)

[1] HOERL A E， KENNARD R W. Ridge regression： biased estimation for nonorthogonal problems[J]. Technometrics，1970，12（1）：55-67.

[2] TIBSHIRANI R. Regression shrinkage and selection via the Lasso[J]. Journal of the Royal Statistical Society： Series B （Methodological），1996，58（1）：267-288.

[3] ZOU H， HASTIE T. Regularization and variable selection via the elastic net[J]. Journal of the Royal Statistical Society： Series B （Methodological），2005，67（2）：301-320.

[4] BARRATT S T， BOYD S P. Least squares auto-tuning[J]. Engineering Optimization，2021，53（5）：789-810.

[5] BECK A. First-order methods in optimization[M]. Philadelphia： Society for Industrial and Applied Mathematics （SIAM，3600 Market Street，F(xiàn)loor 6，Philadelphia，PA 19104），2017.

[6] BARRATT S T， BOYD S P. Fitting a kalman smoother to data[C]//2020 American Control Conference （ACC）. Denver： IEEE，2020：1526-1531.

[7] GONG P， ZHANG C， LU Z， et al. A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems[C]//International Conference on Machine Learning. New York： PMLR，2013：37-45.

[8] NIKOLOVA M， NG M K， ZHANG S Q， et al. Efficient reconstruction of piecewise constant images using nonsmooth nonconvex minimization[J]. SIAM Journal on Imaging Sciences，2008，1（1）：2-25.

[9] NIKOLOVA M， NG M， TAM C P. Fast nonconvex nonsmooth minimization methods for image restoration and reconstruction[J]. IEEE Transactions on Image Processing，2010，19（12）：3073-3088.

[10] SHEN X， GU Y. Nonconvex sparse logistic regression with weakly convex regularization[J]. IEEE Transactions on Signal Processing，2018，66（12）：3199-3211.

[11] OCHS P， CHEN Y J， BROX T， et al. iPiano： inertial proximal algorithm for nonconvex optimization[J]. SIAM Journal on Imaging Sciences，2014，7（2）：1388-1419.

[12] WANG Y， YIN W， ZENG J S. Global convergence of ADMM in nonconvex nonsmooth optimization[J]. Journal of Scientific Computing，2018，78（1）：29-63.

[13] 左鑫怡，蔣毅，楊嵐. 一類(lèi)截?cái)嗪瘮?shù)最優(yōu)化問(wèn)題的求解方法[J]. 四川師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2022，45（4）：483-488.

[14] LI H， LIN Z. Accelerated proximal gradient methods for nonconvex programming[C]//Neural Information Processing Systems. Cambridge： MIT Press，2015：379-387.

[15] BOLTE J， SABACH S， TEBOULLE M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems[J]. Mathematical Programming，2014，146（1/2）：459-494.

[16] BECK A， TEBOULLE M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences，2009，2（1）：183-202.

[17] YAO Q M， KWOK J T， GAO F， et al. Efficient inexact proximal gradient algorithm for nonconvex problems[C]//Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. California： International Joint Conferences on Artificial Intelligence Organization，2017：3308-3314.

[18] LI Q， ZHOU Y， LIANG Y， et al. Convergence analysis of proximal gradient with momentum for nonconvex optimization[C]//International Conference on Machine Learning. New York： PMLR，2017：2111-2119.

An Algorithm for Solving Least Squares AutomaticParameter Tuning Problems

XU Xinyue， JIANG Yi

（School of Mathematical Sciences， Sichuan Normal University， Chengdu 610066， Sichuan ）

In this paper， the APGnc+ algorithm is used to solve the least squares automatic parameter tuning problem. Based on the MNIST data set， we consider the application of least squares automatic parameter tuning in classification problems. In addition， the numerical experimental results show that the algorithm in this paper is faster than the existing methods.

least squares automatic parameter tuning; KL property; APGnc+ algorithm

2020 MSC：90C06; 90C20; 90C26

（編輯 余 毅）