完整梯度要累加每个训练样本的贡献;随机梯度只用较小的随机样本,减少每次更新的计算量,同时引入噪声。我们量化这个噪声,并说明下降论证能保证什么、不能保证什么。
从有限和抽样
定义 12.1.1
(小批量梯度与梯度方差)
令 ,其中 可微且 。在固定的当前点 ,独立均匀地从 中有放回地抽取 ,其中整数 。对步长 ,定义
处的梯度方差为 。
当前点固定之后才重新抽取索引;同一个样本可以出现两次。以下所有期望都以 为条件。
定理 12.1.2
(小批量梯度的无偏性与方差)
以 为条件,
因此 。
证明
(先对每次抽样中心化,再展开平方)
令 。因为 服从均匀分布,,所以 ;由 的定义,。又 ,均值的结论随即成立。
展开 。当 时,两次抽样条件独立,故 。于是期望为 ,再除以 便得 。
最后,。中间一项因无偏性期望为零,由此得到 的公式。
证明透视
独立性与有放回抽样用在哪里
证明依赖三个要素。用完整梯度中心化,使每一项均值为零,这用到每个索引都是均匀的。各次抽样条件独立,使所有交叉项消失,所以在乘以 之前方差恰好是 。有放回抽样正好提供这种独立性;若不放回,交叉项为负, 时方差要乘以 ,取 便恰好回到完整梯度。相反的极端是把同一个索引重复使用 次, 只相当于一次抽样,方差仍为 。因子 来自 份相互独立的信息,而不是单纯来自取平均。
由光滑性得到期望下降界
定义 12.1.3
(梯度满足 Lipschitz 条件)
可微函数 的梯度是 -Lipschitz 的(其中 ),是指对所有 都有 。
命题 12.1.4
(小批量步的期望下降)
设 的梯度是 -Lipschitz 的, 为上述小批量步。对每个 ,
特别地,当 时,
证明
(二次上界,再取期望)
对任意两点 与 ,沿线段应用微积分基本定理,
其中用到了柯西–施瓦茨(Cauchy–Schwarz)不等式与 Lipschitz 条件。代入 ,得 。
以 为条件,,且 。取期望即得第一个不等式。当 时 ,便得第二个不等式。证明只用了无偏性与二阶矩,不需要凸性。
证明透视
哪个假设控制哪一项
线性项需要无偏性:它把带噪声的内积变成 。二次项才是噪声付出代价的地方,因为 并不是 的无偏估计,而是多出 。步长限制只用了一次,使 的系数至少为 ;若 ,该系数为负,即使 这个界也不保证下降。证明从未用到凸性,所以适用于非凸的 ;但也正因如此,它只能谈梯度的大小,不能谈到极小点的距离。
这只是上界,不保证每一步、甚至每一步的期望值都下降。在这些抽样假设下,较大的批量会减小所示的方差项,但每次更新需要计算更多分量梯度。
完整算一次更新
取 、、,并令 。则 、,所以 。两个分量梯度是 与 ,与 分别相差 和 ,故对每个 都有 。
例题 12.1.5
(只抽一个样本的一步)
在 处,取 、,抽到的梯度是 或 ,概率各为 。下一点分别是 或 ,因此
定理的第一个不等式,代入 、、,给出 ,与这个二次例子完全吻合。简化后的界是 ,虽然较松,但依然成立。
例题 12.1.6
(批量为二且出现重复抽样)
仍取 、,但令 。有序对 等可能。 与 的概率各为 ,分别给出 与 ; 与 合起来概率为 ,两者都给出 。下一点 为 、 或 ,对应的目标值是 、 与 。因此
的均值为 ,方差为 ,与定理一致。命题的第一个不等式给出 ,同样精确吻合。需要注意的边界情形是:有放回时 仍然是随机的,因为 这一对从未见到第二个样本。
反例模式
无偏梯度不一定使目标下降
有人可能认为,只要梯度估计无偏,就能保证 。在同一例子的极小点 处,分量梯度为 和 。取 及任意 ,下一点以相等概率为 或 ,两种情况下目标都由 上升到 。梯度估计无偏,但方差非零,而命题中的方差项正好出现:由于 ,界为 ,并且恰好取等。无偏性只控制线性项;要论证下降,还必须控制噪声。
从单步到平均保证
命题 12.1.7
(平均梯度平方界)
设 的梯度是 -Lipschitz 的,且有下界 。使用固定的 走 步,每一步在给定历史后抽取大小为 的新的独立小批量,且每个迭代点都有 。则
证明
(把条件界逐步叠加)
在 处、以历史为条件应用上一命题的第二个不等式,再用全期望公式取总期望,得 ;因为 而每一步只增加有限的量,所有期望都是有限的。移项并对 求和,函数值相互抵消:
两边乘以 即得结论。
左边是梯度范数平方的期望的平均,并不是对每个迭代点、也不是对到全局最优点的距离的界。固定步长时,第二项不一定随 增大而消失。若要其他类型的保证,需要凸性、更强的假设或不同的步长安排;上述计算并没有建立它们。
例题 12.1.8
(二次例子中的平均界)
沿用上面的例子,取 、、。此时 、、、,右边为 。
现在精确计算左边。令 。抽到的梯度是 ,其中 等可能,且与过去独立,所以 。交叉项的期望为零,故 满足 ,。解为 ;例如 、。对 的平均是 。 时为 , 时为 。
边界情形是极限:当 时,真实平均趋向 而不是零,而界趋向 。固定步长下,噪声下限确实存在,且与界的第二项同阶,因此这类证明无法使它消失。
常见错误
常见错误
(梯度无偏,不代表平方范数无偏)
因为 ,容易误写成 。正确的值是 。在例子的 处,,而抽到的梯度是 ,所以 。光滑性不等式的二次项看到的正是这个多出来的部分。
常见错误
(批量变为四倍,误差只减半,而不是减为四分之一)
的方差是 ,所以 使方差除以四;但误差 的典型大小是方差的平方根,只减为一半。把方差的因子当成误差本身的因子,会高估每多计算一个梯度所换来的好处。
习题
快速检查
(在例子的 处, 是多少?)
算出两个分量梯度及其平均。
解答 · 答案
在 处,分量梯度为 、,平均为 。偏差的平方都是 ,所以 ,与前面得到的常数 一致。
快速检查
(独立有放回抽样时, 由 变成 , 如何变化?)
使用方差公式。
解答 · 答案
变为原来的四分之一。因此 的均方根误差只减为一半,而不是四分之一。
快速检查
(若所有 相同, 是多少?下降界变成什么?)
比较每个分量梯度与 。
解答 · 答案
每个 都等于 ,所以对每个 都有 ,无论批量多大都有 。命题便给出确定性的下降 。
快速检查
(平均梯度界是否保证最后一个迭代点有小梯度?)
注意左边是对什么取平均。
解答 · 答案
单凭此界不行;它限制的是所有迭代点的期望的平均。在 、 的二次例子中, 对每个 都大于 ,所以最后一个迭代点的梯度在期望意义下同样不小。