6.4-随机梯度下降

本节介绍随机梯度下降 (stochastic gradient descent) 算法，该算法在机器学习领域应用广泛。我们将证明SGD是RM算法的一种特殊情况，而前面介绍的期望值估计算法又是SGD算法的一种特殊情况。

考虑如下优化问题：

\[\min_{w}J(w)=\mathbb{E}[f(w,X)],\tag{6.10}\]

其中$w$为待优化参数，$X$是一个随机变量。这里的期望值是对$X$进行计算。这里$w$和$X$可以是标量也可以是向量，而函数$f(\cdot)$是一个标量。

解决 (6.10) 的常见方法是梯度下降 (gradient descent)。由于 $\mathbb{E}[f(w, X)]$ 的梯度是 $\nabla_w \mathbb{E}[f(w, X)] = \mathbb{E}[\nabla_w f(w, X)]$，相应的梯度下降算法是

\[w_{k+1} = w_k - \alpha_k \nabla_w J(w_k) = w_k - \alpha_k \mathbb{E}[\nabla_w f(w_k, X)] \tag{6.11}\]

梯度下降算法在一些条件下(例如 $f$ 是凸函数)可以找到全局最优解$w^*$。关于梯度下降算法的更多信息可参见附录D。

梯度下降算法需要依赖于期望值 $\mathbb{E}[\nabla_w f(w_k, X)]$。我们知道有两种获取期望值的方法：第一种方法是基于模型的方法，即利用 $X$ 的概率分布和期望值的定义直接计算，然而 $X$ 的概率分布可能是难以得到的；第二种方法是基于数据的方法，即用独立同分布的样本 $\{x_i\}_{i=1}^n$ 来计算：

\[E[\nabla_w f(w_k, X)] \approx \frac{1}{n} \sum_{i=1}^n \nabla_w f(w_k, x_i).\]

此时$(6.11)$式变为

\[w_{k+1} = w_k - \alpha_k \frac{1}{n} \sum_{i=1}^n \nabla_w f(w_k, x_i),\tag{6.12}\]

$(6.12)$式中算法的一个问题在于它每次迭代都需要使用全部样本。如果样本是逐个采集的，可采用如下算法：

\[w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k),\tag{6.13}\]

其中 $x_k$ 是在时刻 $k$ 得到的样本。上式就是著名的随机梯度下降，它之所以被称为随机梯度下降，是因为它采用一个基于单个随机样本得到的随机梯度 $\nabla_w f(w_k, x_k)$ 来替换梯度下降中的真实梯度 $\mathbb{E}[\nabla_w f(w_k, X)]$。

由于随机梯度 $\nabla_w f(w, x_k)$ 不等于真实梯度 $\mathbb{E}[\nabla_w f(w, X)]$，那么替换后该算法能否确保当 $k \to \infty$ 时 $w_k \to w^*$ 呢？答案是可以的。下面我们先给出一个直观的解释，之后在第$6.4.5$节给出更严格的证明。

Note

这里可以将SGD与GD和BGD对比一下。

具体来说，随机梯度可以重新写成

\[\begin{aligned}\nabla_{w}f(w_{k},x_{k})&=\mathbb{E}[\nabla_wf(w_k,X)]+\left(\nabla_wf(w_k,x_k)-\mathbb{E}[\nabla_wf(w_k,X)]\right)\\&\doteq\mathbb{E}[\nabla_wf(w_k,X)]+\eta_k,\end{aligned}\]

上式表明随机梯度等于真是梯度加一个噪声项$\eta_k$，将其代入式$(6.13)$可得

\[w_{k+1} = w_k - \alpha_k \mathbb{E}[\nabla_w f(w_k, X)] - \alpha_k \eta_k. \]

因此，随机梯度下降算法与常规的梯度下降算法的差异仅仅是一个噪声项 $\alpha_k \eta_k$。由于 $\{x_k\}$ 是独立同分布的，我们有 $\mathbb{E}_{x_k}[\nabla_w f(w_k, x_k)] = \mathbb{E}_X[\nabla_w f(w_k, X)]$。因此，$\eta_k$ 的期望等于 0：

\[\mathbb{E}[\eta_k] = \mathbb{E}[\nabla_w f(w_k, x_k) - \nabla_w f(w_k, X)] = \mathbb{E}_x[\nabla_w f(w_k, x_k)] - \mathbb{E}_X[\nabla_w f(w_k, X)] = 0.\]

在直观上，由于噪声的均值等于 0，因此它应该不会对收敛性造成太大的危害。更严格的证明将在章节 6.4.5 节中给出。

6.4.1 应用于期望估计¶

接下来，我们应用随机梯度下降(SGD)来分析期望值估计问题，并证明式$(6.4)$中的期望值估计算法是一种特殊的随机梯度下降算法。

首先，我们将期望值估计问题描述为如下优化问题：

\[\min_wJ(w)=\mathbb{E}\left[\frac{1}{2}\|w-X\|^2\right]\doteq\mathbb{E}[f(w,X)],\tag{6.14}\]

其中 $f(w,X) = \|w - X\|^2/2$且梯度为 $\nabla_w f(w,X) = w - X$。通过求解 $\nabla_w J(w) =0$可验证最优解为 $w^* = \mathbb{E}[X]$。因此，该优化问题等价于期望值估计问题。

Note

$\nabla_w J(w) =0$$\rightarrow$$\mathbb{E}[\nabla_w f(w,X)]=0$$\rightarrow$$\mathbb{E}[w-X]=0$$\rightarrow$$w^*=\mathbb{E}[X]$

求解式$(6.14)$的梯度下降算法为

\[\begin{aligned}w_{k+1}&=w_k-\alpha_k\nabla_wJ(w_k)\\&=w_k-\alpha_k\mathbb{E}[\nabla_wf(w_k,X)]\\&=w_k-\alpha_k\mathbb{E}[w_k-X]\end{aligned}\]

该梯度下降算法无法直接使用，因为等式右侧的 $E[w_k - X]$或 $E[X]$未知，实际上这正是我们需要求解的项。
求解式$(6.14)$的随机梯度下降算法为

\[w_{k+1}=w_k-\alpha_k\nabla_wf(w_k,x_k)=w_k-\alpha_k(w_k-x_k)\]

其中$x_k$为时刻$k$处获取的样本。值得注意的是，这个随机梯度下降算法与式$(6.4)$中的期望值估计算法完全一致。因此，$(6.4)$式是专门为解决期望值估计问题设计的随机梯度下降算法。

6.4.2 随机梯度下降的收敛形式¶

随机梯度下降法的思想是用随机梯度代替真实梯度。由于随机梯度是随机的，读者可能会认为其收敛速度不是很慢或很随机。实际上，随机梯度下降法通常可以高速收敛。一个有趣的模式是：当估计值 $w_k$ 远离最优解 $w^*$ 时，随机梯度下降的收敛与常规梯度下降类似；只有当 $w_k$ 接近 $w^*$ 时，随机梯度下降的收敛才会表现出更多的随机性。下面是对此一收敛模式的分析和示例。

Note

$\nabla_wf(w_k,x_k)$可以看作是$\mathbb{E}[\nabla_wf(w,X)]$的噪声测量值。

下文将分析该模式并给出示例说明。

分析：随机梯度与真实梯度之间的相对误差(relative error)为

\[\delta_k\doteq\frac{|\nabla_wf(w_k,x_k)-\mathbb{E}[\nabla_wf(w_k,X)]|}{|\mathbb{E}[\nabla_wf(w_k,X)]|}.\]

为简化分析，我们考虑 $w$和 $\nabla_w f(w, x)$均为标量的情形。由于 $w^*$是最优解，故有 $\mathbb{E}[\nabla_w f(w^*,X)] =0$。此时上式可改写为

\[\delta_k=\frac{|\nabla_wf(w_k,x_k)-\mathbb{E}[\nabla_wf(w_k,X)]|}{|\mathbb{E}[\nabla_wf(w_k,X)]-\mathbb{E}[\nabla_wf(w^*,X)]|}=\frac{|\nabla_wf(w_k,x_k)-\mathbb{E}[\nabla_wf(w_k,X)]|}{|\mathbb{E}[\nabla_w^2f(\tilde{w}_k,X)(w_k-w^*)]|},\tag{6.15}\]

其中最后一个等式由中值定理[7,8]得出，其中$\tilde{w}_k \in [w_k, w^*]$。假设$f$是严格凸的，即对任意$w,X$有$\nabla^2_w f \geq c >0$。此时，$(6.15)$中的分母可表示为

\[\begin{aligned}\left|\mathbb{E}[\nabla_{w}^{2}f(\tilde{w}_{k},X)(w_{k}-w^{*})]\right|&=\left|\mathbb{E}[\nabla_{w}^{2}f(\tilde{w}_{k},X)]\right|\left|(w_{k}-w^{*})\right|\\&\geq c|w_{k}-w^{*}|.\end{aligned}\]

将上述不等式代入式$(6.15)$可得

\[\delta_k\leq\frac{\mid\overbrace{\nabla_wf(w_k,x_k)}^\text{stochastic gradient}-\overbrace{\mathbb{E}[\nabla_wf(w_k,X)]}^\text{true gradient}\mid}{\underbrace{c|w_k-w^*|}_{\text{distance to the optimal solution}}}.\]

上式表明了梯度的相对误差 $\delta_k$ 与估计的绝对误差 $|w_k - w^*|$ 之间的关系。当 $|w_k - w^*|$ 较大时，$\delta_k$ 较小，此时随机梯度和真实梯度差不多，因此随机梯度下降法的表现类似于梯度下降法，进而 $w_k$ 会迅速接近 $w^*$，这是我们希望看到的良好特质。当 $|w_k - w^*|$ 较小时，梯度的相对误差 $\delta_k$ 可能会很大，此时随机梯度下降法的表现相较于梯度下降会有更大的随机性，这就是使用随机样本本难以避免的问题，可以通过使用更多的数据和较小的学习率来缓解随机性问题。
例子: 期望值估计问题是展示上述分析的典型案例。考虑$(6.14)$中的均值估计问题，当$w$和$X$均为标量时，有$f(w,X) = |w -X|^2/2$，因此

\[\begin{aligned}\nabla_{w}f(w,x_{k})&=w-x_{k},\\\mathbb{E}[\nabla_wf(w,x_k)]&=w-\mathbb{E}[X]=w-w^{*}.\end{aligned}\]

此时可以计算得到梯度的相对误差为

\[\delta_k=\frac{|\nabla_wf(w_k,x_k)-\mathbb{E}[\nabla_wf(w_k,X)]|}{|\mathbb{E}[\nabla_wf(w_k,X)]|}=\frac{|(w_k-x_k)-(w_k-\mathbb{E}[X])|}{|w_k-w^*|}=\frac{|\mathbb{E}[X]-x_k|}{|w_k-w^*|}.\]

图$6.5$：演示随机梯度下降与小批量梯度下降算法的示例。二维随机变量 $X \in \mathbb{R}^2$服从边长为20、原点为中心的正方形区域均匀分布，其均值满足 $\mathbb{E}[X] =0$。均值估计基于100个独立同分布样本。

Note

通过图$6.5$也可以发现，SGD在收敛过程中，初始时刻并没有展现出随机性，而当靠近目标值时，展现出了一定的随机性，这与我们分析是一致的。

从上式可知两个有意思的性质。第一，$\delta_k$ 与 $|w_k - w^*|$ 是反比的，这与前面的分析是一致的，即当 $w_k$ 离 $w^*$ 较远时，随机梯度下降和梯度下降的行为是类似的。第二，$\delta_k$ 与 $\mathbb{E}[X] - x_k$ 的差有关，这是因为它的定义是 $var(X) = \mathbb{E}[(\mathbb{E}[X] - X)^2]$。因此，当方差很小时，$\mathbb{E}[X] - x_k$ 的值是比较小的，进而 $\delta_k$ 是较小的，此时随机梯度下降的行为会更接近梯度下降。

图 $6.5$ 给出了一个期望值估计的例子。这里 $X \in \mathbb{R}^2$ 表示一个边长为 10 的方形区域中的一个随机位置，其分布是均匀的，且其实际期望值在原点。该计算过程使用了最低千个独立同分布的样本。可以看出，尽管初始估计离实际值很远，但随机梯度下降能接近原点，当估计值接近原点时，收敛过程会表现出一定的随机性。这体现与前面的理论分析是一致的。

6.4.3 随机梯度下降的另一种描述¶

式$(6.13)$描述的随机梯度下降是涉及随机变量的。有的读者可能会在其他资料中看到另一种描述随机梯度下降算法的方式，而其中并不显式涉及任何随机变量。

具体来说，考虑一组实数 $\{x_i\}_{i=1}^{n}$，其中 $x_i$ 并非任何随机变量的样本。这是要解决的优化问题是最小化平均值：

\[\min_wJ(w)=\frac{1}{n}\sum_{i=1}^nf(w,x_i),\tag{6.16}\]

其中 $f(w, x_i)$为参数化函数，$w$为待优化参数。求解该问题的梯度下降算法为

\[w_{k+1}=w_{k}-\alpha_{k}\nabla_{w}J(w_{k})=w_{k}-\alpha_{k}\frac{1}{n}\sum_{i=1}^{n}\nabla_{w}f(w_{k},x_{i}).\]

假设集合 $\{x_i\}_{i=1}^n$规模很大，并且每次仅能获取一个元素。在此情况下，采用下式来更新$w_k$：

\[w_{k+1}=w_k-\alpha_k\nabla_wf(w_k,x_k).\tag{6.17}\]

读者可能已经注意到$(6.17)$中的算法与随机梯度下降非常相似。然而，其问题描述看起来与之前介绍的随机梯度下降算法非常不同，这是因为它并不涉及任何随机变量或期望值。因此，许多问题也随之而来。例如，这个算法是随机梯度下降吗？我们应该如何合理地从 $\{x_i\}_{i=1}^{n}$ 中抽取元素？是应该按照某种顺序对这些数字排列后一个接一个地使用它们，还是应该从集合中随机抽取？

这些问题看似很复杂，但实际上很简单。上面描述中确实涉及了泛及随机变量，不过我们可以通过让 $x_i$ 为随机变量，将上述表述转换为一个我们熟悉的泛及随机变量的描述。具体来说，设 $X$ 为定义在集合 $\{x_i\}_{i=1}^{n}$ 上的随机变量。假设其概率分布为均匀的，即 $p(X = x_i) = 1/n$。此时，式（6.16）中的优化问题就变成了

\[\min_wJ(w)=\frac{1}{n}\sum_{i=1}^nf(w,x_i)=\mathbb{E}[f(w,X)].\]

式中的第二个符号是严格成立的而不是近似。因此，（6.17）中的算法确实是求解上面这个优化问题的随机梯度下降法。而且从理论上来说，由于 $x_k$ 应该是独立同分布的，这要求每次获取的 $x_k$ 应该独立分布于 $\{x_i\}_{i=1}^{n}$ 中采样，因此不能将这些数字按照一定顺序排列进而一个一个地使用。此外，由于随机采样，因此有可能会重复取到 $\{x_i\}_{i=1}^{n}$ 中的同一个值。

6.4.4 小批量梯度下降¶

随机梯度下降在每次迭代中仅使用一个样本。下面介绍小批量梯度下降(mini-batch gradient descent, MBGD)，它在每次迭代中会使用更多样本。如果每次迭代使用所有样本，那么该算法被称为批量梯度下降（batch gradient descent, BGD）。

具体来说，我们的目标是最大化目标函数 $J(w) = \mathbb{E}[f(w, X)]$。我们有一组 $X$ 的随机样本 $\{x_i\}_{i=1}^n$。解决这个优化问题的 BGD, MBGD, SGD 算法分别是

\[\begin{aligned}&w_{k+1}=w_{k}-\alpha_{k}\frac{1}{n}\sum_{i=1}^{n}\nabla_{w}f(w_{k},x_{i}),&&\mathrm{(BGD)}\\&w_{k+1}=w_{k}-\alpha_{k}\frac{1}{m}\sum_{j\in\mathcal{I}_{k}}\nabla_{w}f(w_{k},x_{j}),&&\mathrm{(MBGD)}\\&w_{k+1}=w_{k}-\alpha_{k}\nabla_{w}f(w_{k},x_{k}).&&\mathrm{(SGD)}\end{aligned}\]

第一，BGD 算法在每次迭代中都用到了所有样本，因此 $(1/n) \sum_{i=1}^n \nabla_w f(w_k, x_i)$ 也更加接近于真实梯度 $\mathbb{E}[\nabla_w f(w, X)]$。第二，MBGD 算法在每次迭代中使用一个小批量样本，这批样本的集合记作 $I_k$，这批样本也是独立同分布的，样本数量设作 $|I_k| = m$。第三，SGD 算法在每次迭代中仅用到一个样本 $x_k$，它是时刻 $k$ 随机从 $\{x_i\}_{i=1}^n$ 中采样得到的。

MBGD 可以被视为 SGD 和 BGD 之间的中间版本。与 SGD 相比，MBGD 的随机性较小，收敛速度通常更快，因为它使用的样本比 SGD 多。与 BGD 相比，MBGD 不需要在每次迭代中使用所有样本，因此更加灵活。如果 $m = 1$，那么 MBGD 变成 SGD。然而，如果 $m = n$，MBGD 仍然与 BGD 有细微区别，这是因为 MBGD 使用 $n$ 个随机抽取的样本，这些样本可能是从无法涵盖 $\{x_i\}_{i=1}^n$ 的所有值，而 BGD 使用了 $\{x_i\}_{i=1}^n$ 中的所有值。

均值估计问题是展示上述分析的典型案例。具体而言，给定一组数值 $\{x_i\}_{i=1}^n$，我们的目标是计算均值 $\bar{x} = \sum_{i=1}^n x_i/n$。该问题可等价表述为以下优化问题：

\[\min_wJ(w)=\frac{1}{2n}\sum_{i=1}^n\|w-x_i\|^2,\]

其最优解为 $w^* = \bar{x}$。求解该问题的三种算法分别为：

\[\begin{aligned}&w_{k+1}=w_{k}-\alpha_{k}\frac{1}{n}\sum_{i=1}^{n}(w_{k}-x_{i})=w_{k}-\alpha_{k}(w_{k}-\bar{x}),\quad\mathrm{(BGD)}\\&w_{k+1}=w_{k}-\alpha_{k}\frac{1}{m}\sum_{j\in\mathcal{I}_{k}}(w_{k}-x_{j})=w_{k}-\alpha_{k}\left(w_{k}-\bar{x}_{k}^{(m)}\right),\quad\mathrm{(MBGD)}\\&w_{k+1}=w_k-\alpha_k(w_k-x_k),\quad\mathrm{(SGD)}\end{aligned}\]

其中 $\bar{x}^{(m)}_k = \sum_{j\in I_k} x_j/m$。此外，若 $\alpha_k =1/k$，上述方程组可通过如下公式解得：

\[\begin{aligned}&w_{k+1}=\frac{1}{k}\sum_{j=1}^{k}\bar{x}=\bar{x},\quad(\mathrm{BGD})\\&w_{k+1}=\frac{1}{k}\sum_{j=1}^{k}\bar{x}_{j}^{(m)},\quad(\mathrm{MBGD})\\&w_{k+1}=\frac{1}{k}\sum_{j=1}^{k}x_{j}.\quad(\mathrm{SGD})\end{aligned}\]

上式的推导与$(6.3)类比，在此省略。从上式可以看出，因为 BGD 在每次迭代中都使用了所有样本，所以它迭代一次就能得到最优解 $w^* = \bar{x}$。相比之下，MBGD 和 SGD 则需要更多次的迭代。

仿真实例参见前面给出的图 $6.5$。如图 $6.5$ 所示，不同批量大小的 MBGD 算法都能收敛到最优值，不过 $m = 50$ 时收敛最快，而 $m = 1$ 时收敛最慢。这与上文分析一致。即便如此，SGD 的收敛依然是较高效的，特别是当 $w_k$ 远离 $w^*$ 的时候。

6.4.5 随机梯度下降的收敛性¶

随机梯度下降（SGD）的收敛性严格证明如下。

Info

定理6.4. (随机梯度下降法的收敛性)。对于式$(6.13)$中的SGD算法，若满足以下条件，则 $w_k$几乎必然收敛至 $\nabla_w E[f(w,X)] =0$的根。

\[\begin{aligned}&(a)\quad0<c_{1}\leq\nabla_{w}^{2}f(w,X)\leq c_{2};\\&(b)\quad\sum_{k=1}^{\infty}a_{k}=\infty \;and\;\sum_{k=1}^{\infty}a_{k}^{2}<\infty;\\&(c)\quad\{x_{k}\}_{k=1}^{\infty}\;are\;i.i.d.\end{aligned}\]

定理$6.4$中的三个条件将在下文中讨论。

条件 (a) 要求 $f$ 是凸的，并且其二阶导数是有上下界的。这里 $w$ 和 $\nabla_w^2 f(w, X)$ 都是标量。当然，这个条件也可以推广到向量情形：当 $w$ 是一个向量时，$\nabla_w^2 f(w, X)$ 是海森矩阵 (Hessian) 矩阵。
条件 (b) 与 RM 算法一致。值得一提的是，实践中 $a_k$ 常被选择为一个很小的正数，此时 $\sum_{k=1}^{\infty} a_k^2 < \infty$ 不再成立。这么做的原因可参见第 6.2.1 节最后的讨论。

具体证明详见Box 6.1。

6.4-随机梯度下降

6.4.1 应用于期望估计¶

6.4.2 随机梯度下降的收敛形式¶

6.4.3 随机梯度下降的另一种描述¶

6.4.4 小批量梯度下降¶

6.4.5 随机梯度下降的收敛性¶

评论