0
雷鋒網(wǎng) AI 科技評論按：Michael Jordan 教授是機器學(xué)習(xí)領(lǐng)域神經(jīng)網(wǎng)絡(luò)的大牛，發(fā)表過很多神經(jīng)網(wǎng)絡(luò)方面的學(xué)術(shù)論文。雷鋒網(wǎng) AI 科技評論整理了公開發(fā)表在伯克利博客上的一篇機器學(xué)習(xí)領(lǐng)域的學(xué)術(shù)性文章，作者 Chi Jin、Michael Jordan 。
原文地址鏈接：http://bair.berkeley.edu/blog/2017/08/31/saddle-efficiency/
在機器學(xué)習(xí)領(lǐng)域中，非凸優(yōu)化中的一個核心問題是鞍點的逃逸問題。最近關(guān)于這個方面的研究表明，梯度下降法（GD，Gradient Descent）一般可以漸近地逃離鞍點（詳見 Rong Ge 和 Ben Recht 的相關(guān)論文），但是還有一個未解決的問題——效率，即梯度下降法是否可以加速逃離鞍點，還是反而速度明顯地降低了？逃逸率和環(huán)境維度的關(guān)系是怎樣的？那么，這篇文章將會就涵蓋這些問題，描述 Chi Jin 與 Michael Jordan 在與 Rong Ge，Praneeth Netrapalli 以及 Sham Kakade 合作的相關(guān)成果。效率方面，他們首次公開了梯度下降法在效率問題上的正面表現(xiàn)；令人驚訝的是，使用合理的擾動參數(shù)增強的梯度下降法可有效地逃離鞍點；實際上，rate 和 dimension 上的結(jié)果幾乎看不出任何鞍點存在的痕跡。
在經(jīng)典的梯度下降（GD）領(lǐng)域——假設(shè)函數(shù)
，我們要在負梯度方向最小化函數(shù)f：
這里 xt 是需優(yōu)化變量在第t步的值，η 是步長。梯度下降法的理論研究在凸優(yōu)化上已經(jīng)很充分了，但是在非凸優(yōu)化情況下就少了很多。我們知道，在非凸情況下，GD 會快速收斂到駐點（
附近的點），但是這些穩(wěn)定的點可能是局部極小點或者是沒用的局部最大點或者甚至是鞍點。
顯然，如果駐點是起點，GD 是不可能逃離這個起始點的（就算起始點是局部最大點也一樣）；因此，為了實現(xiàn)GD的作用，我們需要稍稍調(diào)整一下 GD，增加一些隨機變量。目前已經(jīng)有了兩種方法：
1. 間歇性擾動：Ge/Huang/Jin/Yuan在2015年提出了《Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition》，增加偶爾的隨機擾動，并提供了逃離鞍點的多項式時間保證。（亦見Rong Ge的博客）；
2. 隨機初始化：Lee等人在2016年提出《Gradient Descent Converges to Minimizers》，進使用隨機初始化的方法，GD也可漸近地逃離鞍點（但是實現(xiàn)步驟趨向無窮大）（見Ben Recht的博客）。
漸進——甚至多項式時的結(jié)果對一般的理論研究來說是重要的，但這兩點不能解釋基于梯度算法在實際非凸問題中的成功。它們既不能證明 GD 的運行是可靠的——我們發(fā)現(xiàn)自己無法處于一種狀態(tài)中，即學(xué)習(xí)曲線趨于平緩一段時間（無法定義時間的長度），但是用戶無法知道漸近是否已經(jīng)開始了。它們也不能證明 GD 具有在高維度中的良好性質(zhì)，這一點在凸優(yōu)化中是已知的。
解決這個問題的一個合理的辦法是考慮二階算法（Hessian-based）。盡管這些算法一般在一次迭代中的成本遠比 GD 高，也比 GD 執(zhí)行起來更加復(fù)雜，但是它們確實提供了可有效地逃離鞍點所需的鞍點的幾何信息。因此，文獻中出現(xiàn)了對 Hessian-based 的算法合理解釋，并且使用這種算法已經(jīng)取得了切實有效的結(jié)果。
如果考慮隨機初始化策略，基于第一個問題則出現(xiàn)了一個反面的結(jié)果。總的來說，GD是低效的，尤其在最壞情況下花費冪指數(shù)的時間來逃離鞍點（詳見后文“增加擾動的必要性”部分）。
但是如果我們考慮擾動策略，神奇的是，結(jié)果竟大不相同。為了清楚的陳述這個結(jié)果，我們使用如下的算法進行分析：
這里，擾動參數(shù) 
從一個適當?shù)陌霃椒秶鷥?nèi)，以一個中心為零的球均勻采樣，并當梯度適當時，擾動會被加入到迭代中。這些特殊的選擇是為了便于分析；我們不認為均勻的噪聲是必要的；也不認為噪聲必須要在梯度值很小時才能加。
在這篇文章中，我們定義鞍點，既包括經(jīng)典鞍點，也包括局部極大值。它們是沿著至少一個方向在局部最大化的駐點。鞍點和局部極小值可以根據(jù) Hessian 的最小特征值來分類：
我們將上述情況中
<0 的鞍點稱為嚴格鞍點（strict paddle points）。
盡管非嚴格鞍點在谷底可以是平坦的，但是嚴格鞍點需要在至少一個方向上的曲率嚴格為負。這樣的方向的存在則給基于梯度的算法逃離鞍點的可能性。一般來說，區(qū)分局部極小和非嚴格鞍點是 NP-hard 的；因此，我們，也包括之前這方面的學(xué)者們，都會把注意力放在逃離嚴格鞍點上。
形式上，我們就光滑度提出以下兩個標準假設(shè)：
傳統(tǒng)理論是通過限定迭代次數(shù)找到一階駐點
的速度，研究收斂至?-一階駐點（
）的所需步數(shù)，我們的理論與之類似，即按照如下設(shè)定，規(guī)劃嚴格鞍點的逃離速度并隨后收斂到二階駐點
>=0，并找到?-弱化版本所需步數(shù)。
在這個定義中，ρ 是Hessian Lipschitz常數(shù)。這個定標是根據(jù)Nesterov and Polyak 2016公約設(shè)定的。
在大多數(shù)的非凸問題中，已經(jīng)證實所有的鞍點都是嚴格鞍點——這些非凸問題包括，但不僅限于principal components analysis, canonical correlation analysis, orthogonal tensor decomposition, phase retrieval, dictionary learning, matrix sensing, matrix completion等其他非凸低秩問題。
此外，在所有這些非凸問題中，所有的局部極小值事實上也是全局極小值。因此，在這種情況下，所有尋找-二階駐點的問題立即成為解決這些非凸問題的全局保證。
在經(jīng)典的一階駐點情況下，GD具有很好的理論性質(zhì)： 
在這個定理中，x0是初始點，f? 是全局極小值的函數(shù)。定理規(guī)定任何gradient-Lipschitz函數(shù)，任何駐點都可以通過GD在第O(1/?2) 次獲得，不受d 的影響，這就是所謂的“自由尺寸優(yōu)化”。對一個GD的成本計算為 O(d)，因此整體的運行時間為 O(d)的階。 O(d)這樣線性scaling對現(xiàn)代高維非凸問題（比如深度學(xué)習(xí)）來說是非常重要的。
那么，我們將同樣的方法應(yīng)用到二階駐點的問題上。我們可以得到什么樣的結(jié)論呢？我們是否也可以像之前一樣實現(xiàn)：
1. 一個無維數(shù)的迭代次數(shù)；
2. O(1/?2)的收斂速度；
3. 對 ? 和 (f(x0)?f?)的依賴與Nesterov 1998中的結(jié)果相同；
結(jié)果是出人意料的，對這三個問題的答案都是Yes。 
主要定理中，O~(?) 只隱藏了對數(shù)因子；這邊對維度的依賴只有l(wèi)og4(d).。定理證明，在一個額外增加的Hessian-Lipschitz條件下，增加擾動的GD收斂到二階駐點的時間和GD收斂到一階駐點的時間幾乎是一樣的。因此，我們可以得出結(jié)論，PGD可以無消耗的逃離鞍點。
下面我們討論一下得出這個結(jié)論所必須的幾個關(guān)鍵點。
我們關(guān)于嚴格鞍點的假設(shè)是，在最壞的情況下，逃離鞍點在d維度上只能沿著一個方向?qū)崿F(xiàn)。一般的鞍點逃逸在梯度下降的方向上至少需要 poly(d)次迭代，那么 polylog(d)次真的就足夠了嗎？
舉個簡單的例子，假設(shè)一個函數(shù)在鞍點附近是二次的。那么目標函數(shù)假定為
，鞍點在0，且Hessian 
在這種情況下，只有第一個方向是逃離鞍點的方向（負特征值-1）。
迭代次數(shù)的推導(dǎo)是很直接的：
假設(shè)我們的起始點是0，那么增加擾動后，從一個以0為圓心半徑為1的球
均勻的采樣。函數(shù)遞減可以表現(xiàn)為：
將迭代次數(shù)設(shè)置為 1/2，λi 將作為 Hessian H 的 第 i 個本征值，并將
設(shè)置為起始點 x0在第i個方向上的參數(shù)。同時
，于是：
可以得出結(jié)論，如果要讓函數(shù)值減少一定常量，最多進行 O(log d) 次迭代。
我們可以得出這樣的結(jié)論：一個恒定的Hessian矩陣的情況下，只有當擾動處x0在集合
的情況下，我們才會需要花費很長的時間避開鞍點。我們稱這個區(qū)域為限制區(qū)域；在這種情況下，可以看見，這個區(qū)域是一個圓盤狀的。一般來說，當Hessian不再是一個恒定值時，限制區(qū)域也就不是一個圓盤狀的了，會像下方左圖中的一樣。這個區(qū)域很難用公式來表達。
以前的學(xué)術(shù)分析試圖用一個平面集來逼近鞍點附近的動態(tài)范圍的限制區(qū)域。這需要非常小的步長和相應(yīng)的非常大的運行時間和復(fù)雜度。我們的速度則非?？?，這取決于一個關(guān)鍵的因素——雖然我們不知道限制區(qū)域的形狀，但是我們知道，這個限制區(qū)域很薄。 
為了量化這個“薄”的概念，我們假設(shè)兩個擾動參數(shù) 
，由 
分離并且沿著逃離的方向。如果我們從 
開始運行 GD ，至少有一個軌跡可以很快的脫離鞍點。這意味著限制區(qū)域的厚度最大為 
，因此，隨機擾動落在限制區(qū)域內(nèi)的幾率是非常小的。
以上我們已經(jīng)討論了兩種方法來修改標準的梯度下降算法了，第一種是增加間歇性的擾動，第二種是依靠隨機初始化。雖然后者具備漸近收斂性，但是它需要耗費大量的時間和資源，犧牲了有效性；在近期與 Simon Du，Jason Lee, Barnabas Poczos 和 Aarti Singh 的合作中，我們已經(jīng)展現(xiàn)出，盡管使用非常自然的隨機初始化方法和非病理函數(shù)，僅僅使用隨機初始化的 GD 會因為鞍點大大降低效率，需要非常長的時間才能實現(xiàn)鞍點逃離。而 PGD 的表現(xiàn)卻非常不同，它一般可以在多項式的時間內(nèi)逃離鞍點。
為了更好的解釋這個結(jié)果，我們使用包括高斯（Gaussians）和均勻分布的超立方體來進行隨機初始化，同時我們構(gòu)建一個光滑的目標函數(shù)，滿足假設(shè) 1 和 2。這個函數(shù)被設(shè)計成即使隨機初始化，在很大概率上 GD 和 PGD 在達到局部極小值之前都需要依次經(jīng)過 d 范圍內(nèi)的嚴格鞍點。所有的嚴格鞍點都只有一個逃逸方向（見下方左圖，d=2）
當 GD 在一系列鞍點附近移動時，它會越來越接近后面一個鞍點，因此需要越來越長的時間實現(xiàn)逃逸。逃逸的時間抽象為：逃離第 i 個鞍點的時間為。另一方面，PGD 始終可以在很少的迭代時間內(nèi)實現(xiàn)逃逸，不管之前的逃逸過程是怎么樣的。這個過程在我們的實驗中得到了驗證，見上方右圖，d=10。
在這篇文章中，我們證明了一個擾動形式的梯度下降可以收斂到二階駐點，其使用的時間與標準的梯度下降收斂到一階駐點的時間幾乎相同。這意味著，在有效地逃離鞍點的問題上，Hessian 信息是不必要的。同時，這還解釋了在非凸問題上基本的 GD 和 SGD 表現(xiàn)的出奇的好的原因。這一新的收斂結(jié)果可以直接應(yīng)用于非凸問題，如 matrix sensing/completion 來進行有效地全局收斂。
當然，在非凸優(yōu)化領(lǐng)域，還存在著許多懸而未決的問題。舉幾個例子：加入動量會使收斂到一個二階駐點的速度提高？什么類型的局部極小值可用，并且是否存在一些有用的結(jié)構(gòu)性假設(shè)可以讓我們有效地應(yīng)用在局部極小值上，從而避免局部極小值？在非凸優(yōu)化問題上我們正在緩慢而穩(wěn)步地取得這進展，在不久的將來，我們可以真正實現(xiàn)「科學(xué)」的跨越。
雷鋒網(wǎng) AI 科技評論編譯
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
