前面的笔记分析了正定二次函数上的梯度下降:迭代是线性的,Hessian 的特征值精确描述误差。即使训练一个很小的神经网络,目标函数也可能既非二次函数,又非凸函数。此时谱分解的论证不再适用,我们需要改变问题。
一般情况下,不能指望证明算法收敛到全局最小点。但在梯度光滑且目标函数有下界时,可以证明梯度趋于零。本节从头推导这一保证,并用例子检验它的边界。
基本假设
以下设 满足:
- 光滑性: 连续可微,且对某个 ,梯度在整个空间上满足 Lipschitz 条件:
- 有下界: 存在实数 ,使得对所有 都有 。
只需是一个下界,不一定是下确界,也不一定能被取到。对非负损失, 总是可用。本文使用欧几里得(Euclid)范数。
固定步长梯度下降选择 和 ,然后令
下降引理
Lipschitz 条件控制梯度变化的快慢。先将它转化为关于函数值的结论:函数与其切平面相差多少?
定理 3.2.1
(下降引理)
在上述光滑性假设下,对所有 ,
证明
(沿线段对梯度积分)
固定 ,记 ,定义 为 。
由链式法则,。因为 连续,这个导数关于 连续,故微积分基本定理给出
将 写为它在 上的积分并相减,得到
Cauchy–Schwarz 不等式给出 ;Lipschitz 条件则给出 。因此
证明用到了梯度连续性和 Lipschitz 界:前者保证可应用微积分基本定理,后者控制被积函数;这里没有用到凸性。引理给出了切平面两侧的二次界,下面只需要上界:
每一步使目标下降
定理 3.2.2
(充分下降)
在基本假设和 下,每一步满足
证明
(代入梯度步)
记 ,则 。在上面的下降不等式中取 、:
记 。步长限制 恰好保证 。作为 的函数, 是开口向下的抛物线,在 取得最大值 。因此 使保证的下降量最大,实际下降量可以更大。
概念视角算法
梯度下降作为二次上界模型的极小化
下降不等式的上半部说明 位于 之上,并在 处与它相切。配方可见 恰好在 处取得极小值 。因此步长 就是“先取上界、再极小化”的一步,其保证下降量 正是模型本身的下降。步长 极小化的是曲率为 的模型,而它只在 时才是上界模型。
梯度平方可和与有限步界
定理 3.2.3
(固定步长梯度下降的驻点保证)
在基本假设和 下,
对于每个整数 ,
特别地,。
证明
(将下降不等式累加)
充分下降可改写为 。从 加到 ,右侧首尾相消:
最后一步正是使用下界的地方。
非负级数 的部分和因此有统一上界,所以级数收敛,其和也满足同一界。收敛级数的项趋于零,故 ,从而 。
对于有限步界,每一项都不小于前 项中的最小值,所以
两边除以 并取平方根即可;平方根递增,故最小平方范数等于最小范数的平方。
证明透视
各个假设在驻点证明中的位置
整个论证只有一个想法:每一步都用函数值“支付”它的梯度平方,而可用的函数值总量是有限的预算 。累加把局部的单步不等式变成全局的计数,过程中完全不需要知道迭代点在哪里。
光滑性只出现一次:通过下降引理得到单步不等式。步长限制通过 起作用:当 时,累加后的不等式变成 ,不含任何信息。下界只在最后一步 用到;没有它,预算就是无限的。例如 的梯度是常数,因而对每个 都是 -Lipschitz;迭代为 ,而每个 都有 。
证明控制的是一个和,而和只能控制最小项与平均值,不能控制每一项。所以有限步结论针对 ,而不是最后一个迭代点。凸性从未用到。
这个界按 衰减。要保证 ,取
便足够。
例题 3.2.4
(迭代次数的界可以有多悲观)
取 ,于是 、、。选 、,则 ,且
定理保证什么。 容差 对应的充分次数为
所以 次迭代保证足够。
实际发生什么。 迭代为 ,故 、。条件 即 ,首次在 成立,此时 。所以前 个迭代点中已经有满足容差的点。
检验。 第一步的充分下降预测 ,而 :单步不等式在这里取等号。 与 的差距来自累加:它假设每一步只得到保证的下降量,并消耗保证的预算。这个函数是强凸的,而定理没有用到这种结构,所以最坏情况的次数在这里远离实际。
迭代点能否收敛?
定义 3.2.5
(驻点与聚点)
若 ,称 为 的驻点。
如果某个子序列 收敛到 ,称 为序列 的聚点。
推论 3.2.6
(梯度下降的聚点都是驻点)
在基本假设和 下,梯度下降序列 的每个聚点都是 的驻点。若 有界,则至少存在一个聚点。
证明
(沿子序列取极限)
设 。梯度连续性给出 。由驻点保证,整个梯度范数序列趋于零,子序列也如此。极限唯一,故 。
若 有界,Bolzano–Weierstrass 定理给出一个收敛子序列,因而至少有一个聚点;由第一部分,它是驻点。
有界性是额外假设,基本假设并不能保证它;下面的 logistic 损失反例就没有聚点。
定理并不保证迭代点收敛、驻点是最小点(它可能是鞍点甚至最大点)、恢复数据生成模型的真实参数,也不保证 趋零的任何速率。这些结论需要额外结构,例如凸性、梯度支配不等式,或有界次水平集以及关于驻点集合的信息。
例题 3.2.7
(收敛到鞍点)
令 。则 ,可取 ,且
Hessian 的算子范数为 ,故 是 -Lipschitz,。取 ,两个坐标互不影响:
边界情形 。 从 出发,每一步都有 ,故 、。迭代点收敛到 ;这是 Hessian 为 的驻点,即鞍点,且 ,而最小值是 。定理的每个结论都成立,但极限不是最小点。
扰动后的起点。 从 出发,其中 。映射 满足 和 ,所以把 映入自身;又因为 ,在该区间上 。序列 递增且以 为上界,其极限 满足 ,故 。迭代点收敛到全局最小点 ,。到达哪个驻点取决于起点,而定理看不到这一点。
对二次连续可微的目标函数及足够小的固定步长,只有测度为零的起点集合会收敛到严格鞍点。
自然的下一个问题
梯度下降停在鞍点的情况有多常见?
对二次连续可微的目标函数及足够小的固定步长,只有测度为零的起点集合会收敛到严格鞍点。
在上例中,坏的起点恰好是水平直线族 ,即 之处;从其他每个起点出发,迭代都到达最小点。这是典型情况。若 二次连续可微且 ,梯度映射是微分同胚,而迭代收敛到某个 Hessian 有负特征值的驻点的起点,构成 Lebesgue 测度为零的集合。证明要用到稳定流形定理,超出本节范围;它也没有给出迭代点在鞍点附近停留多久的上界。
单参数 tanh 预测器
例题 3.2.8
(用 拟合目标值 )
考虑预测器 :它是一个权重为 、输入固定为 的 tanh 单元。用平方损失拟合目标 :
显然 ,所以可取 。
导数。 由 和 ,得
再用乘积法则:
一个有效的 Lipschitz 常数。 对所有实数 ,、,因而 。由三角不等式,
中值定理给出 ,故 可用。
这个界并非最紧。令 ,可得 ,例如 。定理只需要一个有效的 ,不要求最佳常数。
从 以 走一步。 因为 ,定理适用。由 、,
此时 ,充分下降给出
在 代入级数 ,可得 ,故
实际值严格小于初值 ,也小于保证的上界 。
最优点及本例的特殊之处。 由于 ,方程 必须有 。因此唯一驻点为
且 ,所以它是全局最小点。
在本例中还可证明迭代点收敛。对 ,单调下降给出 ,即 。因此 落在闭区间 内,而这个区间包含于 ,所以 保持有界。
每个聚点都是驻点,因此只能是 。有界序列若只有一个聚点 ,便收敛到 。这里用到了本例特有的有界次水平集和唯一驻点,不能把结论推广成一般定理。
反例:结论的边界
反例模式
下降但没有有限驻点:logistic 损失
令 。它严格为正,故可取 。其导数为
由于 ,有 ,因此 有效。这个函数根本没有驻点。
从任意有限的 出发,以任意固定 作梯度下降:
增量严格为正,故 严格递增。若它收敛到有限数 ,在更新式中取极限便得 ,矛盾。递增实数序列若无有限极限,必无上界,故 。
于是 且 :梯度趋零的结论成立,但既没有聚点,也没有最小点。梯度小并不意味着迭代点接近某个驻点。
以上是精确算术中的推导。浮点计算时, 很负会使 溢出。应使用稳定的改写
并使用专门的 log1p 函数计算 。
第二个反例针对步长假设,而不是 的形状。
反例模式
端点步长:L 分之二
令 ,其梯度 的 Lipschitz 常数恰为 。当 时,
若 ,迭代值在 之间交替, 始终不变。梯度范数始终为 ,并不趋零。
这与充分下降不矛盾,因为 ;它说明严格条件 不能省去。
常见错误
(把定理用于带 ReLU 折点的损失)
令 。当 时 ;当 时 。两式在 处相等,故 连续,于是很容易直接引用驻点保证。
但 处左导数为 ,右导数为 ,故 在此不可微。下降引理中沿直线应用微积分基本定理的证明不再适用,上述形式的驻点保证也不适用;下面最后一题说明,无论把哪个数当作“ 处的导数”,都挽救不了下降不等式。这类损失需要另行做非光滑分析。
如何理解训练中的保证
报告哪个迭代点。 有限步界针对前 个迭代点中的最优者,而非最后一个。算法每步本来就计算 ,因此可以记录
并报告 ,它满足该界。这只说明 的驻点程度。
常见错误
(把界当作关于最后一个迭代点的结论)
有限步界并不控制 。梯度范数不一定逐步下降:在下面关于正弦迭代的练习中,第一步之后梯度范数反而上升。证明控制的是前 个梯度范数平方之和,所以只有最优的迭代点,或平方范数的平均值,才满足这个界。例如在 中均匀抽取的指标 满足 。
确定性梯度与随机梯度。 上面的分析要求每一步使用 的精确梯度。随机训练将其替换成随机小批量估计,此时下降不等式逐路径不一定成立,需要另作论证,通常要取期望并对噪声和步长作假设。上述结论不能自动沿用。
经验损失与总体损失。 若 是固定数据集上的平均损失,定理只保证经验损失近似驻点,并不说明来自基础分布的新数据上的损失。训练梯度小是优化结论;测试表现好是另一个统计问题。
练习
练习 3.2.9
(设 。求使 为 -Lipschitz 的最小常数,以及有效下界 。直接证明下降引理,并写出 时 的界。)
核心
解答(4)
- 1
说明 有效
对某个介于 之间的 ,有 ,故 可用。
依据: 对 应用中值定理。
- 2
说明更小的常数不行
若对所有 有 ,除以 并令 得 ;取 得 。下界 有效且可取到。
- 3
直接验证下降引理
令 ,则
被积函数绝对值至多为 ,所以整个式子的绝对值至多为 。
- 4
应用驻点保证
满足 ,且 ,因此
练习 3.2.10
(设 、、。定理要求多少次迭代才能保证 ?与 比较。)
基础
解答(3)
- 1
检查步长并计算
因为 ,定理适用;。
- 2
解出 的充分条件
故 次足够。
- 3
与 比较
若 ,则 ,只需 。因为 在 最大,这是该界能给出的最小充分次数。这些都是最坏情况界的充分次数,并非实际表现的预测。
练习 3.2.11
(取 、。(a) 从 出发,证明 。(b) 证明迭代值留在 中,并确定其极限。(c) 从 出发会发生什么?)
核心
解答(4)
- 1
(a) 梯度范数可以上升
,故 。于是
由于 ,角度满足 。正弦在 严格递增,所以 。梯度范数不一定单调下降;定理并未声称如此。另一方面,充分下降给出 。
- 2
(b) 区间在迭代下不变
令 ,则 ,故 不递减。当 时,,因此 ;又 。
- 3
(b) 确定极限
关键一步
在区间内 ,故序列不递增且有下界,收敛到某个 ;它是驻点,因而 ,。又 ,故 ,是全局最小点。
依据: 确定极限的是单调性,而不是一般定理。
- 4
(c) 从最大点出发
,故所有 都有 。迭代点停在全局最大点:梯度为零,却离最优函数值最远。
练习 3.2.12
((a) 对 ,描述 和 时的梯度下降。(b) 对 ,证明不管把哪个数 指定为 处的导数,都不存在 使下降引理的双侧不等式在 附近成立。)
综合证明
解答(4)
- 1
(a) 线性递推
两种情形均有 。 时乘数为 ,迭代值在 和 之间交替,损失不变。 时 ;只要 ,就有 且 。
- 2
(b) 折点两侧的余项
令 。若 ,则 ;若 ,则 。
- 3
(b) 两个单侧极限都必须为零
关键一步
所以 从两侧都必须趋于零。右侧极限为 ,迫使 ;左侧极限为 ,迫使 。
依据: 把 除以 ,得 。
- 4
(b) 矛盾
∎与 两个要求不相容。折点并非记号造成的假象,它确实违反了定理要求的光滑性。
总结
若连续可微函数有下界且梯度为 -Lipschitz,则对固定步长 :
- 每步至少使 下降 ;
- 梯度范数的平方可和;
- 前 个梯度范数的最小值不超过 ;
- 每个聚点都是驻点;若迭代序列有界,至少存在一个聚点。
迭代点收敛、全局最优、参数恢复和函数值差距的收敛速率都需要额外结构。