全局最優解？為什麼SGD能令神經網路的損失降到零

選自arXiv

機器之心編譯

參與：思源

昨日，reddit 上一篇帖子引發熱議，該帖介紹了一篇關於梯度下降對過參數化神經網路影響的論文，該論文只用單個非常寬的隱藏層，並證明了在一定條件下神經網路能收斂到非凸優化的全局最優解。這是對深度學習的復古？到底是否有效？社區中很多人對此發表了看法。機器之心簡要介紹了該論文，更詳細的推導過程與方法請查看原論文，不過這樣的證明讀者們都 Hold 住嗎。

用一階方法訓練的神經網路已經對很多應用產生了顯著影響，但其理論特性卻依然成謎。一個經驗觀察是，即使優化目標函數是非凸和非平滑的，隨機初始化的一階方法（如隨機梯度下降）仍然可以找到全局最小值（訓練損失接近為零）。令人驚訝的是，這個特性與標籤無關。在 Zhang 等人的論文 [2016] 中，作者用隨機生成的標籤取代了真正的標籤，但仍發現隨機初始化的一階方法總能達到零訓練損失。

關於神經網路為什麼能適應所有訓練標籤，人們普遍認為是因為神經網路過參數化了。例如，Wide ResNet [Zagoruyko and Komodakis] 使用的參數數量是訓練數據的 100 倍，因此必須存在一個這種架構的神經網路，能夠適應所有訓練數據。然而，這並不能說明為什麼由隨機初始化的一階方法找到的神經網路能夠適應所有數據。目標函數是非凸和非平滑的，這使得傳統的凸優化分析技術在這種情況下沒有用。據我們所知，理論只能保證現有的方法收斂到一個駐點 [Davis et al., 2018]。

在本文中，作者將解釋這一令人驚訝的現象，即帶有修正線性單元（ReLU）激活函數的兩層神經網路能收斂到全局最優解。形式化的，我們可以考慮有以下形式的神經網路：

其中 x ∈ R^d 為 d 維實數向量輸入，w_r ∈ R^d 為第一層的權重向量，a_r ∈ R 為輸出權重。此外，σ (·) 表示 ReLU 激活函數：σ (z) = z if z ≥ 0、 σ (z) = 0 if z

隨後我們可以根據二次損失函數（歐式距離）定義經驗風險最小化問題，若給定 n 筆數據的訓練集 {(x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n) }，我們希望最小化：

為了實現經驗風險最小化，我們需要修正第二層並針對第一層的權重矩陣應用梯度下降（GD）：

其中η > 0 為學習率（在本論文中為步長），因此每一個權重向量的梯度計算式可以表示為：

儘管這只是一個淺層全連接網路，但由於使用了 ReLU 激活函數，目標函數仍然是非凸和不平滑的。不過即使針對這樣簡單的目標函數，為什麼隨機初始化的一階梯度方法能實現零的訓練誤差仍然不太清楚。實際上，許多先前的研究工作都在嘗試回答這個問題。他們嘗試的方法包括損失函數面貌分析、偏微分方程、演算法動力學分析或最優傳輸理論等。這些方法或研究結果通常都依賴於標籤和輸入分布的強假設，或者並沒有明示為什麼隨機初始化的一階方法能實現零的訓練損失。

在這一篇論文中，作者們嚴格證明了只要 m 足夠大，且數據是非退化的，那麼使用適當隨機初始化的 a 和 W(0)，梯度下降能收斂到全局最優解，且收斂速度對於二次損失函數是線性的。線性速率也就是說模型能在 K = O(log (1/ε)) 次迭代內搜索到最優解 W(k)，它能令 L(W(K)) ≤ ε。因此，作者理論結果並不僅僅展示了全局收斂性，同時還為達到期望的準確率提供了量化的收斂率。

分析技術概覽：

首先作者直接分析了每一次獨立預測的動力學特徵，即 f(W, a, x_i) for i = 1, . . . , n。他們發現預測空間的動力學是由格拉姆矩陣（Gram matrix）譜屬性決定的，且只要格拉姆矩陣的最小特徵值是下界，那麼梯度下降就服從線性收斂速度。

其次作者觀察到格拉姆矩陣僅和激活模式相關（ReLU 輸入大於零的情況），因此他們就能使用矩陣微擾分析探索是否大多數的模式並沒有改變，因此格拉姆矩陣仍然接近於初始化狀態。

最後作者發現過參數化、隨機初始化和線性收斂聯合限制了權重向量 w_r 仍然接近於初始值。

最後作者根據這三個觀察結果與方法嚴格證明了他們的論點，此外他們還表示整個證明僅使用了線性代數與標準概率邊界，因此能推廣到其它深度神經網路。以下我們展示了他們證明出的兩個定理（Theorem 3.1 和 Theorem 4.1），證明過程請查閱原論文。

論文：Gradient Descent Provably Optimizes Over-parameterized Neural Networks

論文鏈接：https://arxiv.org/abs/1810.02054

摘要：神經網路一個最神秘的地方是梯度下降等隨機初始化的一階優化方法能實現零的訓練損失，即使目標函數是非凸和不平滑的。本論文揭秘了這一現象，即帶有 ReLU 激活函數的兩層全連接網路為什麼能實現零的訓練損失。對於有 m 個隱藏神經元的淺層神經網路（ReLU 激活函數）和 n 項訓練數據，我們的實驗表示只要 m 足夠大，且數據是非退化的，那麼隨機初始化的梯度下降能收斂到全局最優解，且收斂速度對於二次損失函數是線性的。

我們的分析基於以下觀察：過參數化和隨機初始化聯合限制了每一個權重向量在所有迭代中都接近於它的初始值，這令我們可以利用比較強的類凸屬性，並展示梯度下降能以全局線性的速率收斂到全局最優解。我們相信這些觀點同樣能用於分析深度模型和其它一階梯度優化方法。

3 連續型時間分析

本章展示了分析梯度流（gradient flow）的結果，即將步長設置為無窮小量的梯度下降。在後一部分的離散型時間分析中，我們將進一步修正這一部分的證明，並為帶正下降步長的梯度下降設定一個定量邊界。

形式化而言，我們考慮常微分方程，公式如下所示：

其中 r 屬於 1 到 m。我們將 u_i(t) = f(W(t), a, x_i) 指定為輸入 x_i 在時間 t 上的預測，u(t) = (u_1(t), . . . , u_n(t)) ∈ R^n 指定為時間 t 上的預測向量。本章的主要結果見以下定理：

4 離散型時間分析

本章展示了具有正常數項步長的隨機初始化梯度下降以線性速率收斂到全局最小值。我們首先介紹主要定理：

定理 4.1 表明，即使目標函數是非平滑和非凸的，具有正常數步長的梯度下降仍然具有線性收斂速度。我們對最小特徵值和隱藏節點數的假設與梯度流定理完全相同。值得注意的是，與之前的研究 [Li and Liang, 2018] 相比，我們對步長的選擇與隱藏節點 m 的數量無關。

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

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

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！