12.4. 随机梯度下降¶ 在 SageMaker Studio Lab 中打开 Notebook
在前面的章节中，我们一直在训练过程中使用随机梯度下降，但没有解释它为什么有效。为了阐明这一点，我们刚刚在 12.3节 中描述了梯度下降的基本原理。在本节中，我们将更详细地讨论随机梯度下降。
%matplotlib inline
import math
import torch
from d2l import torch as d2l
%matplotlib inline
import math
from mxnet import np, npx
from d2l import mxnet as d2l
npx.set_np()
%matplotlib inline
import math
import tensorflow as tf
from d2l import tensorflow as d2l
12.4.1. 随机梯度更新¶
在深度学习中，目标函数通常是训练数据集中每个样本的损失函数的平均值。给定一个包含 \(n\) 个样本的训练数据集，我们假设 \(f_i(\mathbf{x})\) 是关于索引为 \(i\) 的训练样本的损失函数，其中 \(\mathbf{x}\) 是参数矢量。那么我们的目标函数是
目标函数在 \(\mathbf{x}\) 处的梯度计算如下
如果使用梯度下降，每个自变量迭代的计算成本为 \(\mathcal{O}(n)\)，它与 \(n\) 呈线性增长。因此，当训练数据集较大时，每次迭代的梯度下降计算成本会更高。
随机梯度下降（SGD）降低了每次迭代的计算成本。在随机梯度下降的每次迭代中，我们从数据样本中均匀随机抽样一个索引 \(i\in\{1,\ldots, n\}\)，并计算梯度 \(\nabla f_i(\mathbf{x})\) 来更新 \(\mathbf{x}\)
其中 \(\eta\) 是学习率。我们可以看到，每次迭代的计算成本从梯度下降的 \(\mathcal{O}(n)\) 降至常数 \(\mathcal{O}(1)\)。此外，我们要强调的是，随机梯度 \(\nabla f_i(\mathbf{x})\) 是完整梯度 \(\nabla f(\mathbf{x})\) 的无偏估计，因为
这意味着，平均而言，随机梯度是对梯度的良好估计。
现在，我们将通过向梯度中添加均值为0、方差为1的随机噪声来模拟随机梯度下降，并将其与梯度下降进行比较。
def f(x1, x2): # Objective function
return x1 ** 2 + 2 * x2 ** 2
def f_grad(x1, x2): # Gradient of the objective function
return 2 * x1, 4 * x2
def sgd(x1, x2, s1, s2, f_grad):
g1, g2 = f_grad(x1, x2)
# Simulate noisy gradient
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 1
eta = 0.1
lr = constant_lr # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))
epoch 50, x1: 0.225517, x2: -0.076646
def f(x1, x2): # Objective function
return x1 ** 2 + 2 * x2 ** 2
def f_grad(x1, x2): # Gradient of the objective function
return 2 * x1, 4 * x2
def sgd(x1, x2, s1, s2, f_grad):
g1, g2 = f_grad(x1, x2)
# Simulate noisy gradient
g1 += np.random.normal(0.0, 1, (1,))
g2 += np.random.normal(0.0, 1, (1,))
eta_t = eta * lr()
return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)
def constant_lr():
return 1
eta = 0.1
lr = constant_lr # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))
[22:10:25] ../src/storage/storage.cc:196: Using Pooled (Naive) StorageManager for CPU
epoch 50, x1: -0.472513, x2: 0.110780
def f(x1, x2): # Objective function
return x1 ** 2 + 2 * x2 ** 2
def f_grad(x1, x2): # Gradient of the objective function
return 2 * x1, 4 * x2
def sgd(x1, x2, s1, s2, f_grad):
g1, g2 = f_grad(x1, x2)
# Simulate noisy gradient
g1 += tf.random.normal([1], 0.0, 1)
g2 += tf.random.normal([1], 0.0, 1)
eta_t = eta * lr()
return (x1 - eta_t * g1, x2 - eta_t * g2, 0, 0)
def constant_lr():
return 1
eta = 0.1
lr = constant_lr # Constant learning rate
d2l.show_trace_2d(f, d2l.train_2d(sgd, steps=50, f_grad=f_grad))
epoch 50, x1: 0.228397, x2: -0.078016
正如我们所看到的，随机梯度下降中变量的轨迹比我们在 12.3节 中观察到的梯度下降的轨迹要嘈杂得多。这是由于梯度的随机性所致。也就是说，即使我们接近最小值，我们仍然受到瞬时梯度 \(\eta \nabla f_i(\mathbf{x})\) 注入的不确定性的影响。即使在50步之后，质量仍然不是很好。更糟糕的是，在额外的步骤之后它不会改善（我们鼓励你尝试更多的步骤来证实这一点）。这给我们留下了唯一的选择：改变学习率 \(\eta\)。然而，如果我们选择得太小，我们最初将不会取得任何有意义的进展。另一方面，如果我们选择得太大，我们将无法得到一个好的解决方案，如上所示。解决这些相互冲突的目标的唯一方法是随着优化的进展动态地降低学习率。
这也是在 sgd 步进函数中添加学习率函数 lr 的原因。在上面的例子中，任何学习率调度功能都处于休眠状态，因为我们将相关的 lr 函数设置为常量。
12.4.2. 动态学习率¶
用与时间相关的学习率 \(\eta(t)\) 替代 \(\eta\) 增加了控制优化算法收敛性的复杂性。特别是，我们需要弄清楚 \(\eta\) 应该以多快的速度衰减。如果太快，我们将过早停止优化。如果降低得太慢，我们会在优化上浪费太多时间。以下是随着时间推移调整 \(\eta\) 的一些基本策略（我们将在后面讨论更高级的策略）
在第一个分段常数场景中，我们降低学习率，例如，每当优化进展停滞时。这是训练深度网络的常用策略。或者，我们可以通过指数衰减更积极地降低它。不幸的是，这通常会导致在算法收敛前过早停止。一个流行的选择是多项式衰减，其中 \(\alpha = 0.5\)。在凸优化的情况下，有许多证明表明这个速率表现良好。
让我们看看指数衰减在实践中的样子。
def exponential_lr():
# Global variable that is defined outside this function and updated inside
global t
t += 1
return 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.758829, x2: -0.115584
def exponential_lr():
# Global variable that is defined outside this function and updated inside
global t
t += 1
return 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.820458, x2: 0.004701
def exponential_lr():
# Global variable that is defined outside this function and updated inside
global t
t += 1
return 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.874313, x2: -0.046612
正如预期的那样，参数的方差显著减少。然而，这是以未能收敛到最优解 \(\mathbf{x} = (0, 0)\) 为代价的。即使在1000次迭代后，我们仍然离最优解很远。事实上，该算法根本没有收敛。另一方面，如果我们使用多项式衰减，其中学习率随着步数的平方根倒数而衰减，那么仅在50步之后，收敛性就会变得更好。
def polynomial_lr():
# Global variable that is defined outside this function and updated inside
global t
t += 1
return (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.144834, x2: 0.041688
def polynomial_lr():
# Global variable that is defined outside this function and updated inside
global t
t += 1
return (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.025029, x2: 0.115820
def polynomial_lr():
# Global variable that is defined outside this function and updated inside
global t
t += 1
return (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.061363, x2: -0.130460
关于如何设置学习率，还有许多其他选择。例如，我们可以从一个小的速率开始，然后迅速提高，然后再降低，尽管速度更慢。我们甚至可以在较小和较大的学习率之间交替。存在各种各样的此类调度。目前，让我们关注那些可以进行全面理论分析的学习率调度，即在凸环境下的学习率。对于一般的非凸问题，很难获得有意义的收敛保证，因为一般情况下，最小化非线性非凸问题是NP难的。有关综述，请参见例如 Tibshirani 2015年的优秀讲义。
12.4.3. 凸目标函数的收敛性分析¶
以下针对凸目标函数的随机梯度下降收敛性分析是可选的，主要用于传达更多关于该问题的直觉。我们仅限于最简单的证明之一(Nesterov and Vial, 2000)。存在更为先进的证明技术，例如，当目标函数表现特别良好时。
假设目标函数 \(f(\boldsymbol{\xi}, \mathbf{x})\) 对于所有的 \(\boldsymbol{\xi}\) 都是在 \(\mathbf{x}\) 上的凸函数。更具体地，我们考虑随机梯度下降更新
其中 \(f(\boldsymbol{\xi}_t, \mathbf{x})\) 是关于在第 \(t\) 步从某个分布中抽取的训练样本 \(\boldsymbol{\xi}_t\) 的目标函数，而 \(\mathbf{x}\) 是模型参数。记
为期望风险，\(R^*\) 为其关于 \(\mathbf{x}\) 的最小值。最后，让 \(\mathbf{x}^*\) 为最小化器（我们假设它存在于 \(\mathbf{x}\) 定义的域内）。在这种情况下，我们可以跟踪在时间 \(t\) 的当前参数 \(\mathbf{x}_t\) 与风险最小化器 \(\mathbf{x}^*\) 之间的距离，并观察它是否随时间改善
我们假设随机梯度 \(\partial_\mathbf{x} f(\boldsymbol{\xi}_t, \mathbf{x})\) 的 \(\ell_2\) 范数由某个常数 \(L\) 界定，因此我们有
我们主要关心 \(\mathbf{x}_t\) 和 \(\mathbf{x}^*\) 之间的距离如何在期望上变化。事实上，对于任何特定的步骤序列，距离很可能会增加，这取决于我们遇到的 \(\boldsymbol{\xi}_t\)。因此，我们需要限制点积。由于对于任何凸函数 \(f\)，对于所有 \(\mathbf{x}\) 和 \(\mathbf{y}\)，都有 \(f(\mathbf{y}) \geq f(\mathbf{x}) + \langle f'(\mathbf{x}), \mathbf{y} - \mathbf{x} \rangle\) 成立，根据凸性我们有
将不等式 (12.4.9) 和 (12.4.10) 代入 (12.4.8)，我们得到在时间 \(t+1\) 的参数之间距离的界限如下
这意味着只要当前损失和最优损失之间的差值超过 \(\eta_t L^2/2\)，我们就能取得进展。由于这个差值必然会收敛到零，因此学习率 \(\eta_t\) 也需要消失。
接下来，我们对 (12.4.11) 取期望。这得到
最后一步是对 \(t \in \{1, \ldots, T\}\) 的不等式求和。由于和是伸缩的，并且通过舍去较低项，我们得到
请注意，我们利用了 \(\mathbf{x}_1\) 是给定的，因此期望可以被去掉。最后定义
因为
根据 Jensen 不等式（在 (12.2.3) 中设置 \(i=t\), \(\alpha_i = \eta_t/\sum_{t=1}^T \eta_t\)）和 \(R\) 的凸性，可以得出 \(E[R(\mathbf{x}_t)] \geq E[R(\bar{\mathbf{x}})]\)，因此
将此代入不等式 (12.4.13) 得到界限
其中 \(r^2 \stackrel{\textrm{def}}{=} \|\mathbf{x}_1 - \mathbf{x}^*\|^2\) 是对初始参数选择与最终结果之间距离的界限。简而言之，收敛速度取决于随机梯度范数的界限（\(L\)）以及初始参数值与最优值之间的距离（\(r\)）。请注意，这个界限是关于 \(\bar{\mathbf{x}}\) 而不是 \(\mathbf{x}_T\)。这是因为 \(\bar{\mathbf{x}}\) 是优化路径的平滑版本。当 \(r, L\) 和 \(T\) 已知时，我们可以选择学习率 \(\eta = r/(L \sqrt{T})\)。这给出了一个上限 \(rL/\sqrt{T}\)。也就是说，我们以 \(\mathcal{O}(1/\sqrt{T})\) 的速率收敛到最优解。
12.4.4. 随机梯度和有限样本¶
到目前为止，在讨论随机梯度下降时，我们有些随意。我们假设我们从某个分布 \(p(x, y)\) 中抽取实例 \(x_i\)，通常带有标签 \(y_i\)，并且我们用它来以某种方式更新模型参数。特别地，对于有限的样本大小，我们简单地认为离散分布 \(p(x, y) = \frac{1}{n} \sum_{i=1}^n \delta_{x_i}(x) \delta_{y_i}(y)\) 对于某些函数 \(\delta_{x_i}\) 和 \(\delta_{y_i}\) 允许我们对其执行随机梯度下降。
然而，这并不是我们实际做的。在本节的玩具示例中，我们只是向一个非随机梯度添加了噪声，即我们假装有配对 \((x_i, y_i)\)。事实证明，这里这样做是合理的（详见练习部分的详细讨论）。更麻烦的是，在之前的所有讨论中，我们显然没有这样做。相反，我们只迭代了所有实例一次。要理解为什么这样做更可取，请考虑相反的情况，即我们从离散分布中有放回地抽样 \(n\) 个观测值。随机选择一个元素 \(i\) 的概率是 \(1/n\)。因此，至少选择它一次的概率是
类似的推理表明，选择某个样本（即训练样本）恰好一次的概率由下式给出
与无放回抽样相比，有放回抽样导致方差增加和数据效率降低。因此，在实践中，我们执行后者（这也是本书中的默认选择）。最后请注意，对训练数据集的重复遍历会以不同的随机顺序进行。
12.4.5. 总结¶
对于凸问题，我们可以证明，对于广泛的学习率选择，随机梯度下降将收敛到最优解。
对于深度学习，情况通常并非如此。然而，对凸问题的分析为我们提供了如何进行优化的有用见解，即逐步降低学习率，但不要太快。
当学习率太小或太大时会出现问题。在实践中，合适的学习率通常只有在多次实验后才能找到。
当训练数据集中有更多样本时，计算梯度下降的每次迭代成本更高，因此在这些情况下首选随机梯度下降。
在非凸情况下，通常无法获得随机梯度下降的最优性保证，因为需要检查的局部最小值的数量可能呈指数级增长。
12.4.6. 练习¶
尝试不同的随机梯度下降学习率调度和不同的迭代次数。特别是，绘制与最优解 \((0, 0)\) 的距离作为迭代次数的函数。
证明对于函数 \(f(x_1, x_2) = x_1^2 + 2 x_2^2\)，向梯度添加正态噪声等价于最小化损失函数 \(f(\mathbf{x}, \mathbf{w}) = (x_1 - w_1)^2 + 2 (x_2 - w_2)^2\)，其中 \(\mathbf{x}\) 服从正态分布。
比较当您从 \(\{(x_1, y_1), \ldots, (x_n, y_n)\}\) 中有放回地抽样和无放回地抽样时，随机梯度下降的收敛性。
如果某个梯度（或者更确切地说，与其相关的某个坐标）始终比所有其他梯度大，您会如何更改随机梯度下降求解器？
假设 \(f(x) = x^2 (1 + \sin x)\)。 \(f\) 有多少个局部最小值？您能改变 \(f\)，使得要最小化它就需要评估所有的局部最小值吗？