基于慣性動力系統(tǒng)的加速梯度算法

李 春 凱

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

近年來，優(yōu)化算法廣泛應(yīng)用于機器學習領(lǐng)域，對于求解大規(guī)模的問題，Hessian矩陣的計算和存儲成本大，因此一階梯度算法再一次回歸主流.對連續(xù)時間下的常微分方程(Ordinary differential equation，ODE)與離散迭代算法建立聯(lián)系，獲取加速梯度算法引起越來越多的關(guān)注.

本文針對二階的ODE 采用不同的離散格式，得到了加速梯度算法.

1 研究方法

本文考慮無約束最優(yōu)化問題：

(1)

其中：f是光滑的凸函數(shù).最基礎(chǔ)的一階梯度算法是梯度下降法(Gradient decent method，GD):

xk+1=xk-sf(xk),

(2)

其中:x0是初始點，s是步長.在一階優(yōu)化算法的框架下，是否存在改進GD收斂速率的算法是一個微妙而重要的問題.

1.1 動量方法

動量方法是指迭代過程中在僅使用一階梯度信息的基礎(chǔ)上加入前一步的迭代信息的一種方法.現(xiàn)代對于這種擴展的一階算法的研究可以追溯到Polyak[1-2]，他在GD 的基礎(chǔ)上加入動量項(xk-xk-1)，得到重球方法(Heavy-Ball):

yk+1=xk-sf(xk)，xk+1=yk+1-α(xk-xk-1)(3)

其中:α>0是動量系數(shù).重球方法在最小值附近比GD能獲得更快的局部收斂速率，但它通常并不能保證全局加速.而且Lessard[3]證明了即使對于強凸函數(shù)，由于步長的選擇，重球方法并不能保證收斂性.

另外一種重要的動量方法是Nesterov[4-5]提出的Nesterov加速梯度算法(Nesterov’s accelerated gradient algorithm，NAG),當目標函數(shù)f為強凸函數(shù)時，迭代形式為：

(4)

(5)

1.2 連續(xù)時間ODE

近年來，通過連續(xù)時間的ODE來分析加速梯度算法越來越受到人們的關(guān)注.特別是Su等人[6]表明，假設(shè)目標函數(shù)f為凸函數(shù)，當s→0時，NAG可收斂到一個關(guān)于時間t的連續(xù)時間ODE:

(6)

Su等人通過構(gòu)造合適的連續(xù)時間下的Lyapunov函數(shù)，證明了在連續(xù)時間下迭代點的加速收斂速率，進而佐證NAG具有加速收斂速率.

文獻[7-8]中Lagrangian和Hamiltonian框架被用來生成一大類連續(xù)時間的ODE，以便統(tǒng)一處理基于加速梯度的方法.但Wilson等人指出[8]，當f為強凸函數(shù)時，NAG對應(yīng)的ODE為:

(7)

重球方法對應(yīng)的ODE與式(7)相同，然而重球方法和NAG的迭代形式并不一樣，NAG的收斂速率更快且收斂性更好，因此并不能通過分析式(7)體現(xiàn)出NAG的優(yōu)勢.因此Shi等人[9]在計算ODE過程中提高精度，得到重球方法和NAG的高精度的ODE.值得注意的是，當f為強凸函數(shù)時，重球方法和NAG的高精度ODE是不同的，分別為：

(8)

(9)

1.3 離散化ODE

2 慣性動力系統(tǒng)

‖f(y)-f(x)‖≤L‖y-x‖

當目標函數(shù)f為強凸函數(shù)時，重球方法對應(yīng)的高精度ODE(8)和NAG對應(yīng)的高精度ODE(9)都可以看作是Attouch文中[14]中特殊形式的Hessian-driven慣性動力系統(tǒng):

(10)

對該連續(xù)時間系統(tǒng)離散化，可以得到一系列的優(yōu)化算法.系統(tǒng)中包含的Hessian項可以看作是f(X(t))對t的導(dǎo)數(shù)，正好對應(yīng)到NAG中函數(shù)梯度差.

在優(yōu)化問題中，Polyak[12]首先利用慣性動力學使梯度法獲得加速收斂速率，即帶有摩擦系數(shù)的連續(xù)時間下的重球方法(HBF)：

(11)

其中：阻尼系數(shù)γ>0，由于很難取到合適的γ，且在一些優(yōu)化問題中，收斂性并不好.Alvare[15]受連續(xù)時間牛頓方法啟發(fā)，引入Hessian項，得到類牛頓的慣性動力系統(tǒng)(Dynamic inertial system，(DIN)γ,β)：

(12)

(13)

本文的目的是通過不同的離散格式對式(13)離散化，得到優(yōu)化算法，并證明定理1中的指數(shù)收斂速率可轉(zhuǎn)換為離散迭代格式下的線性收斂速率.

3 新的優(yōu)化算法

采用三種離散格式：辛格式，顯示Euler，隱式Euler對上述微分方程離散化，得到三種優(yōu)化算法.

3.1 辛格式優(yōu)化算法

第一種離散格式是辛格式，近似規(guī)則如下:

由辛格式離散ODE(13)可得優(yōu)化算法：

證明設(shè)Lyapunov函數(shù)為：

已知

f(xk+1)-f(xk)≤〈f(xk+1),xk+1-xk〉-

2x*)+vk+1+vk+β(f(xk+1)+f(xk))〉-

2x*)+vk+1+vk+β(f(xk+1)+f(xk))〉-

2x*)+vk+1+vk+β(f(xk+1)+f(xk))〉-

已知以下兩個等式

和

顯然成立，所以

因為目標函數(shù)為強凸函數(shù)，所以滿足

因此可得：

由假設(shè)可知

根據(jù)強凸性質(zhì)

所以

由Cauchy-Schwarz不等式，可知

βf(xk)‖2≤

成立.所以

3.2 顯式Euler優(yōu)化算法

第二種離散格式是顯式Euler格式，近似規(guī)則如下:

由顯式Euler格式離散ODE(13)可得優(yōu)化算法：

證明設(shè)Lyapunov函數(shù)為：

βf(xk)‖2+f(xk)-f(x*)

<1)，且各件產(chǎn)品是否為不合格品相互獨立．

vk+1+vk+β(f(xk+1)+f(xk))〉≤

根據(jù)Cauchy-Schwarz不等式以及f為強凸函數(shù)，以下兩個不等式

和

成立，因此

利用Cauchy-Schwarz不等式得：

x*‖2+‖vk‖2+β2‖f(xk)‖2)

又因為f為強凸函數(shù)，所以有：

因此

3.3 隱式Euler優(yōu)化算法

另一種格式是隱式Euler格式，近似規(guī)則如下：

2f(xk+1)vk+1≈f(xk+1)-f(xk)

由隱式Euler格式離散ODE(13)可得優(yōu)化算法：

證明設(shè)Lyapunov函數(shù)為：

βf(xk)‖2+f(xk)-f(x*)

vk+1+vk+β(f(xk+1+f(xk))〉≤

根據(jù)Cauchy-Schwarz不等式

3μ‖xk+1-x*‖2+f(xk+1)-f(x*)

4 結(jié) 語

本文主要是通過離散連續(xù)時間下的慣性動力系統(tǒng)得到加速梯度算法.具體是通過三種不同的離散格式：辛格式、顯式Euler和隱式Euler對該動力系統(tǒng)進行離散后得到三種優(yōu)化算法，并證明了當目標函數(shù)是強凸函數(shù)時，由辛格式以及隱式Euler離散慣性動力系統(tǒng)(13)得到的的優(yōu)化算法能夠?qū)崿F(xiàn)與文獻[13]中相同的加速收斂速率.