非凸函數(shù)上，隨機梯度下降能否收斂？網(wǎng)友熱議：能，但有條件，且比凸函數(shù)收斂更難

非凸優(yōu)化問題被認(rèn)為是非常難求解的，因為可行域集合可能存在無數(shù)個局部最優(yōu)點，通常求解全局最優(yōu)的算法復(fù)雜度是指數(shù)級的（NP 困難）。那么隨機梯度下降能否收斂于非凸函數(shù)？針對這一問題，眾多網(wǎng)友進行了一番討論。

在機器學(xué)習(xí)領(lǐng)域，我們經(jīng)常會聽到凸函數(shù)和非凸函數(shù)，簡單來講，凸函數(shù)指的是順著梯度方向走，函數(shù)能得到最優(yōu)解 ，大部分傳統(tǒng)機器學(xué)習(xí)問題都是凸的。而非凸指的是順著梯度方向走能夠保證是局部最優(yōu)，但不能保證是全局最優(yōu)，深度學(xué)習(xí)以及小部分傳統(tǒng)機器學(xué)習(xí)問題都是非凸的。

在尋求最優(yōu)解的過程中，研究者通常采用梯度下降算法。近日，reddit 上的一個熱議帖子，帖子內(nèi)容為「隨機梯度下降能否收斂于非凸函數(shù)？」

原貼內(nèi)容包括：大量的研究和工作表明梯度下降算法可以收斂于（確定性）凸函數(shù)、可微和利普希茨連續(xù)函數(shù)：

然而，在非凸函數(shù)領(lǐng)域，基于梯度下降算法（例如隨機梯度下降）的收斂程度有多大，目前看來研究還不夠充分。例如，神經(jīng)網(wǎng)絡(luò)中的損失函數(shù)幾乎是非凸的。非凸函數(shù)通常有鞍點（即損失函數(shù)的一階導(dǎo)數(shù)為 0 的點），我們可以將這些鞍點視為「陷阱」，鞍點的存在阻止梯度下降到最優(yōu)點，因為梯度下降在導(dǎo)數(shù)為 0 時不能向前移動。

兩座山中間的鞍點（雙紐線的交叉點）

在機器學(xué)習(xí)、深度學(xué)習(xí)中使用的優(yōu)化算法除了常見的梯度下降和隨機梯度下降，還包括其他版本，例如 Nesterov 動量、Adam、RMSprop 等幾種優(yōu)化器，這些優(yōu)化器旨在讓梯度遠(yuǎn)離鞍點。對于這些算法，發(fā)帖者很熟悉，但 ta 比較感興趣的是隨機梯度下降算法本身的理論局限性有哪些？

在過去的幾周里，發(fā)帖人一直在閱讀有關(guān)這個主題的文章，但是理解其中一些結(jié)果所需的數(shù)學(xué)知識遠(yuǎn)遠(yuǎn)超出了 ta 的能力范圍。為了弄清這個問題，ta 也查閱了大量的文獻(xiàn)，以下是其中 2 篇：

文獻(xiàn) 1：Stochastic Gradient Descent for Nonconvex Learning without Bounded Gradient Assumptions

隨機梯度下降被大量應(yīng)用于非凸函數(shù)，但研究者對非凸函數(shù)的隨機梯度下降的理論尚未完全了解（目前僅對凸函數(shù)的隨機梯度下降有了解）；

現(xiàn)階段隨機梯度下降要求對梯度的一致有界性施加一個假設(shè)；

論文作者建立了非凸函數(shù)隨機梯度下降理論基礎(chǔ)，使有界假設(shè)可以消除而不影響收斂速度；

論文建立了應(yīng)用于非凸函數(shù)隨機梯度下降收斂的充分條件和最優(yōu)收斂速度。

文獻(xiàn) 2 ：Stochastic Gradient Descent on Nonconvex Functions with General Noise Models

盡管隨機梯度下降的最新進展值得注意，但這些進展是建立在對正在優(yōu)化的函數(shù)施加了某些限制（例如，凸性、全局利普希茨連續(xù)等）的基礎(chǔ)之上；

作者證明，對于一般類的非凸函數(shù)，隨機梯度下降迭代要么發(fā)散到無窮大，要么收斂到概率為 1 的靜止點；

作者進一步限制并證明，無論迭代是發(fā)散還是保持有限 —— 在隨機梯度下降的迭代中評估的梯度函數(shù)的范數(shù)以概率 1 收斂到零，并且符合預(yù)期；從而擴大了隨機梯度下降可以應(yīng)用于的函數(shù)范圍，同時保持對其全局行為的嚴(yán)格保證。

發(fā)帖人表示：基于這些文獻(xiàn)，我們是否真的能夠證明（隨機）梯度下降有潛力在非凸函數(shù)上顯示類似的全局收斂性質(zhì)，達(dá)到之前僅在凸函數(shù)上顯示收斂程度？

但是我們?nèi)匀挥欣碛上嘈牛S機）梯度下降與凸函數(shù)相比在非凸函數(shù)上收斂更困難。

網(wǎng)友：問題改成「梯度下降在什么條件下會收斂于非凸函數(shù)」更好

針對發(fā)帖者的這一問題 —— 隨機梯度下降能否收斂于非凸函數(shù)？網(wǎng)友紛紛從自身經(jīng)驗進行解答。機器之心從中挑選出了幾個獲贊較多的回復(fù)。

首先來看網(wǎng)友 @anonymousTestPoster 的回答。ta 表示，假設(shè)存在一個表現(xiàn)良好的非凸函數(shù)，可以參見 Issam Laradji 撰寫的《非凸優(yōu)化》文檔。

地址：https://www.cs.ubc.ca/labs/lci/mlrg/slides/non_convex_optimization.pdf

如果存在向下延伸至 Hessian 矩陣的 Lipschitz 連續(xù)性限制，則文檔 19 頁中的 Thm 似乎表明可以不斷取得進展以接近頂點。

如果想要更復(fù)雜的函數(shù)，則幾乎可以肯定需要的函數(shù)是可微的或者利普希茨連續(xù)，否則只能選擇一些處處連續(xù)、無處可微的瘋狂函數(shù)（crazy function），例如 Weierstrass 函數(shù)。

所以，關(guān)于「隨機梯度下降能否收斂于非凸函數(shù)」這一問題，ta 認(rèn)為在某些條件下「會」，因為很多非凸函數(shù)可能擾亂可微性。在提出反例時，永遠(yuǎn)不要低估數(shù)學(xué)家的想象力。

所以，ta 建議發(fā)帖者將問題改成「梯度下降在什么條件下會收斂于某類非凸函數(shù)」，然后將每類函數(shù)作為子問題進行研究，并消除打破傳統(tǒng)梯度下降方法的非凸函數(shù)反例。

接著來看網(wǎng)友 @astone977 指出了原貼內(nèi)容中存在的一些問題。ta 表示，當(dāng)發(fā)帖者認(rèn)為神經(jīng)網(wǎng)絡(luò)的誤差表面是非凸時，則損失函數(shù)也是非凸的。但是，MSE 等損失函數(shù)是凸函數(shù)。將一個非凸映射（神經(jīng)網(wǎng)絡(luò)）應(yīng)用于一個損失函數(shù)的輸入，可以創(chuàng)建一個非凸誤差表面。

如果我們將 MSE、BCE 等凸函數(shù)稱為損失函數(shù)，那么不應(yīng)該使用相同的術(shù)語來描述一個神經(jīng)網(wǎng)絡(luò)的非凸誤差表面。這在過去一直是造成混亂的根源，所以 ta 指了出來。

最后，網(wǎng)友 @Funktapus 也表示，如果發(fā)帖者只是在討論優(yōu)化期間避免局部最小值，則這是優(yōu)化領(lǐng)域一個普遍且非常古老的問題。通常而言，答案是「會」。

我們可以使用隨機方法來跳出小的局部最小值。蒙特?卡羅方法（Monte Carlo）是一種經(jīng)典的方法。另一種方法是在開始梯度下降之前建立一個網(wǎng)格并找出全局最小值的大區(qū)域。

大家如何看待這個問題呢？感興趣的小伙伴請在留言區(qū)積極發(fā)言。

參考鏈接：https://www.reddit.com/r/MachineLearning/comments/slnvzw/d_can_stochastic_gradient_descent_converge_on/