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