ML Theory 太魔怔了?。。。?！

從微積分課上我們學(xué)到

• 對(duì)一個(gè) \(\mathscr C^2\) 函數(shù)，其二階泰勒展開(kāi)的皮亞諾余項(xiàng)形式

  \[f(\bm w') = f(\bm w) + \langle \nabla f(\bm w), \bm w' - \bm w\rangle + o(\|\bm w' - \bm w\|) \]

  這說(shuō)明只要 \(\bm w'\) 和 \(\bm w\) 挨得足夠接近，我們就可以用 \(f(\bm w) + \langle \nabla f(\bm w), \bm w' - \bm w \rangle\) 來(lái)逼近 \(f(\bm w')\)。

現(xiàn)在我們想定量描述這個(gè)逼近過(guò)程，來(lái)說(shuō)明梯度下降 (gredient descent, GD) 的收斂性及其速率。因此考慮其拉格朗日余項(xiàng)

我們來(lái)定量描述 \(g\) 的性質(zhì)。

由于梯度下降要執(zhí)行多輪，因此會(huì)有不同的 \(\bm w, \bm w'\)，所以性質(zhì)需要適用于所有位置。

定義 平滑性假設(shè) (Smoothness assumption) \(\exists L, \text{ s.t. } \forall \bm w, \bm w', |g(\bm \xi)| \leq L\)。換句話說(shuō)，

這個(gè)假設(shè)是非常自然的，其略強(qiáng)于 \(\mathscr C^2\)。在有界閉集上兩者等價(jià)。

平滑性是說(shuō)一個(gè)函數(shù)在每個(gè)點(diǎn)被一個(gè)二次函數(shù) bound 住，在梯度的視角下，這等價(jià)于其 Lipschitz 連續(xù)，在 Hessian 矩陣的視角下，這等價(jià)于矩陣的 norm 被 bound 住。

命題 梯度 \(L\)-Lipschitz 連續(xù)等價(jià)于 \(\|\nabla^2 f(x)\| \leq L\)，其中 \(|\nabla^2 f(x)|\) 表示 Hessian 矩陣的 Euclidean norm，即 \(\max_{\|x\| = 1} \|Hx\| = |\lambda|_{\max}\)。梯度 \(L\)-Lipschitz 連續(xù)表示

證明

• \(\Leftarrow\)：

  \[\begin{aligned} \|\nabla f(\bm w') - \nabla f(\bm w)\| &= \left\|\int^1_0 \nabla^2 f(\bm w + \tau(\bm w' - \bm w))(\bm w' - \bm w) \mathrm d \tau\right\| \\ &= \left\|\int^1_0 \nabla^2 f(\bm w + \tau(\bm w' - \bm w)) \mathrm d \tau \cdot (\bm w' - \bm w)\right\| \\ &\leq \left\|\int^1_0 \nabla^2 f(\bm w + \tau(\bm w' - \bm w))\mathrm d \tau\right\| \cdot \|\bm w' - \bm w\| \\ &\leq \int^1_0 \|\nabla^2 f(\bm w + \tau(\bm w' - \bm w))\|\mathrm d \tau \cdot \|\bm w' - \bm w\| \\ &\leq L\|\bm w' - \bm w\| \end{aligned}\]

• \(\Rightarrow\)：

  \[\|\nabla^2 f(\bm w)\| = \max_{\|\bm x\| = 1} \|H\bm x\| \leq \lim_{\alpha \to 0^+}\frac{\|\nabla f(\bm w + \alpha \bm v) - \nabla f(\bm w)\|}{\alpha} \leq L \]

  其中 \(\|\bm v\| = 1\)。

命題 \(L\)-平滑等價(jià)于梯度 \(L\)-Lipschitz 連續(xù)。

證明

• \(\Leftarrow\)：

  \[\begin{aligned} f(\bm w') &= f(\bm w) + \int^1_0 \langle \nabla f(\bm w + \tau(\bm w' - \bm w)), \bm w' - \bm w \rangle \mathrm d \tau \\ &= f(\bm w) + \langle \nabla f(\bm w), \bm w' - \bm w \rangle + \int^1_0 \langle \nabla f(\bm w + \tau(\bm w' - \bm w)) - \nabla f(\bm w), \bm w' - \bm w \rangle \mathrm d \tau \\ &\leq f(\bm w) + \langle \nabla f(\bm w), \bm w' - \bm w \rangle + \int^1_0 \|\nabla f(\bm w + \tau(\bm w' - \bm w)) - \nabla f(\bm w)\| \cdot \|\bm w' - \bm w \| \mathrm d \tau && \text{Cauchy-Schwarz} \\ &\leq f(\bm w) + \langle \nabla f(\bm w), \bm w' - \bm w \rangle + \int^1_0 L\tau\|\bm w' - \bm w\| \cdot \|\bm w' - \bm w \| \mathrm d \tau \\ &= f(\bm w) + \langle \nabla f(\bm w), \bm w' - \bm w \rangle + \frac L2\|\bm w' - \bm w\|^2 \\ \end{aligned}\]

• \(\Rightarrow\)：考慮 \(f\) 的 Lagrange 余項(xiàng)的 Taylor 展開(kāi)

  \[f(\bm w') = f(\bm w) + \langle f(\bm w), \bm w' - \bm w \rangle + \frac 12 \langle\nabla^2 f(\bm \xi)(\bm w' - \bm w), \bm w' - \bm w \rangle \]
  \[|f(\bm w')- f(\bm w) - \langle \nabla f(\bm w), \bm w' - \bm w\rangle| = \frac 12 |\langle \nabla^2 f(\bm \xi)(\bm w' - \bm w), \bm w' - \bm w \rangle|\leq \frac L2\|\bm w' - \bm w\|^2 \]

  令 \(\bm w' = \bm w + t \bm v, \|\bm v\| = 1\)，有

  \[|\langle \nabla^2 f(\bm w + t \bm v) \bm v, \bm v\rangle| \leq L \]

  令 \(t \to 0^+\)，由于 \(f\) 是 \(\mathscr C^2\) 函數(shù)，可得

  \[|\langle \nabla^2 f(\bm w) \bm v, \bm v\rangle| \leq L \]

  注意到 \(\nabla^2 f(\bm w)\) 是一個(gè) self-adjoint 的矩陣，因此

  \[\max_{\bm v} \|\nabla^2 f(\bm w)\bm v\|_2 = \max_{\bm v} \langle \nabla^2 f(\bm w) \bm v, \bm v\rangle = |\lambda|_{\max} \]

  根據(jù)上一條命題，該命題得證。

回到梯度下降中。對(duì)平滑的 \(f\)，有

這給出了一個(gè)從 \(\bm w\) 出發(fā)，走到某個(gè) \(\bm w'\) 的 \(f\) 的上下界，就像這樣（靈魂畫(huà)手 yy）

下界并不重要，我們關(guān)心的是上界。在 \(\bm w, \bm w'\) 足夠接近時(shí)，\(f\) 總是下降的，定量地，假設(shè)在梯度下降中采取學(xué)習(xí)速率 \(\eta\)，\(\bm w' = \bm w - \eta \nabla f(\bm w)\)，

因此當(dāng) \(\eta < \frac 2L\) 時(shí)，式子總是 \(< 0\) 的，這保證我們每次梯度下降都會(huì)有進(jìn)步。

但是這個(gè)假設(shè)還是不夠。首先它可能會(huì)落入局部最優(yōu)，其次雖然每次都有進(jìn)步，但是全局的收斂速度沒(méi)有保證?？紤] \(f(x) = \mathrm{sigmoid}(x)\)，從 \(x\) 很大的開(kāi)始向中間靠攏，速度是負(fù)指數(shù)級(jí)的。這要求我們給函數(shù)更多的整體性質(zhì)。

定義 一個(gè)函數(shù) \(f\) 是凸的，如果 \(f(t\bm x_1 + (1 - t)\bm x_2) \leq tf(\bm x_1) + (1 - t)f(\bm x_2),\ t \in [0, 1]\)。

其有若干個(gè)等價(jià)定義，這是微積分課上講過(guò)的。

命題 若 \(f\) 是 \(\mathscr C^2\) 函數(shù)，則凸等價(jià)于 \(\nabla^2 f(\bm w)\) 半正定。

也就是說(shuō)，凸性和平滑性一個(gè)保證的是 \(|\lambda|_{\max}\) 的界，一個(gè)保證的是 \(\lambda_{\min}\) 的符號(hào)。

凸性能夠保證收斂速度。

命題 \(\bm w^* = \operatorname{argmin}_{\bm w} f(\bm w)\)，采用學(xué)習(xí)速率 \(\eta \leq \frac 1L\) 進(jìn)行 \(t\) 輪梯度下降時(shí)，有

證明 考慮裂項(xiàng)法

由于 \(f(\bm w_i)\) 不升，

令總訓(xùn)練輪數(shù)

即可得到 \(f(\bm w_t) \leq f(\bm w^*) + \epsilon\)。

接下來(lái)考慮一個(gè)很常用的技巧，隨機(jī)梯度下降 (stochastic gradient descent, SGD)。如果我們每次都僅選取小批量數(shù)據(jù)計(jì)算梯度，那么便要考慮收斂性的問(wèn)題。

其中

如果采取隨機(jī)選取 \(S\) 的策略，我們可以不再考慮 \(\bm G_t\) 的由來(lái)，而是僅把其當(dāng)作一個(gè)隨機(jī)變量對(duì)待。

命題 \(f\) 是一個(gè)凸的 \(L\)-平滑函數(shù)，\(\bm w^* = \operatorname{argmin}_{\bm w} f(\bm w)\)，采用學(xué)習(xí)速率 \(\eta \leq \frac 1L\) 且使得 \(\mathrm{Var}(\bm G_t) \leq \sigma^2\) 進(jìn)行 \(t\) 輪梯度下降時(shí)，有

其中 \(\overline {\bm w_i} = \frac 1t \sum_{i=1}^t \bm w_i\)。

證明 考慮轉(zhuǎn)化為和 GD 類(lèi)似的形式。一次項(xiàng)用期望的線性性，二次項(xiàng)用方差 \(\mathrm{Var}(\bm G_t) = \mathbb E\|\bm G_t\|^2 - (\mathbb E \bm G_t)^2 = \mathbb E\|\bm G_t\|^2 - \|\nabla f(\bm w_i)\|^2\)。由此不斷轉(zhuǎn)化 \(\bm G_i\) 和 \(\nabla f(\bm w_i)\)，分離固定部分和隨機(jī)部分。

令

即可得到 \(\mathbb Ef(\overline{\bm w_t}) \leq f(\bm w^*) + \epsilon\)。

也就是說(shuō)，誤差項(xiàng)是不隨 \(t\) 改變的，因此只能通過(guò)縮小學(xué)習(xí)速率降低誤差。這導(dǎo)致 GD 有 \(\frac 1T\) 的收斂速率時(shí) SGD 只有 \(\frac 1{\sqrt T}\) 的收斂速率。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-711711.html

到了這里，關(guān)于[機(jī)器學(xué)習(xí)] 1. 梯度下降 Gradient Descent 與隨機(jī)梯度下降 Stochastic Gradient Descent的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！