王 淇 淇

(北京郵電大學(xué) 理學(xué)院， 北京 100876)

本文考慮下面的極大極小值優(yōu)化問題：

(1)

其中：X∈Rn,Y∈Rm是非空閉凸集，f∶X×Y→R是一個可微的光滑函數(shù).許多實際問題都可以抽象成極大極小值問題，例如生成對抗模型的目標(biāo)函數(shù)[1]，多領(lǐng)域上的魯棒優(yōu)化問題等.

解決極大極小值問題可以等價于尋找目標(biāo)函數(shù)的鞍點.一個不是局部最小值的駐點稱為鞍點.如果一個點是鞍點，那么表示目標(biāo)函數(shù)在此點上的梯度值為 0，但是從該點出發(fā)的一個方向是函數(shù)的極大值點，而從該點出發(fā)的另一個方向則是函數(shù)的極小值點.所以判斷鞍點的一個充分條件是，函數(shù)在一階導(dǎo)數(shù)為零處(駐點)的Hessian矩陣為不定矩陣.

目前對極大極小值問題的研究的關(guān)注點大多是在凸-凹問題上，即目標(biāo)函數(shù)f(x,y)關(guān)于x是一個凸函數(shù)，關(guān)于y則是一個凹函數(shù).常用的算法是GDA算法，即對極小值問題選擇用梯度下降方向優(yōu)化，對極大值問題用梯度上升方向優(yōu)化，同時交替地更新x和y.在f(x,y)關(guān)于x和y都是局部強凸的假設(shè)下，GDA算法已經(jīng)被證明具有局部線性收斂性[2]，然而實驗表明GDA算法即使對于一個簡單的非凸-非凹問題(即目標(biāo)函數(shù)f(x,y)關(guān)于x不是一個凸函數(shù)，關(guān)于y也不是一個凹函數(shù))都無法保證收斂性[3].在關(guān)于非凸-非凹問題的研究上，Daskalakis于2018年提出了OMD算法[4]，OMD算法能避免GDA方法在雙線性問題上的“循環(huán)”現(xiàn)象，保證收斂性.Wei Peng等人則于2020年提出了ACA算法[5]，該算法受勻速圓周運動的啟發(fā)，在更新格式中加上了一步梯度項，使算法在雙線性問題上能夠收斂，同時算法在生成對抗網(wǎng)絡(luò)這個特殊的極大極小值問題上也有具有競爭力的表現(xiàn).

1 優(yōu)化算法

首先介紹基于梯度的優(yōu)化算法，即梯度法下降法(GD)，如式(2)，t是當(dāng)前迭代次數(shù)，η是學(xué)習(xí)率，也叫做步長，f(x)是優(yōu)化的目標(biāo)函數(shù)，xf(xt)是目標(biāo)函數(shù)f(x)在第t次迭代點xt處的梯度.梯度下降法是用來解決極小值問題的優(yōu)化算法，其基本思想是將當(dāng)前迭代點位置的負梯度方向作為搜索方向，因為該方向是當(dāng)前位置的最快下降方向，所以也被稱為是“最速下降法”.目前梯度下降法已經(jīng)在機器學(xué)習(xí)中得到了非常廣泛的應(yīng)用，很多改進算法都是基于梯度下降法的思想來進行改進.

xt+1=xt-ηf(xt)

(2)

1.1 GDA算法

GDA(Gradient Descent Ascent)算法，即梯度下降上升算法，是目前常見的用于解決極大極小值問題的優(yōu)化算法.它的思想類似于梯度下降算法，即對于極小值問題，選擇負梯度方向進行優(yōu)化，而對于極大值問題，選擇正梯度方向進行優(yōu)化.在迭代過程中，同時交替地進行優(yōu)化.迭代格式如式(3)所示.

xt+1=xt-γ1xf(xt,yt)
yt+1=yt+γ2yf(xt,yt)

(3)

其中：步長γ1,γ2∈R,γ1,γ2>0.

但是已有數(shù)值實驗表明，GDA算法在一個簡單的雙線性極大極小值問題上無法收斂到鞍點，如圖1所示，出現(xiàn)了“循環(huán)”現(xiàn)象.這使得GDA算法無法保證收斂性.

圖1 比較GDA,OMD,ACA三種算法在問題(8)上的表現(xiàn)Figure 1 Comparing the performance of GDA, OMD, ACA on the problem (8)

1.2 OMD算法

OMD(Optimism Mirror Descent)算法，也叫樂觀鏡像算法，是由Daskalakis等人于2018年提出的另一種用于解決極大極小值問題的優(yōu)化算法.該算法的思想來源于在線優(yōu)化算法，由于梯度下降法可以等同于帶有一個l2的正則化的在線優(yōu)化算法FTRL(Follow the Regularized Leader)，如式(4)所示

(4)

OMD算法通過增加下一次迭代梯度的預(yù)測Mx,t+1來改進在線優(yōu)化算法.

(5)

當(dāng)選擇上一次梯度來用來預(yù)測下一次迭代梯度時，即在式(5)中，用Mx,t+1=x,tf來預(yù)測第(t+1)次迭代目標(biāo)函數(shù)關(guān)于x的梯度，用Mx,t=x,t-1f來預(yù)測第t次迭代目標(biāo)函數(shù)關(guān)于x的梯度.得到了如下的更新格式(yt+1迭代格式的推導(dǎo)同如上xt+1的推導(dǎo)).

xt+1=xt-2ηxf(xt,yt)+ηxf(xt-1,yt-1)

yt+1=yt+2ηyf(xt,yt)-ηyf(xt-1,yt-1)

(6)

其中:η∈R,η>0.

1.3 ACA算法

ACA(Alternative centripetal algorithm)算法，即向心加速度算法，是由Wei Peng等人于2020年提出的優(yōu)化算法.ACA算法的主要思想來源于勻速圓周運動.在GDA算法出現(xiàn)“循環(huán)”現(xiàn)象后，受到勻速圓周運動中向心加速度的啟發(fā)，將每一次迭代中的梯度等同于勻速圓周運動的速度，用相鄰兩次迭代的梯度差來近似勻速圓周運動中的瞬時向心加速度，迭代格式如式(7)所示，其中xf(xt,yt)-xf(xt-1,yt-1)項就是用來近似圓周運動中向心加速度的梯度差.

(7)

其中：α1,α2,β1,β2∈,α1,α2,β1,β2>0.

對于上述提到的三種優(yōu)化算法，本文考慮如下面式(8)的極大極小值問題，這是一個簡單的雙線性問題，該問題的最優(yōu)值點，即鞍點為(0,0)點.由于目標(biāo)函數(shù)的Hessian矩陣是不定矩陣，這也是一個非凸-非凹的極大極小值問題.

(8)

針對上述提到的三種解決極大極小值問題的算法進行數(shù)值實驗，初始點為(1,1)點.GDA算法中步長γ1=γ2=0.3，OMD算法中步長η=0.15，ACA算法中步長α1=α2=0.3,β1=β2=0.1.

對比圖 1的結(jié)果可以看到，GDA算法在這個問題上呈現(xiàn)“循環(huán)”現(xiàn)象，無法收斂到(0,0)點，無法保證收斂性.而OMD算法避免了“循環(huán)”現(xiàn)象，能收斂到(0,0)點，保證了算法的收斂性.同樣地，ACA算法由于在GDA方法的基礎(chǔ)上加上了向心加速度項，也能避免這種“循環(huán)”現(xiàn)象.

2 學(xué)習(xí)步長算法

2.1 算法分析

由于GDA算法在問題的極大極小值問題上無法收斂，而OMD算法和ACA算法都能在該問題上收斂，于是對比這三種算法的迭代格式可以發(fā)現(xiàn)，OMD算法和ACA算法都選擇在GDA算法的基礎(chǔ)上，加上前一次迭代梯度方向的信息，不同之處在于這兩個算法的更新格式中，當(dāng)前梯度項和上一步梯度項的系數(shù)不一樣.在OMD算法中，當(dāng)前梯度項的系數(shù)是上一步梯度的兩倍，而ACA算法中則沒有對這兩項的系數(shù)關(guān)系有明確的規(guī)定,文獻([5]中作者通過手動調(diào)整這兩項的系數(shù)來適應(yīng)不同的任務(wù)).

(9)

從上述幾種優(yōu)化算法的簡述和對比中可以看出，優(yōu)化損失函數(shù)的算法大致上有兩個決定性因素:一是優(yōu)化方向，理想情況下，針對極小值問題，優(yōu)化方向一般選擇整個數(shù)據(jù)集計算的損失函數(shù)的負梯度方向，即全局梯度;第二個決定因素則是步長的選擇，步長在每次迭代的更新中也起著關(guān)鍵性作用.目前步長的選擇策略有很多，比如預(yù)先設(shè)定的步長策略，帶有衰減率的步長和自適應(yīng)步長等.雖然以上幾種步長策略可以在某些學(xué)習(xí)任務(wù)上有很好的表現(xiàn)，但在實踐中仍存在著不足.首先，這些策略需要手動預(yù)先指定步長或者步長的計算公式，但顯然這種策略在面對復(fù)雜問題時不夠靈活.其次，在解決新的問題時，總是需要手動調(diào)整預(yù)設(shè)的步長公式，并調(diào)整所涉及的超參數(shù)，這一過程往往會耗費大量的時間.這些不足都會影響這些步長策略在實際應(yīng)用中的應(yīng)用.

2.2 學(xué)習(xí)步長算法

基于上述分析，在式(9)的基礎(chǔ)上，本文提出了一種學(xué)習(xí)步長算法——LSA算法，在進行固定的迭代次數(shù)后，將當(dāng)前的目標(biāo)函數(shù)看作是關(guān)于步長的函數(shù)，即將步長為自變量來更新步長，達到動態(tài)，自動地更新，幾乎在每個更新步驟中都可以獲得最優(yōu)的步長.

算法流程如下：

算法1 學(xué)習(xí)步長算法(LSA算法)

-------------------------------------------

Fort=0 toTdo

更新參數(shù)

計算損失函數(shù)f=loss(xt+1,yt+1)

IftmodT0=0

更新步長(本文使用梯度下降法更新步長)

end

end

具體步驟如下：

2)訓(xùn)練損失函數(shù).選擇當(dāng)前迭代點到最優(yōu)值點(0,0)的歐式距離作為損失函數(shù)，根據(jù)式(9)來更新?lián)p失函數(shù)的梯度，得到每一次迭代損失函數(shù)的值.

3)更新步長.把上一步驟中得到的損失函數(shù)的和作為新的損失函數(shù)，將步長看作損失函數(shù)的自變量，每進行T0次迭代后，同樣使用梯度下降法更新步長，得到當(dāng)前的最優(yōu)步長.

按照上述步驟2)和步驟3)進行迭代后，此時步長已經(jīng)被更新，是根據(jù)當(dāng)前目標(biāo)函數(shù)得到的最優(yōu)步長.不斷循環(huán)這個過程，直到滿足終止條件.

3 數(shù)值實驗與分析

實驗在PC機上完成，PC機的配置如下：Intel Core i5，8GB內(nèi)存，Windows 10系統(tǒng).程序用Python編寫，運行環(huán)境為Python3.9.

首先構(gòu)造如下的二元二次函數(shù)族(10)和二元四次函數(shù)族(11)，

f(x,y)=c1x2-c2x2+c3xy

(10)

f(x,y)=d1x4-d2y4+d3x2-d4y2+d5xy

(11)

其中：ci,di∈,ci>0,di>0.注意，構(gòu)建的二次函數(shù)族和四次函數(shù)族需要滿足函數(shù)族中的每一個函數(shù)Hessian矩陣為不定矩陣，即是非凸非凹極大極小值問題，且函數(shù)保證都存在鞍點，且其中一個鞍點為(0,0)點，對應(yīng)的最優(yōu)值是0.見圖2.

圖2 在二次函數(shù)族上比較四種算法的性能Figure 2 Comparing the performance of the four algorithms on the quadric functions

圖 2分別比較了GDA算法，OMD算法，ACA算法和LSA算法的性能，實驗隨機選取了如式(10)的四個二次函數(shù)，取算法在這四個函數(shù)上的平均損失函數(shù)作為最終的損失函數(shù)loss，iter是迭代次數(shù).其中：學(xué)習(xí)步長算法的初始步長α0=0.3,β0=0.1，GDA算法的步長γ1=2γ2=0.3，OMD算法的步長η=0.15，ACA算法的步長α1=α2=0.3,β1=β2=0.1.對比可以看出，四種算法都可以將損失函數(shù)降低到接近最優(yōu)值，其中學(xué)習(xí)步長算法的收斂速度明顯快于其他三種算法.

圖3 在四次函數(shù)族上比較四種算法的性能.Figure 3 Comparing the performance of the four algorithms on the four power functions

圖3在四次函數(shù)上比較了四種算法的性能，實驗隨機選取了如式的四個四次函數(shù)，取算法在這四個函數(shù)上的平均損失函數(shù)作為最終的損失函數(shù).同樣地，其中：學(xué)習(xí)步長算法的初始步長α0=0.3,β0=0.1，GDA算法的步長γ1=2γ2=0.3，OMD算法的步長η=0.15，ACA算法的步長α1=α2=0.3,β1=β2=0.1.與其他三種算法進行對比，可以看出，四種算法都可以將損失函數(shù)降低到接近最優(yōu)值，其中學(xué)習(xí)步長算法的收斂速度明顯快于其他三種算法.

這兩個數(shù)據(jù)集上的實驗表明，在解決非凸-非凹的極大極小值問題上，GDA算法不能保證收斂性，而OMD算法，ACA算法和LSA算法都是能夠收斂的有效的算法.同時通過對比也可以看到，LSA算法相對有較快的收斂速度.

4 結(jié) 語

本文考慮解決極大極小值問題，分析了現(xiàn)有的解決此類問題的算法，包括GDA算法，OMD算法和ACA算法.在這些算法的啟發(fā)下，分析了基于梯度的算法中步長的選擇，提出了學(xué)習(xí)步長算法，即LSA算法，可以在訓(xùn)練任務(wù)的過程中動態(tài)地，自動地更新步長.并在構(gòu)造的二次函數(shù)集、四次函數(shù)集上進行了數(shù)值實驗，結(jié)果表明，學(xué)習(xí)步長算法LSA，是一種可以和GDA算法，OMD算法，ACA算法媲美的算法.