为什么曲率影响收敛速度?
对光滑凸目标,前面的下降估计给出随 递减的界。在更强的条件下,我们可以证明每次更新都消去剩余误差的一个固定比例。想象二次损失的等高线是又长又窄的椭圆:能在陡峭方向安全使用的步长,沿平坦方向可能走得很慢。这两种曲率的比值,可以预示单一固定步长会遇到的困难。
我们研究确定性、无约束的目标;含噪声梯度和边界最小值需要另外分析。
假设与记号
定义 21.1.1
(光滑强凸目标)
设 二次连续可微,且存在 ,使每个 都满足
矩阵不等式按二次型理解。条件数定义为 。固定步长 的梯度下降为 。
下界推出 。特别地,以 代入,右边在 时趋于无穷,因此 有最小点 。强凸性保证它唯一,而整个 上的可微性给出 。上界则给出系数为 的相应二次上界。这些都是全局假设,不能由某一步观察到的 Hessian 自动推得。
收缩定理
定理 21.1.2
(平衡曲率的步长)
在上述假设下,取 及 。对每个整数 ,
若 ,一次更新便到达最小点。 的界可独立理解,或约定 。
证明
(沿线段把误差线性化)
写 。沿 到 的线段使用微积分基本定理,
对任意固定向量积分原来的二次型不等式,可得对称矩阵 亦满足 。故其每个特征值 都在 内,而且
代入指定步长,两端的因子分别为 和 。仿射函数的绝对值在区间上的最大值出现在端点,所以范数因子不大于 。反复使用便得到距离界。再在 使用二次上界,并利用该处梯度为零,便得目标值界。
证明透视
为什么 Hessian 改变仍可证明
两个曲率界各用了两次。下界给出 的存在与唯一,以及 ;有了后者,误差递推才可从 出发。两个界合起来,再把每个平均 Hessian 的特征值限制在 内。关键一步是积分形式的中值定理:它把非线性的更新化为精确的线性递推 ,其中对称矩阵随 而变。 可以每一步都不同,也不必与先前的矩阵可交换。我们先统一控制每一步的算子范数,然后才相乘,无须同时对角化。这正是假设必须是全局的原因:只知道起点的 Hessian,并不能控制其后各线段上的平均 Hessian。
对在两个端点均有特征值的对称正定二次函数,固定步长的最坏倍数是 。令两端大小平衡,得 ,其最小最坏倍数是 。这是针对这些曲率的最坏情况结论,并非每个初始向量都以此步长最快。 很大时, 接近一。重新缩放特征或采用有理据的预条件法可能改善条件数,但变换变量后须同时改写目标和更新公式。
另一条路:目标值下降
步长 可直接给出目标值界,完全不用距离 。
定理 21.1.3
(步长 的目标值下降)
在同一假设下,步长 的梯度下降对每个整数 满足
证明
(合并下降一步与梯度下界)
Hessian 上界给出 。取 ,得
强凸性也推出 。证法是把强凸性下界视为 的函数,在整个 上取最小:最小值在 处取得,等于 ,且不大于 。在第一式中取 ,两边减去 ,再代入第二式:
反复使用这个每步因子 ,便得结论。
这是直接控制目标值之差;它与前面的距离界使用不同步长,也使用不同的初始量。单看指数不能证明哪个数值界一定较小。
例题 21.1.4
(细长的二次函数)
设 ,。这里 、、,平衡步长为 。更新分别把两个坐标乘以 和 ,因此 ,,比 小。第二个坐标虽然正负交替,其绝对值仍在收缩。本例的目标值每一步恰好乘以 。
例题 21.1.5
(曲率会变化的非二次目标)
设 上的 。用逻辑斯谛函数 表示,有 及 。由于 ,假设在 、 时成立。因此 ,。
最小点满足 ,没有闭式解;数值上 。从 出发,梯度是 ,所以 。于是
线段上的平均曲率是 ,正如证明所需,落在 内。由于 ,迭代越过了 ,但误差仍按保证的因子收缩。
例题 21.1.6
(条件数如何决定迭代次数)
要以平衡步长保证 ,需要 ,即 ,其中 。
当 时,,,所以 足够。当 时,,,所以 足够。 增大十倍,保证所需的迭代次数也约增大十倍,因为 很大时 ,得 。在边界情形 ,,一步便足以达到任何容许误差。
反例模式
只有光滑性并不保证存在最小值
函数 的梯度是 -Lipschitz,但函数无下界,也没有最小点。取 ,梯度下降得到 ,任何非零起点都会发散。曲率上界不能代替曲率下界;即使非凸目标的迭代收敛,也未必收敛至全局最小点。
定理是在假设成立时的保证,不是训练效果的直接测量。神经网络的经验目标可能有负曲率或零曲率;有随机梯度噪声时,一般亦不能不加修改便把此确定性定理用于每条迭代轨迹。加二次惩罚后要得到强凸性,仍须假设其余部分凸,或另行证明 Hessian 下界。
常见错误
(只看一个 Hessian 就定出 与 )
这两个常数必须控制迭代点及通往 的线段可能经过的每一点处的 Hessian。在非二次例子中,,但 时 ;在其他目标上,起点的曲率可以远小于别处。只按 选的步长没有任何保证。
常见错误
(以为任何二次惩罚都带来强凸性)
加上 会把每个 Hessian 特征值提高 。若其余部分的曲率低于 ,和仍然不凸: 的二阶导数是 。只有其余部分凸时,惩罚才给出 。
练习与解答
快速检查
(对 和 ,找出 ,并计算平衡步长的 。)
二阶导数是常数。
解答 · 答案
Hessian 为 ,故取 ,,得到 。这是 的特殊情形。
快速检查
(在细长二次函数例子中,用 计算第一次更新及其目标值。)
每个坐标乘以 ,其中 是该坐标自己的曲率。
解答 · 答案
两个倍数是 和 ,所以 ,。一般目标值界只保证不大于 ;对这个起点它虽然有效,却不紧。
快速检查
(同一二次函数取 和 ,会发生什么?)
计算第二个坐标的倍数。
解答 · 答案
第二个倍数为 ,所以 。目标值维持 ,迭代不收敛。严格收缩的步长条件不能包括端点 。
快速检查
(若 、,平衡步长至少迭代多少次,才能保证距离不超过初始距离的百分之一?)
先计算 。
解答 · 答案
这时 ,需要 ,即 。因此 次足够。这只是最坏情况保证,不表示每个起点都需要十二次。