一類最小二乘的自動調(diào)參問題的求解算法

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

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

O221.1

A

0812-06

06.011

本文考慮最小二乘自動調(diào)參問題

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

（1）

這里

r（ω）：Rn→R∪{+∞}是防止過度擬合的正則化函數(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ù).問題（1）中

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

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

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

該最小二乘問題的形式為

minθ∈Rn×m

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

（2）

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

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

當θls（ω）=ω時，問題（1）轉(zhuǎn)變?yōu)樽畛Ｒ姷姆峭狗枪饣瑥秃虾瘮?shù)

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

（3）

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

受文獻[4，18]的啟發(fā)，將APGnc+算法的思想應用于求解最小二乘自動調(diào)參問題，力爭進一步提升計算速度.

1 計算方法

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

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

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

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

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

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

定義 1.1（次微分）[18]

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

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

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

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

定義 1.2（臨界點）[18]

點ω∈Rn為f（·）的臨界點當且僅當0∈f（ω）.

定義 1.3（距離）[18]

點ω∈Rn到閉集ΩRn的距離定義為

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

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

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

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

其中，ηgt;0.

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

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

有

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

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

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

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

for k=1，2，…，niter

步驟1：解決最小二乘問題

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

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

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

步驟4：計算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

假設（H3）成立，則對任意的ω，y∈Rn，有

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

（4）

其中

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

（5）

證明

對任意ω，y∈Rn，構造函數(shù)

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

在上式中，關于t求導可得

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）

由假設（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.

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

引理 1.7

假設（H3）成立，則對任意的η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）

由假設（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}有極限點.

引理 1.8

假設（H1）～（H3）成立且步長ηlt;1L.由算法A所生成的序列{ωk}滿足：

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

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

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

證明

（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），則對所有的kgt;0，下列不等式成立

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

（12）

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

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

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

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

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

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

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

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

（14）

在（14）式兩邊，關于k求和可得

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

（15）

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

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

上式兩端同時加上ω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），由假設（H3），可得

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

（17）

考慮任意極限點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′）.

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

limk→∞ sup r（ωk）≤r（z′）.另一方面，函數(shù)r（·）滿足下半連續(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）式可得，對任意的z′∈Ω，有

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

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

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

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

定理 1.9[14]

假設（H1）～（H3）成立且對所有的ω∈Ω，有F（ω）≡F*.記zk：=F（ωk）-F*且cgt;0.當步長ηlt;1L時，序列{zk}在k0足夠大時滿足：

（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），收斂速度通常是線性的;參數(shù)l∈（0，12），收斂速度為次線性速度.

2 數(shù)值實驗

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

首先，給出所用的目標函數(shù)，并對其中所用到的超參數(shù)進行說明.

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為關聯(lián)矩陣.正則化超參數(shù)（ω1，ω2）分別對R1和R2進行加權.向量a1，a2，…，ak∈R1×784為樣本數(shù)據(jù)，向量y1，y2，…，yk∈R1×10為對應標簽.

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

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

參考文獻

[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] 左鑫怡，蔣毅，楊嵐. 一類截斷函數(shù)最優(yōu)化問題的求解方法[J]. 四川師范大學學報（自然科學版），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

（編輯 余 毅）