动机
基本随机梯度在解附近仍可能有噪声。不同记录各自偏好的参数不一样,即使平均梯度为零,单项梯度也不消失。逐步减小步长能压低噪声,却也减慢移动。方差缩减采另一策略:偶尔算完整参考梯度,再用它修正便宜的抽样方向。修正应保留期望,同时抵消参考点已能解释的随机变动。
本节推导一个完整快照方法及其凸性收敛证明,通常称为 SVRG。名称不是核心;估计量才是:在当前位置与固定快照,使用同一抽取项算梯度,相减后加完整快照梯度。两次必须用同一索引;若独立抽两个索引,便改了噪声结构,不能套原来的抵消论证。
固定预条件器则改变哪些方向算长、哪些梯度算大。适当选择可把拉长的二次问题调整得均衡;没有依据的选择也可使步长证明失效。因此我们同时交代单项光滑界及采用的几何。
定义
定义 7.1.1
(平均强凸的有限和目标)
设 ,定义域为 。每项可微、凸,且梯度全局 Lipschitz,共同有效常数为 。另设 为 -强凸,,极小点为 。强凸的意思是
所以 ,且极小点唯一。每个单项凸是额外假设,不能只从平均强凸推出。
定义 7.1.2
(快照轮)
每轮固定快照 ,算 ,从 开始。内步重新独立均匀抽取 ,然后
做 步后,下一快照取平均 。
输出规则是证明的一部分;改用最后内步,需要另一论证。期望适当地给定快照及先前抽样;在这些信息固定后,新索引仍然均匀,才能使用条件无偏。
定理 / 命题
定理 7.1.3
(修正方向无偏且噪声消失)
固定 ,均匀抽 ,取 。则 ,且
当 ,方向恰为完整梯度,与索引无关;当两者均为 ,方向为零,即使个别项梯度仍非零。
定理 7.1.4
(完整一轮的收缩)
在上述凸性假设下取 ,新快照为指定内步平均,则
尤其 、 给 。做 轮后,期望目标差不多于初始的 。它不断言每一次实现的内步均单调改善。
上述整轮不等式其实在 都成立。要收缩则须 ;较严格的 令 ,所以可以通过足够大的轮长度达到收缩。
证明思路
证明
(减去切平面与中心化)
对一项减去在 的切平面,得 。凸性使 是 的极小点,梯度仍为 -Lipschitz。使用光滑上界,沿负梯度走 ,得到 。对项取平均,再用 ,即有
把 写成当前项梯度相对于 的差,减去快照同类差的中心化版本。两向量之差的范数平方不多于两者平方各乘二;中心化亦不增加二阶矩。在 各使用前式,便得第一定理。直接取期望则得无偏。这里限制的是二阶矩,不要把它与精确噪声方差混为一谈。
证明透视
为什么先减去切平面
不等式 只涉及所用函数的最小值,而一般来说 并不在 取最小值。减去切平面不改变梯度差 ;分项凸性正是在这里使用,用来保证 是 的极小点。由于 ,各 的平均就是 ,所以界回到目标差距。第二个想法是把 拆成在 处的部分和在 处的中心化部分:初等不等式 加上中心化,便给出常数 。
证明
(整轮距离的裂项求和)
收缩证明先展开更新后的距离平方:
条件无偏把中间项的 换成 ,凸性给出 ,二阶矩界则控制最后一项。合起来得到
整轮加总并舍去非负最后距离。初始距离由强凸限制为初始目标差的 倍。凸性又使平均位置的目标不多于平均目标值,除以 即得 。代入指定参数,两项各不多于四分之一。每轮先给定随机快照再重用论证,便得到跨轮期望界。
证明透视
整轮证明中每个假设各用一次
每个假设都在一个可辨认的位置进入。给定过去后重新均匀抽取的索引,使交叉项 的期望变成 ,而 的凸性把它限制为 。单项凸与光滑只通过二阶矩界进入,同时产生因子 及快照项 。强凸只用了一次,就是以 限制 ;这正是 第一项的来源。裂项求和能够闭合,是因为最后距离非负、可以舍去,而 的凸性把内步目标差的平均化为平均位置的目标差。最后内步没有这样的不等式,所以输出规则属于定理的一部分。
单项凸看似只是技术条件,因为没有它程序照样可以运行。下例显示二阶矩界本身会失效。
反例模式
一个凹单项足以破坏二阶矩界
断言:若平均 强凸且每项 -光滑,即使没有单项凸,第一定理的界仍成立。取 、、、。两项都是 -光滑,故 ; 是 -强凸,;但 是凹函数。在 、 时,方向 取值 或 ,故 。所声称的界是 ,反而更小。失效的一步是 :此处 ,在 处左边是 ,右边是 。仅靠光滑只能得到 ,需要另外分析;恢复原界的正是单项凸这一假设。
例题详解
例题 7.1.5
(可直接执行的有限和方法)
程序的第 项为对角二次函数 。平均 Hessian 是 ,所以 ;每项最大曲率至多十二,所以 。精确极小点为 。注意每次更新前先累积平均,与定理的输出规则完全相同。
import math
import random
data = [([1.0, 4.0], [1.0, 0.0]),
([2.0, 8.0], [0.0, 1.0]),
([3.0, 12.0], [-1.0, -1.0])]
def gradient(i, x):
h, center = data[i]
return [hj * (xj - aj) for hj, xj, aj in zip(h, x, center)]
def objective(x):
return math.fsum(0.5 * math.fsum(hj * (xj - aj)**2
for hj, xj, aj in zip(h, x, center))
for h, center in data) / len(data)
def svrg(start, epochs=5, seed=5):
n, d = len(data), len(start)
L, mu = 12.0, 2.0
eta, steps = 1 / (10 * L), math.ceil(50 * L / mu)
rng = random.Random(seed)
snapshot = list(start)
history = [objective(snapshot)]
for _ in range(epochs):
full = [0.0] * d
for i in range(n):
gi = gradient(i, snapshot)
full = [a + b / n for a, b in zip(full, gi)]
x = list(snapshot)
average = [0.0] * d
for _ in range(steps):
average = [a + b / steps for a, b in zip(average, x)]
i = rng.randrange(n)
now, old = gradient(i, x), gradient(i, snapshot)
direction = [a - b + c for a, b, c in zip(now, old, full)]
x = [a - eta * b for a, b in zip(x, direction)]
snapshot = average
history.append(objective(snapshot))
return snapshot, history
answer, history = svrg([3.0, 3.0])
optimum = [-1/3, -1/6]
assert objective(answer) >= objective(optimum) - 1e-12
print([round(x, 6) for x in answer])
print([round(value - objective(optimum), 6) for value in history])
断言只检查精确极小值的下界,不是证明所有种子收敛。所示执行的最后位置约为 [-0.332576, -0.166667];包括起点的目标差约为 51.222222, 0.552737, 0.020938, 0.000538, 0.000022, 0.000001。这核查某个实现及种子,不能反过来估计普遍收缩率。理论使用理想独立均匀索引,实际生成器提供可重复的演示。程序从不以观察到的下降代替对凸性及光滑性的核查。
例题 7.1.6
(抵消在极小点仍存在的噪声)
取 、,平均 的极小点是零,但两项梯度在此为负一及正一。普通抽样梯度仍有变动,修正后却是 ,任何索引都等于完整梯度。这个特殊问题每处都精确抵消;若两次抽不同索引,偏移量不再抵消,噪声便重新出现。
例题 7.1.7
(预条件器消除已知二次拉伸)
,普通下降步长一半,第二坐标被乘负四十九,因而不稳定。取 ,用 ,同一步长使两坐标都减半,目标变成四分之一。此预条件器使用已知曲率信息,不是任意目标都安全的装饰。
第三例提示了固定预条件器作用的一般描述。
概念视角几何
预条件就是坐标变换
固定对称正定 的意义很清楚:令 、。链式法则给变换梯度 ,在新坐标用同一算法,恰为原坐标的预条件更新。二次可微时,新 Hessian 是 。其上下界才是新光滑与强凸常数;只改善平均 Hessian,不自动限制每个抽样项的上界。
距离证明也随坐标改变。新坐标的距离平方 是原坐标差向量的 -二次型,而不是原欧氏(Euclidean)距离;因此不能保留旧常数,却把更新矩阵任意换掉。目标函数值仍对应同一位置,内步平均也因线性变换而相容,但解读距离及步长时必须使用同一几何。
拉伸例子的新 Hessian 是单位矩阵。一般问题建立或应用 可能很贵;对角近似便宜而省空间,稠密精确逆却昂贵。比较时应包含预处理及每次应用成本,不能只报告迭代减少。若预条件器随时间改变,亦不再是此处一个固定坐标变换。
精度规划与停止证书
若初始差至多 ,希望期望差不多于 ,指定参数下 轮足够。配合每轮成本,项梯度次数为 级别,常数已由定理明示。初始界及曲率常数仍须证明;看短暂轨迹后挑乐观数值,不能支持这个预算。
若完整梯度已可用,还有逐点的证书。
命题 7.1.8
(强凸下的梯度证书)
若 为 -强凸,极小点为 ,则对每一点 ,
证明
(最小化二次下界模型)
强凸在 给出:对每个 ,。右边是 的二次函数,在 处取最小值 。因此对每个 都有 ;取 即得结论。
所以快照完整梯度可在不知道精确极小值时,认证目标差已小。这是确定性不等式,亦适用于随机产生的位置。把完整梯度换成单次噪声方向便失去证书;浮点下极小的计算梯度也须留意相消与精度,不能任意解释到无限细容差。
常见错误
常见错误
(替换或移动快照梯度)
完整快照梯度是估计量的一部分,不能随便换成噪声小批量还引用原条件公式。近似快照方法可能有用,但须新分析。轮内快照也须固定;每步改快照,已改变估计量及证明。
常见错误
(只计内步而不计完整扫描)
不缓存的每轮需 次项梯度,额外工作向量为 ,不包括原数据。保存全部快照项梯度可减少重算,却要 空间。效果取决于完整扫描、内步、内存及目标精度的平衡。定理提供保守而透明的充分预算,不是普遍最快的参数。
常见错误
(在强凸以外引用线性收敛率)
强凸属指定目标及参数化的性质。过度参数化可能有多个解,神经网络目标常非凸。循环仍可运行,但此全局线性收敛证明不能认证它。把实验可行与定理涵盖范围分开,是正确使用方法的一部分。
总结
快照修正保留平均梯度,并在解附近抵消单项噪声。单项凸与光滑限制二阶矩,平均强凸则给指定平均输出的整轮收缩。固定预条件是坐标变换,须重新核查常数。算法、输出规则、假设及成本应放在同一论证中。
练习
快速检查
(第二例取 、,分别计算两个索引的修正方向,以及步长 的新位置。)
解答 · 答案
快照完整梯度为 。第一项修正为 ,第二项为 。新位置都是 。同一索引的偏移量以相反符号出现,才有精确抵消。
快速检查
(取 、、、。求定理中的收缩系数;多少轮足以使期望差上界至少缩小三十二倍?)
解答 · 答案
、。第一项是 ,第二项为 ,故 。五轮给出期望因子 ,并不保证每条单独轨迹恰好按此比率改善。
快速检查
(对 及 ,求变换后的 Hessian,并从 以步长 比较普通梯度下降与预条件梯度下降。)
解答 · 答案
。普通更新为 ,预条件后则是 ,两个坐标减半、二次目标变为四分之一。原坐标的步长对第二方向的曲率过大,导致剧烈放大。
快速检查
(为何使用最后内步、在两个单项梯度中独立抽取索引,或随时改变的预条件器,都不能只引用本节的整轮证明?各指出受影响的一步。)
解答 · 答案
证明用凸性把平均位置的目标限制于内步目标的平均,对最后一步没有同样的结论。同索引相减提供二阶矩界所需的抵消,独立索引改变了噪声计算。固定预条件器提供单一坐标变换与一组常数,变化的几何则需要新的控制。即使程序看起来相似,每种修改仍需要独立的定理。