機器之心報道

　　機器之心編輯部

　　數天前，機器之心發佈了 Simon S. Du 等人的論文《Gradient Descent Finds Global Minima of Deep Neural Networks》引起了大家激烈的討論。對此論文，讀者們褒貶不一。此外，機器之心通過讀者留言瞭解到微軟研究院 Zeyuan Allen-Zhu、斯坦福 Yuanzhi Li、德州大學奧斯汀分校 Zhao Song（共同一作）稍微早些時候也發佈了一篇類似的論文，但有更好的結果。後經溝通聯繫，機器之心對微軟的這篇論文進行了跟進報道，希望能爲讀者提供更全面的內容參考，更好的理解兩篇論文。

　　在細緻解讀微軟研究院的這篇論文之前，讀者們可以先了解下微軟這篇論文與 Simon S. Du 等人論文的對比（詳見微軟這篇論文的第二頁）。

　　最重要的區別是，Simon Du 等人證明了全連接深度網絡（非 ResNet）的收斂時間關於層數 L 的依賴是不超過指數級別 2^O(L) 的，而殘差網絡（ResNet）是多項式級別 poly(L) 的。Simon Du 等人因此給出理論依據，判斷 ResNet 的收斂性更好。本文作者指出，這樣的推斷是邏輯錯誤的，因爲本文證明了全連接網絡也同樣在多項式級別 poly(L) 時間內收斂（所以 Simon Du 等人文中的「不超過指數」，其實是和殘差網絡一樣的多項式）。也就是說，ResNet 相對於非 ResNet 的優勢，實際上有更深層的原因，而不是像 Simons Du 文章裏聲稱的，是指數和多項式的區別。兩篇文章的其它的區別包括，Simon Du 等的人的結果，隱藏了其它的可能指數級別的參數，以及 Simon Du 的結果不能處理最常用的 ReLU 激活函數，等等。

　　微軟的這篇論文是基於 [Li-Liang 2018] 在今年 NIPS 2018 上發表的一個深度延伸。Li 和 Liang 證明了只有一個隱藏層的神經網絡，在過參數化的情況下可以找到全局最優。至於多層網絡，需要開發更多的理論技術。一個具體的例子是這樣的。假設訓練數據不退化（相對距離爲δ），那麼如何證明數據傳遞到了最後一層，也不會發生退化？這篇論文證明了，只要過參數化（引理 4.5），那麼樣本傳遞到最後一層，相對距離依然可以有δ\/2。

　　下面是對微軟研究院這篇論文的技術介紹：

　　論文：A Convergence Theory for Deep Learning via Over-Parameterization

　　論文https://arxiv.org/pdf/1811.03962.pdf

　　摘要：深層神經網絡（DNN）已在許多領域表現出主導性能；自 AlexNet 以來，實踐中使用的神經網絡越來越深，越來越寬。然而在理論方面，前人大部分的工作在關注爲什麼我們可以訓練只有一個隱藏層的神經網絡。多層網絡的理論仍然不明確。

　　在這項工作中，我們證明了爲什麼常用的算法，比如隨機梯度下降（SGD），可以在多項式時間內找到 DNN 訓練的全局最優解。我們只做兩個假設：輸入數據不退化，和網絡過參數化。前者意味着輸入不存在兩個相同的數據點有矛盾的標籤；後者意味着隱藏神經元的數量足夠多，也就是關於層數 L，以及樣本數量 n 都是多項式級別。

　　作爲一個具體示例，在訓練集上從隨機初始的權重開始，我們證明了在關於 n 和 L 的多項式時間內，SGD 就可以在分類任務中達到了 100％的準確率，也就是找到全局最優解。我們的理論可適用於最常用的 ReLU 激活函數，適用於任何光滑甚至非凸的損失函數。在網絡架構方面，我們的理論至少可以適用於全連接網絡，卷積網絡（CNN）和殘差網絡（ResNet）。

　　神經網絡在衆多機器學習任務中取得了巨大成功。其中一項實驗結果表明，通過隨機初始化的一階方法訓練的神經網絡，具有非常強的擬合訓練數據的能力。從容量的角度來看，擬合訓練數據的能力可能並不令人驚訝：現代神經網絡總是過參數化，它們具有遠多於訓練樣本總數的參數。因此，理論上，只要數據不退化，總會存在實現零訓練誤差的參數選擇。

　　然而，從優化的角度來看，一階方法可以在訓練數據上找到全局最優解這事情「非常不簡單」。大家常用的神經網絡通常配備 ReLU 激活函數，這使得神經網絡不僅是非凸的，甚至非光滑。與之相對的是，優化理論中，如何找到非凸、非平滑函數的哪怕是一階、二階臨界點的收斂性也是不明確的 [Burke, 2005]，更不用提全局最優解。那麼，實際訓練中，隨機梯度下降法（SGD）是如何在含有 ReLU 的深度神經網絡中，收斂到全局最小值的呢？

　　這篇文章證明了，不管是全連接的深度前饋網絡，是深度卷積網絡 (CNN)，還是深度殘差網絡 (ResNet)，假設深度爲 L，假設訓練樣本有 n 個，只要樣本不退化——也就是任意兩個樣本之間的相對距離超過δ——那麼只要神經元數量超過，隨機初始化後的 SGD 算法就可以在多項式時間內找到全局最優解。這裏「找到全局最優解」的定義取決於具體任務，如果是分類問題，那麼就是在多項式時間內得到 100% 正確率；如果是擬合問題，就是在多項式時間內找到擬合殘差爲ε的解。後者被稱爲線性收斂速率。

　　細節

　　這篇文章的細節其實可以由如下兩個簡單的定理和圖片概括（文中 Sec 3.1）。假設損失函數是平方擬合（l_2 regression loss）

　　文中定理 3（沒有馬鞍點）：在一定條件下（比如 SGD 的移動路徑上），神經網絡目標函數的梯度模長的平方，大於目標函數值本身，除以一個多項式因子：

　　定理 3 說了一件很簡單的事情，就是隻要沒有達到全局最優，那麼函數梯度就一定大於零，並且函數越大，梯度的模長就越大。換言之，在 SGD 的移動路徑上，只要訓練損失 (training loss) 不到 0，就不會出現馬鞍點，更不會出現局部最小值。這個結果本身就很特殊，因爲大部分的非凸問題不滿足這個性質，而過度參數化的神經網絡，用 SGD 進行訓練，卻可以保證得到這個性質！

　　有了定理 3，就可以證明 SGD 收斂了麼？並沒有，因爲如果 SGD 向梯度的反方向移動，爲什麼函數值會下降？「函數值會下降」在優化理論中對應了光滑性 (smoothness)。傳統的優化理論中有很多關於光滑性的定義，但都需要函數至少二階可導（可惜 ReLU 激活函數並不存在二階導數）。這篇文章的另一個精髓，在於證明了過度參數化的神經網絡滿足以下的一個「半光滑性」。

　　文中定理 4（半光滑性）：在一定條件下（比如 SGD 的移動路徑上），神經網絡目標函數和其一階近似之間的距離「很小」：

　　與傳統光滑性不同的是，這裏不等式的右邊有一個關於‖ΔW‖的一階項，文中說明，這個一階項會隨着神經元數量越來越多，變得越來越小。也就是網絡參數越多，會越「光滑」，也就越容易做訓練。

　　爲了理解定理 3 和定理 4，我們可以參見文中的圖片。當目標函數值在 1.3（並沒有到全局最優）的時候，函數的梯度很大（定理 3），並且向梯度方向走，的確可以有效地降低目標函數值（定理 4）。

　　延伸

　　本文中關於 SGD 收斂性的證明，停留在了前饋網絡（包括 CNN，ResNet 等），那麼是否可以擴展到其它的更復雜的深度學習網絡呢？例如在自然語言處理應用中廣泛使用的遞歸神經網絡（RNN）？作者強調了 RNN 其實是一個比 DNN 更難的問題（第三頁）。在兩週前，本文的作者將這個問題單獨成稿，發表在了 arXiv 上（鏈接：https://arxiv.org/abs/1810.12065）。

　　目前提到的多層網絡收斂性都是針對訓練數據找全局最優。那麼如何推廣到測試數據集呢？這篇文章並沒有涉及，但是在第三頁援引了一個同樣是這周傳到 arXiv 的重要工作 [Allen-Zhu, Li, Liang 2018]：證明了過度參數化的三層神經網絡的訓練集最優解可以推廣到測試集！具體而言，如果數據是由一個未知的三層神經網絡產生的，那麼使用過參數化的三層神經網絡，和 SGD 進行訓練，只要多項式級別那麼多樣本，就可以學出能在測試集上完成比如分類、擬合問題的未知網絡。這個結果是對本文的一個很好的補充（鏈接：https://arxiv.org/abs/1811.04918）。

　　本文爲機器之心報道，轉載請聯繫本公衆號獲得授權。