隨機(jī)梯度下降

在前面的章節(jié)中，我們一直在訓(xùn)練過程中使用隨機(jī)梯度下降，但沒有解釋它為什么起作用。為了澄清這一點(diǎn)，我們剛在 :numref:sec_gd中描述了梯度下降的基本原則。本節(jié)繼續(xù)更詳細(xì)地說明隨機(jī)梯度下降（stochastic gradient descent）。

%matplotlib inline
import math
import torch
from d2l import torch as d2l

隨機(jī)梯度更新

在深度學(xué)習(xí)中，目標(biāo)函數(shù)通常是訓(xùn)練數(shù)據(jù)集中每個(gè)樣本的損失函數(shù)的平均值。給定$n$個(gè)樣本的訓(xùn)練數(shù)據(jù)集，我們假設(shè)$f_i(\mathbf{x})$是關(guān)于索引$i$的訓(xùn)練樣本的損失函數(shù)，其中$\mathbf{x}$是參數(shù)向量。然后我們得到目標(biāo)函數(shù)

$$f(\mathbf{x})=\frac{1}{n}\sum _{i=1}^n{f}_i(\mathbf{x}).$$

$\mathbf{x}$的目標(biāo)函數(shù)的梯度計(jì)算為

$$?f(\mathbf{x})=\frac{1}{n}\sum _{i=1}^n?f_i(\mathbf{x}).$$

如果使用梯度下降法，則每個(gè)自變量迭代的計(jì)算代價(jià)為$\mathcal{O}(n)$，它隨$n$線性增長(zhǎng)。因此，當(dāng)訓(xùn)練數(shù)據(jù)集較大時(shí)，每次迭代的梯度下降計(jì)算代價(jià)將較高。

隨機(jī)梯度下降（SGD）可降低每次迭代時(shí)的計(jì)算代價(jià)。在隨機(jī)梯度下降的每次迭代中，我們對(duì)數(shù)據(jù)樣本隨機(jī)均勻采樣一個(gè)索引$i$，其中 i ∈ { 1 , … , n } i\in\{1,\ldots, n\} i∈{1,…,n}，并計(jì)算梯度$?f_i(\mathbf{x})$以更新$\mathbf{x}$：

$$\mathbf{x}\leftarrow \mathbf{x}?\eta ?f_i(\mathbf{x}),$$

其中$\eta$是學(xué)習(xí)率。我們可以看到，每次迭代的計(jì)算代價(jià)從梯度下降的$\mathcal{O}(n)$降至常數(shù)$\mathcal{O}(1)$。此外，我們要強(qiáng)調(diào)，隨機(jī)梯度$?f_i(\mathbf{x})$是對(duì)完整梯度$?f(\mathbf{x})$的無偏估計(jì)，因?yàn)?/p>

$${\mathbb{E}}_i?f_i(\mathbf{x})=\frac{1}{n}\sum _{i=1}^n?f_i(\mathbf{x})=?f(\mathbf{x}).$$

這意味著，平均而言，隨機(jī)梯度是對(duì)梯度的良好估計(jì)。

現(xiàn)在，我們將把它與梯度下降進(jìn)行比較，方法是向梯度添加均值為0、方差為1的隨機(jī)噪聲，以模擬隨機(jī)梯度下降。

def f(x1, x2):  # 目標(biāo)函數(shù)return x1 ** 2 + 2 * x2 ** 2def f_grad(x1, x2):  # 目標(biāo)函數(shù)的梯度return 2 * x1, 4 * x2

def sgd(x1, x2, s1, s2, f_grad):g1, g2 = f_grad(x1, x2)# 模擬有噪聲的梯度g1 += torch.normal(0.0, 1, (1,)).item()g2 += torch.normal(0.0, 1, (1,)).item()eta_t = eta * lr()return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)

def constant_lr():return 1eta = 0.1
lr = constant_lr  # 常數(shù)學(xué)習(xí)速度
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: 0.020569, x2: 0.227895

正如我們所看到的，隨機(jī)梯度下降中變量的軌跡比我們?cè)?:numref:sec_gd中觀察到的梯度下降中觀察到的軌跡嘈雜得多。這是由于梯度的隨機(jī)性質(zhì)。也就是說，即使我們接近最小值，我們?nèi)匀皇艿酵ㄟ^$\eta ?f_i(\mathbf{x})$的瞬間梯度所注入的不確定性的影響。即使經(jīng)過50次迭代，質(zhì)量仍然不那么好。更糟糕的是，經(jīng)過額外的步驟，它不會(huì)得到改善。這給我們留下了唯一的選擇：改變學(xué)習(xí)率$\eta$。但是，如果我們選擇的學(xué)習(xí)率太小，我們一開始就不會(huì)取得任何有意義的進(jìn)展。另一方面，如果我們選擇的學(xué)習(xí)率太大，我們將無法獲得一個(gè)好的解決方案，如上所示。解決這些相互沖突的目標(biāo)的唯一方法是在優(yōu)化過程中動(dòng)態(tài)降低學(xué)習(xí)率。

這也是在sgd步長(zhǎng)函數(shù)中添加學(xué)習(xí)率函數(shù)lr的原因。在上面的示例中，學(xué)習(xí)率調(diào)度的任何功能都處于休眠狀態(tài)，因?yàn)槲覀儗⑾嚓P(guān)的lr函數(shù)設(shè)置為常量。

動(dòng)態(tài)學(xué)習(xí)率

用與時(shí)間相關(guān)的學(xué)習(xí)率$\eta (t)$取代$\eta$增加了控制優(yōu)化算法收斂的復(fù)雜性。特別是，我們需要弄清$\eta$的衰減速度。如果太快，我們將過早停止優(yōu)化。如果減少的太慢，我們會(huì)在優(yōu)化上浪費(fèi)太多時(shí)間。以下是隨著時(shí)間推移調(diào)整$\eta$時(shí)使用的一些基本策略（稍后我們將討論更高級(jí)的策略）：

$$\begin{array}{rlrl}\eta (t)& ={\eta }_i\text{?if?}{t}_i\le t\le t_{i+1}& & \text{分段常數(shù)}\\ \eta (t)& ={\eta }_0?e^{?\lambda t}& & \text{指數(shù)衰減}\\ \eta (t)& ={\eta }_0?(\beta t+1{)}^{?\alpha }& & \text{多項(xiàng)式衰減}\end{array}$$

在第一個(gè)分段常數(shù)（piecewise constant）場(chǎng)景中，我們會(huì)降低學(xué)習(xí)率，例如，每當(dāng)優(yōu)化進(jìn)度停頓時(shí)。這是訓(xùn)練深度網(wǎng)絡(luò)的常見策略?；蛘?#xff0c;我們可以通過指數(shù)衰減（exponential decay）來更積極地減低它。不幸的是，這往往會(huì)導(dǎo)致算法收斂之前過早停止。一個(gè)受歡迎的選擇是$\alpha =0.5$的多項(xiàng)式衰減（polynomial decay）。在凸優(yōu)化的情況下，有許多證據(jù)表明這種速率表現(xiàn)良好。

讓我們看看指數(shù)衰減在實(shí)踐中是什么樣子。

def exponential_lr():# 在函數(shù)外部定義，而在內(nèi)部更新的全局變量global tt += 1return math.exp(-0.1 * t)t = 1
lr = exponential_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=1000, f_grad=f_grad))

epoch 1000, x1: -0.998659, x2: 0.023408

正如預(yù)期的那樣，參數(shù)的方差大大減少。但是，這是以未能收斂到最優(yōu)解$\mathbf{x}=(0,0)$為代價(jià)的。即使經(jīng)過1000個(gè)迭代步驟，我們?nèi)匀浑x最優(yōu)解很遠(yuǎn)。事實(shí)上，該算法根本無法收斂。另一方面，如果我們使用多項(xiàng)式衰減，其中學(xué)習(xí)率隨迭代次數(shù)的平方根倒數(shù)衰減，那么僅在50次迭代之后，收斂就會(huì)更好。

def polynomial_lr():# 在函數(shù)外部定義，而在內(nèi)部更新的全局變量global tt += 1return (1 + 0.1 * t) ** (-0.5)t = 1
lr = polynomial_lr
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))

epoch 50, x1: -0.174174, x2: -0.000615

關(guān)于如何設(shè)置學(xué)習(xí)率，還有更多的選擇。例如，我們可以從較小的學(xué)習(xí)率開始，然后使其迅速上漲，再讓它降低，盡管這會(huì)更慢。我們甚至可以在較小和較大的學(xué)習(xí)率之間切換?，F(xiàn)在，讓我們專注于可以進(jìn)行全面理論分析的學(xué)習(xí)率計(jì)劃，即凸環(huán)境下的學(xué)習(xí)率。對(duì)一般的非凸問題，很難獲得有意義的收斂保證，因?yàn)榭偟膩碚f，最大限度地減少非線性非凸問題是NP困難的。有關(guān)的研究調(diào)查，請(qǐng)參閱例如2015年Tibshirani的優(yōu)秀講義筆記。

凸目標(biāo)的收斂性分析

以下對(duì)凸目標(biāo)函數(shù)的隨機(jī)梯度下降的收斂性分析是可選讀的，主要用于傳達(dá)對(duì)問題的更多直覺。我們只限于最簡(jiǎn)單的證明之一 :cite:Nesterov.Vial.2000。存在著明顯更先進(jìn)的證明技術(shù)，例如，當(dāng)目標(biāo)函數(shù)表現(xiàn)特別好時(shí)。

假設(shè)所有$\mathbf{\xi }$的目標(biāo)函數(shù)$f(\mathbf{\xi },\mathbf{x})$在$\mathbf{x}$中都是凸的。更具體地說，我們考慮隨機(jī)梯度下降更新：

$${\mathbf{x}}_{t+1}={\mathbf{x}}_t?{\eta }_t{?}_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x}),$$

其中$f({\mathbf{\xi }}_t,\mathbf{x})$是訓(xùn)練樣本$f({\mathbf{\xi }}_t,\mathbf{x})$的目標(biāo)函數(shù)：${\mathbf{\xi }}_t$從第$t$步的某個(gè)分布中提取，$\mathbf{x}$是模型參數(shù)。用

$$R(\mathbf{x})=E_{\mathbf{\xi }}[f(\mathbf{\xi },\mathbf{x})]$$

表示期望風(fēng)險(xiǎn)，$R^{?}$表示對(duì)于$\mathbf{x}$的最低風(fēng)險(xiǎn)。最后讓${\mathbf{x}}^{?}$表示最小值（我們假設(shè)它存在于定義$\mathbf{x}$的域中）。在這種情況下，我們可以跟蹤時(shí)間$t$處的當(dāng)前參數(shù)${\mathbf{x}}_t$和風(fēng)險(xiǎn)最小化器${\mathbf{x}}^{?}$之間的距離，看看它是否隨著時(shí)間的推移而改善：

$$\begin{array}{rl}& \Vert {\mathbf{x}}_{t+1}?{\mathbf{x}}^{?}{\Vert }^2\\ =& \Vert {\mathbf{x}}_t?{\eta }_t{?}_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x})?{\mathbf{x}}^{?}{\Vert }^2\\ =& \Vert {\mathbf{x}}_t?{\mathbf{x}}^{?}{\Vert }^2+{\eta }_t^2\Vert {?}_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x}){\Vert }^2?2{\eta }_t?{\mathbf{x}}_t?{\mathbf{x}}^{?},{?}_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x})?.\end{array}$$
:eqlabel:eq_sgd-xt+1-xstar

我們假設(shè)隨機(jī)梯度${?}_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x})$的$L_2$范數(shù)受到某個(gè)常數(shù)$L$的限制，因此我們有

$${\eta }_t^2\Vert {?}_{\mathbf{x}}f({\mathbf{\xi }}_t,\mathbf{x}){\Vert }^2\le {\eta }_t^2{L}^2.$$
:eqlabel:eq_sgd-L

我們最感興趣的是${\mathbf{x}}_t$和${\mathbf{x}}^{?}$之間的距離如何變化的期望。事實(shí)上，對(duì)于任何具體的步驟序列，距離可能會(huì)增加，這取決于我們遇到的${\mathbf{\xi }}_t$。因此我們需要點(diǎn)積的邊界。因?yàn)閷?duì)于任何凸函數(shù)$f$，所有$\mathbf{x}$和$\mathbf{y}$都滿足$f(\mathbf{y})\ge f(\mathbf{x})+?f^{\prime }(\mathbf{x}),\mathbf{y}?\mathbf{x}?$，按凸性我們有

$$f({\mathbf{\xi }}_t,{\mathbf{x}}^{?})\ge f({\mathbf{\xi }}_t,{\mathbf{x}}_t)+?{\mathbf{x}}^{?}?{\mathbf{x}}_t,{?}_{\mathbf{x}}f({\mathbf{\xi }}_t,{\mathbf{x}}_t)?.$$
:eqlabel:eq_sgd-f-xi-xstar

將不等式 :eqref:eq_sgd-L和 :eqref:eq_sgd-f-xi-xstar代入 :eqref:eq_sgd-xt+1-xstar我們?cè)跁r(shí)間$t+1$時(shí)獲得參數(shù)之間距離的邊界，如下所示：

$$\Vert {\mathbf{x}}_t?{\mathbf{x}}^{?}{\Vert }^2?\Vert {\mathbf{x}}_{t+1}?{\mathbf{x}}^{?}{\Vert }^2\ge 2{\eta }_t(f({\mathbf{\xi }}_t,{\mathbf{x}}_t)?f({\mathbf{\xi }}_t,{\mathbf{x}}^{?}))?{\eta }_t^2{L}^2.$$
:eqlabel:eqref_sgd-xt-diff

這意味著，只要當(dāng)前損失和最優(yōu)損失之間的差異超過${\eta }_t{L}^2/2$，我們就會(huì)取得進(jìn)展。由于這種差異必然會(huì)收斂到零，因此學(xué)習(xí)率${\eta }_t$也需要消失。

接下來，我們根據(jù) :eqref:eqref_sgd-xt-diff取期望。得到

$$E\left[\Vert {\mathbf{x}}_t?{\mathbf{x}}^{?}{\Vert }^2\right]?E\left[\Vert {\mathbf{x}}_{t+1}?{\mathbf{x}}^{?}{\Vert }^2\right]\ge 2{\eta }_t[E[R({\mathbf{x}}_t)]?R^{?}]?{\eta }_t^2{L}^2.$$

最后一步是對(duì) t ∈ { 1 , … , T } t \in \{1, \ldots, T\} t∈{1,…,T}的不等式求和。在求和過程中抵消中間項(xiàng)，然后舍去低階項(xiàng)，可以得到

$$\Vert {\mathbf{x}}_1?{\mathbf{x}}^{?}{\Vert }^2\ge 2\left(\sum _{t=1}^T{\eta }_t\right)[E[R({\mathbf{x}}_t)]?R^{?}]?L^2\sum _{t=1}^T{\eta }_t^2.$$
:eqlabel:eq_sgd-x1-xstar

請(qǐng)注意，我們利用了給定的${\mathbf{x}}_1$，因而可以去掉期望。最后定義

$$\bar{\mathbf{x}}\stackrel{\mathrm{def}}{=}\frac{{\sum }_{t=1}^T{\eta }_t{\mathbf{x}}_t}{{\sum }_{t=1}^T{\eta }_t}.$$

因?yàn)橛?/p>

$$E\left(\frac{{\sum }_{t=1}^T{\eta }_{t}R({\mathbf{x}}_t)}{{\sum }_{t=1}^T{\eta }_t}\right)=\frac{{\sum }_{t=1}^T{\eta }_{t}E[R({\mathbf{x}}_t)]}{{\sum }_{t=1}^T{\eta }_t}=E[R({\mathbf{x}}_t)],$$

根據(jù)詹森不等式（令 :eqref:eq_jensens-inequality中$i=t$，${\alpha }_i={\eta }_t/{\sum }_{t=1}^T{\eta }_t$）和$R$的凸性使其滿足的$E[R({\mathbf{x}}_t)]\ge E[R(\bar{\mathbf{x}})]$，因此，

$$\sum _{t=1}^T{\eta }_{t}E[R({\mathbf{x}}_t)]\ge \sum _{t=1}^T{\eta }_{t}E\left[R(\bar{\mathbf{x}})\right].$$

將其代入不等式 :eqref:eq_sgd-x1-xstar得到邊界

$$\left[E[\bar{\mathbf{x}}]\right]?R^{?}\le \frac{r^2+L^2{\sum }_{t=1}^T{\eta }_t^2}{2{\sum }_{t=1}^T{\eta }_t},$$

其中$r^2\stackrel{\mathrm{def}}{=}\Vert {\mathbf{x}}_1?{\mathbf{x}}^{?}{\Vert }^2$是初始選擇參數(shù)與最終結(jié)果之間距離的邊界。簡(jiǎn)而言之，收斂速度取決于隨機(jī)梯度標(biāo)準(zhǔn)的限制方式（$L$）以及初始參數(shù)值與最優(yōu)結(jié)果的距離（$r$）。請(qǐng)注意，邊界由$\bar{\mathbf{x}}$而不是${\mathbf{x}}_T$表示。因?yàn)?span id="vxwlu0yf4" class="katex--inline">$\bar{\mathbf{x}}$是優(yōu)化路徑的平滑版本。只要知道$r,L$和$T$，我們就可以選擇學(xué)習(xí)率$\eta =r/(L\sqrt{T})$。這個(gè)就是上界$rL/\sqrt{T}$。也就是說，我們將按照速度$\mathcal{O}(1/\sqrt{T})$收斂到最優(yōu)解。

隨機(jī)梯度和有限樣本

到目前為止，在談?wù)撾S機(jī)梯度下降時(shí)，我們進(jìn)行得有點(diǎn)快而松散。我們假設(shè)從分布$p(x,y)$中采樣得到樣本$x_i$（通常帶有標(biāo)簽$y_i$），并且用它來以某種方式更新模型參數(shù)。特別是，對(duì)于有限的樣本數(shù)量，我們僅僅討論了由某些允許我們?cè)谄渖蠄?zhí)行隨機(jī)梯度下降的函數(shù)${\delta }_{x_i}$和${\delta }_{y_i}$組成的離散分布$p(x,y)=\frac{1}{n}{\sum }_{i=1}^n{\delta }_{x_i}(x){\delta }_{y_i}(y)$。

但是，這不是我們真正做的。在本節(jié)的簡(jiǎn)單示例中，我們只是將噪聲添加到其他非隨機(jī)梯度上，也就是說，我們假裝有成對(duì)的$(x_i,y_i)$。事實(shí)證明，這種做法在這里是合理的（有關(guān)詳細(xì)討論，請(qǐng)參閱練習(xí)）。更麻煩的是，在以前的所有討論中，我們顯然沒有這樣做。相反，我們遍歷了所有實(shí)例恰好一次。要了解為什么這更可取，可以反向考慮一下，即我們有替換地從離散分布中采樣$n$個(gè)觀測(cè)值。隨機(jī)選擇一個(gè)元素$i$的概率是$1/n$。因此選擇它至少一次就是

$$P(\mathrm{choose}i)=1?P(\mathrm{omit}i)=1?(1?1/n{)}^n\approx 1?e^{?1}\approx \mathrm{0.63.}$$

類似的推理表明，挑選一些樣本（即訓(xùn)練示例）恰好一次的概率是

$$\left(\genfrac{}{}{0ex}{}{n}{1}\right)\frac{1}{n}{\left(1?\frac{1}{n}\right)}^{n?1}=\frac{n}{n?1}{\left(1?\frac{1}{n}\right)}^n\approx e^{?1}\approx \mathrm{0.37.}$$

這導(dǎo)致與無替換采樣相比，方差增加并且數(shù)據(jù)效率降低。因此，在實(shí)踐中我們執(zhí)行后者（這是本書中的默認(rèn)選擇）。最后一點(diǎn)注意，重復(fù)采用訓(xùn)練數(shù)據(jù)集的時(shí)候，會(huì)以不同的隨機(jī)順序遍歷它。

小結(jié)

• 對(duì)于凸問題，我們可以證明，對(duì)于廣泛的學(xué)習(xí)率選擇，隨機(jī)梯度下降將收斂到最優(yōu)解。
• 對(duì)于深度學(xué)習(xí)而言，情況通常并非如此。但是，對(duì)凸問題的分析使我們能夠深入了解如何進(jìn)行優(yōu)化，即逐步降低學(xué)習(xí)率，盡管不是太快。
• 如果學(xué)習(xí)率太小或太大，就會(huì)出現(xiàn)問題。實(shí)際上，通常只有經(jīng)過多次實(shí)驗(yàn)后才能找到合適的學(xué)習(xí)率。
• 當(dāng)訓(xùn)練數(shù)據(jù)集中有更多樣本時(shí)，計(jì)算梯度下降的每次迭代的代價(jià)更高，因此在這些情況下，首選隨機(jī)梯度下降。
• 隨機(jī)梯度下降的最優(yōu)性保證在非凸情況下一般不可用，因?yàn)樾枰獧z查的局部最小值的數(shù)量可能是指數(shù)級(jí)的。