SGD   神經(jīng)網(wǎng)絡(luò)

昨日，reddit 上一篇帖子引發(fā)熱議，該帖介紹了一篇關(guān)于梯度下降對過參數(shù)化神經(jīng)網(wǎng)絡(luò)影響的論文，該論文只用單個(gè)非常寬的隱藏層，并證明了在一定條件下神經(jīng)網(wǎng)絡(luò)能收斂到非凸優(yōu)化的全局最優(yōu)解。這是對深度學(xué)習(xí)的復(fù)古？到底是否有效？社區(qū)中很多人對此發(fā)表了看法。機(jī)器之心簡要介紹了該論文，更詳細(xì)的推導(dǎo)過程與方法請查看原論文，不過這樣的證明讀者們都 Hold 住嗎。

用一階方法訓(xùn)練的神經(jīng)網(wǎng)絡(luò)已經(jīng)對很多應(yīng)用產(chǎn)生了顯著影響，但其理論特性卻依然成謎。一個(gè)經(jīng)驗(yàn)觀察是，即使優(yōu)化目標(biāo)函數(shù)是非凸和非平滑的，隨機(jī)初始化的一階方法（如隨機(jī)梯度下降）仍然可以找到全局最小值（訓(xùn)練損失接近為零）。令人驚訝的是，這個(gè)特性與標(biāo)簽無關(guān)。在 Zhang 等人的論文 [2016] 中，作者用隨機(jī)生成的標(biāo)簽取代了真正的標(biāo)簽，但仍發(fā)現(xiàn)隨機(jī)初始化的一階方法總能達(dá)到零訓(xùn)練損失。

關(guān)于神經(jīng)網(wǎng)絡(luò)為什么能適應(yīng)所有訓(xùn)練標(biāo)簽，人們普遍認(rèn)為是因?yàn)樯窠?jīng)網(wǎng)絡(luò)過參數(shù)化了。例如，Wide ResNet [Zagoruyko and Komodakis] 使用的參數(shù)數(shù)量是訓(xùn)練數(shù)據(jù)的 100 倍，因此必須存在一個(gè)這種架構(gòu)的神經(jīng)網(wǎng)絡(luò)，能夠適應(yīng)所有訓(xùn)練數(shù)據(jù)。然而，這并不能說明為什么由隨機(jī)初始化的一階方法找到的神經(jīng)網(wǎng)絡(luò)能夠適應(yīng)所有數(shù)據(jù)。目標(biāo)函數(shù)是非凸和非平滑的，這使得傳統(tǒng)的凸優(yōu)化分析技術(shù)在這種情況下沒有用。據(jù)我們所知，理論只能保證現(xiàn)有的方法收斂到一個(gè)駐點(diǎn) [Davis et al., 2018]。

在本文中，作者將解釋這一令人驚訝的現(xiàn)象，即帶有修正線性單元（ReLU）激活函數(shù)的兩層神經(jīng)網(wǎng)絡(luò)能收斂到全局最優(yōu)解。形式化的，我們可以考慮有以下形式的神經(jīng)網(wǎng)絡(luò)：

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

隨后我們可以根據(jù)二次損失函數(shù)（歐式距離）定義經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化問題，若給定 n 筆數(shù)據(jù)的訓(xùn)練集 {(x_1, y_1), ..., (x_i, y_i), ..., (x_n, y_n) }，我們希望最小化：

為了實(shí)現(xiàn)經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化，我們需要修正第二層并針對第一層的權(quán)重矩陣應(yīng)用梯度下降（GD）：

其中η > 0 為學(xué)習(xí)率（在本論文中為步長），因此每一個(gè)權(quán)重向量的梯度計(jì)算式可以表示為：

盡管這只是一個(gè)淺層全連接網(wǎng)絡(luò)，但由于使用了 ReLU 激活函數(shù)，目標(biāo)函數(shù)仍然是非凸和不平滑的。不過即使針對這樣簡單的目標(biāo)函數(shù)，為什么隨機(jī)初始化的一階梯度方法能實(shí)現(xiàn)零的訓(xùn)練誤差仍然不太清楚。實(shí)際上，許多先前的研究工作都在嘗試回答這個(gè)問題。他們嘗試的方法包括損失函數(shù)面貌分析、偏微分方程、算法動力學(xué)分析或最優(yōu)傳輸理論等。這些方法或研究結(jié)果通常都依賴于標(biāo)簽和輸入分布的強(qiáng)假設(shè)，或者并沒有明示為什么隨機(jī)初始化的一階方法能實(shí)現(xiàn)零的訓(xùn)練損失。

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

分析技術(shù)概覽：

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

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

最后作者發(fā)現(xiàn)過參數(shù)化、隨機(jī)初始化和線性收斂聯(lián)合限制了權(quán)重向量 w_r 仍然接近于初始值。

最后作者根據(jù)這三個(gè)觀察結(jié)果與方法嚴(yán)格證明了他們的論點(diǎn)，此外他們還表示整個(gè)證明僅使用了線性代數(shù)與標(biāo)準(zhǔn)概率邊界，因此能推廣到其它深度神經(jīng)網(wǎng)絡(luò)。以下我們展示了他們證明出的兩個(gè)定理（Theorem 3.1 和 Theorem 4.1），證明過程請查閱原論文。

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

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

摘要：神經(jīng)網(wǎng)絡(luò)一個(gè)最神秘的地方是梯度下降等隨機(jī)初始化的一階優(yōu)化方法能實(shí)現(xiàn)零的訓(xùn)練損失，即使目標(biāo)函數(shù)是非凸和不平滑的。本論文揭秘了這一現(xiàn)象，即帶有 ReLU 激活函數(shù)的兩層全連接網(wǎng)絡(luò)為什么能實(shí)現(xiàn)零的訓(xùn)練損失。對于有 m 個(gè)隱藏神經(jīng)元的淺層神經(jīng)網(wǎng)絡(luò)（ReLU 激活函數(shù)）和 n 項(xiàng)訓(xùn)練數(shù)據(jù)，我們的實(shí)驗(yàn)表示只要 m 足夠大，且數(shù)據(jù)是非退化的，那么隨機(jī)初始化的梯度下降能收斂到全局最優(yōu)解，且收斂速度對于二次損失函數(shù)是線性的。

我們的分析基于以下觀察：過參數(shù)化和隨機(jī)初始化聯(lián)合限制了每一個(gè)權(quán)重向量在所有迭代中都接近于它的初始值，這令我們可以利用比較強(qiáng)的類凸屬性，并展示梯度下降能以全局線性的速率收斂到全局最優(yōu)解。我們相信這些觀點(diǎn)同樣能用于分析深度模型和其它一階梯度優(yōu)化方法。

3 連續(xù)型時(shí)間分析

本章展示了分析梯度流（gradient flow）的結(jié)果，即將步長設(shè)置為無窮小量的梯度下降。在后一部分的離散型時(shí)間分析中，我們將進(jìn)一步修正這一部分的證明，并為帶正下降步長的梯度下降設(shè)定一個(gè)定量邊界。

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

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

4 離散型時(shí)間分析

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

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