让炼丹更科学一些（十）：单调性假设的拆与补

上文《让炼丹更科学一些（九）：经典自适应梯度算法》中，我们为形如 θ t+1=θ t−η t H−1 t g t θ t+1=θ t−η t H−1 t g t 的一般更新规则建立了收敛框架，并以它为出发点重新理解了AdaGrad等经典自适应梯度算法。不过，当时的完整结论依赖于两个前提：一是学习率 η t η t 取常数，二是预条件矩阵 H t H t 关于 t t 单调不减（半正定意义下）。

前者限制了学习率策略的自由度，后者则把RMSProp、Adam这类滑动平均型算法排除在了理论之外。本文尝试逐一拆掉这两个“脚手架”，把收敛理论推广到更一般的情形。

遗留问题[#](https://spaces.ac.cn/archives/11885#%E9%81%97%E7%95%99%E9%97%AE%E9%A2%98)

先回顾上一篇文章的核心结论。对一般的更新规则

θ t+1=θ t−η t H−1 t g t

θ t+1=θ t−η t H−1 t g t(1)

其中 g t=g(x t,θ t)g t=g(x t,θ t)是在样本 x t x t 处计算的随机梯度，H t H t 是（可能依赖于数据的）正定预条件矩阵，上文得到的收敛结论是

2 T∑t=1 η t[L(x t,θ t)−L(x t,θ∗)]≤R 2 tr(H T)+T∑t=1 η 2 t‖g t‖2 H−1 t 2∑t=1 T η t[L(x t,θ t)−L(x t,θ∗)]≤R 2 tr(H T)+∑t=1 T η 2 t∥g t∥2 H−1 t(2)

这里 θ∗θ∗是损失函数的最优点，R=max(‖θ 1−θ∗‖,⋯,‖θ T−θ∗‖)R=max(∥θ 1−θ∗∥,⋯,∥θ T−θ∗∥)是优化轨迹到最优点的最大距离；一个更实用的理解是：假设优化过程始终在一个直径不超过 R R 的超球内进行，必要时这可以通过投影操作来保证。 式(2)(2)的成立还有一个关键前提：对任意 t t，H t−H t−1 H t−H t−1 都是半正定的，简记为 H t⪰H t−1 H t⪰H t−1，即 H t H t 在半正定序下单调不减。上一篇在此前提下，进一步假设 η t η t 是常数 η η，整理得

1 T T∑t=1 L(x t,θ t)−1 T T∑t=1 L(x t,θ∗)≤R 2 2 T η tr(H T)+η 2 T T∑t=1‖g t‖2 H−1 t

1 T∑t=1 T L(x t,θ t)−1 T∑t=1 T L(x t,θ∗)≤R 2 2 T η tr(H T)+η 2 T∑t=1 T∥g t∥2 H−1 t(3)

然后再通过求右端关于 H H 的最小值，获得对最优预条件矩阵的理解——AdaGrad正是这一最优化的产物。而如果将求和换成滑动平均，我们可以衍生出RMSProp、Adam等优化器，但它无法保证 H t⪰H t−1 H t⪰H t−1，于是上述收敛理论便不再自动成立。 那么，接下来的问题自然有两个：1、如果 η t η t 不是常数，结论应当变成什么样？2、如果单调性 H t⪰H t−1 H t⪰H t−1 不恒成立，又该怎么办？

平均收敛[#](https://spaces.ac.cn/archives/11885#%E5%B9%B3%E5%9D%87%E6%94%B6%E6%95%9B)

先来考虑一般的动态学习率 η t η t。幸运的是，动态学习率不会引入任何证明上的困难，我们几乎可以复用前几篇的所有技巧。首先，按照《让炼丹更科学一些（二）：将结论推广到无界域》的思想，我们需要先对式(2)(2)两边取期望 E≜E x 1,x 2,⋯,x T

2 T∑t=1 η t E[L(θ t)−L(θ∗)]≤E[R 2 tr(H T)+T∑t=1 η 2 t‖g t‖2 H−1 t]

这里有几点注释：1、我们假设 η t 与数据 x 1,x 2,⋯,x t 无关；2、除此之外几乎所有变量都数据相关，比如 θ t 依赖于 x 1,x 2,⋯,x t−1，H t 也可能会依赖于数据（比如AdaGrad）；3、g t 是 g(x t,θ t)的简记，自然也不例外；4、R 如果按 max 定义，那么它是数据相关的，但如果按有界球理解，那么就无关，我们通常偏好后者。

现在两端除 2∑T t=1 η t，可得

∑T t=1 η t E[L(θ t)−L(θ∗)]∑T t=1 η t≤E[R 2 tr(H T)2∑T t=1 η t+∑T t=1 η 2 t‖g t‖2 H−1 t 2∑T t=1 η t]

这就得到了动态学习率的加权平均版的收敛结论。另一边，不等式(2)有一个更基本的原型是

2 T∑t=1 η t g t⋅(θ t−φ)≤R 2 tr(H T)+T∑t=1 η 2 t‖g t‖2 H−1 t

即其实是先得到上式，然后假设 L 的凸性以及取 φ=θ∗得到式(2)。基于(6)重复本节的证明得

∑T t=1 η t E[g t⋅(θ t−φ)]∑T t=1 η t≤E[R 2 tr(H T)2∑T t=1 η t+∑T t=1 η 2 t‖g t‖2 H−1 t 2∑T t=1 η t]

这是下一节要用到的不等式。注意这里的 g t 其实可以换成任意向量，因为 g t 取当前点梯度的唯一作用是通过凸性将它跟损失函数联系起来，但这里我们并没涉及到损失，所以单就这个不等式而言，g t 也是任意的。

终点收敛[#](https://spaces.ac.cn/archives/11885#%E7%BB%88%E7%82%B9%E6%94%B6%E6%95%9B)

对实践来说，终点收敛往往比平均收敛更有参考价值。而为了得到终点收敛的结论，我们直接引入《让炼丹更科学一些（六）：自上而下的精妙构造》证明过的一个不等式：

E[L(θ T)−L(θ∗)]≤1 w 1:T T∑t=1 w t E[g(x t,θ t)⋅(ψ t−θ∗)]

其中 ψ t+1−ψ t=w 1:T w t+1:T(θ t+1−θ t)。我们假设读者沿着本系列文章逐篇读下来，所以多数记号就不重复介绍了。不等式(8)的唯一条件是 L 的凸性，即只要假设 L 的凸性，以及 ψ 与 θ 的上述关系，那么就成立不等式(8)，跟具体的优化器无关。

不等式(8)的作用很直观，就是将终点收敛转化为平均收敛，从而可以对接上一节的结论。现在我们设 ψ t+1=ψ t−w t H−1 t g t，取 ψ 1=θ 1，那么由两者的关系可推得

θ t+1=θ t−w t w t+1:T w 1:T H−1 t g t

对不等式(8)的右端利用式(7)，我们得到

E[L(θ T)−L(θ∗)]≤E[R 2 tr(H T)2∑T t=1 w t+∑T t=1 w 2 t‖g t‖2 H−1 t 2∑T t=1 w t]

严格来说，这里的 R 应当是 ψ 轨迹到 θ∗的距离上界；在“有界球”的理解下，只要两条轨迹都处在同一个球内（必要时通过投影保证），就可以用同一个 R 表示。于是，只要 θ t+1=θ t−η t H−1 t g t 的 η t 能表示成 w t w t+1:T w 1:T，那么它就成立如上收敛结论，这就将之前标量版学习率的终点收敛结论推广到了矩阵版学习率。

这里可以马上得到一个符合实践的推论：根据《让炼丹更科学一些（五）：基于梯度精调学习率》的经验，如果我们假设‖g t‖2 H−1 t 接近常数（或者以某个常数为上界，对右端做进一步放缩），那么上式右端的最小值在 w t 为常数时取到，而 w t 为常数对应于 η t 的线性衰减，这就肯定了线性衰减的LR Schedule对一般的自适应学习率优化器的通用性。

除了上述隐式结论外，根据“显式版本”一节的思路，我们还可以得到显式结论：

E[L(θ T)−L(θ∗)]≤E[R 2 tr(H T)4 η 1:T+T−2∑t=1 η 2 t 4 η t+1:T‖g t‖2 H−1 t+η T−1 2(‖g T−1‖2 H−1 T−1+‖g T‖2 H−1 T)]

保证单调[#](https://spaces.ac.cn/archives/11885#%E4%BF%9D%E8%AF%81%E5%8D%95%E8%B0%83)

现在再来看第二个问题：当单调性 H t⪰H t−1 不恒成立时，该如何“补救”。一个朴素的想法是在原优化器上做尽可能小的改动，使其满足所希望的单调性。具体来说，设有半正定矩阵序列 H 1,H 2,⋯，我们希望找到一个与之最接近的新序列 ˆ H 1,ˆ H 2,⋯，并且恒成立 ˆ H t⪰ˆ H t−1。新序列的构造方式是

ˆ H 1=H 1,ˆ H t=ˆ H t−1+[H t−ˆ H t−1]+

其中[S]+是指将实对称矩阵 S 的所有特征值都取 max(⋅,0)后得到的新矩阵。这个构造方式很直观，容易看出 ˆ H t⪰ˆ H t−1 的必然性，同时可以证明它在迹度量下的最优性。

命题：在同时满足⪰ˆ H t−1 和⪰H t 的所有半正定矩阵 S 中，上述 ˆ H t 的迹最小。

证明：设 H t−ˆ H t−1 的特征值分解为 V Λ V⊤，记 N=V⊤(S−ˆ H t−1)V，那么两个条件分别给出 N⪰0 和 N⪰Λ，这又可以分别推出 N i,i≥0 和 N i,i≥Λ i,i，或等价地 N i,i≥max(Λ i,i,0)。于是

tr(S)−tr(ˆ H t−1)=tr(S−ˆ H t−1)=tr(N)≥tr([H t−ˆ H t−1]+)

取 S=ˆ H t=ˆ H t−1+[H t−ˆ H t−1]+正好能让等号成立。证毕。

推论：如果本就恒成立 H t⪰H t−1，那么 ˆ H t=H t。

有了 ˆ H t 后，我们用 ˆ H t 替代原本的 H t，即将更新规则改为

θ t+1=θ t−η t ˆ H−1 t g t

这样就保证了单调性，可以用回前面的收敛结论，只需将 H 换成 ˆ H，同时对原始优化器的改动最小化。特别地，当 H t 是对角矩阵时，ˆ H t 的更新规则可以简化成更直观的

ˆ H t=max(ˆ H t−1,H t)

这里的 max 是指逐元素取最大者。如果用它替换掉Adam的二阶矩，那么就得到了经典的AMSGrad优化器，它的收敛性质更好，代价是多出一组状态变量。同时，跟AdaGrad一样，保证 H t 单调性的优化器在实践中往往会有过于保守的担忧，所以AMSGrad实际上也没有流行起来。

回到源头[#](https://spaces.ac.cn/archives/11885#%E5%9B%9E%E5%88%B0%E6%BA%90%E5%A4%B4)

如果坚持不修改优化器，那么就只能设法从结论入手了。这一节我们回到源头，重新审视上一篇文章的证明过程，看看 H t 的单调性究竟用在了哪里？答案是，我们利用 H t−H t−1 的半正定性给出放缩 H t−H t−1⪯tr(H t−H t−1)I，然后

‖θ t−φ‖2 H t−H t−1≤‖θ t−φ‖2 tr(H t−H t−1)≤R 2 tr(H t−H t−1)

随后再

T∑t=1(‖θ t−φ‖2 H t−‖θ t+1−φ‖2 H t)=‖θ 1−φ‖2 H 1−‖θ T+1−φ‖2 H T+T∑t=2‖θ t−φ‖2 H t−H t−1≤R 2 tr(H 1)−‖θ T+1−φ‖2 H T+T∑t=2 R 2 tr(H t−H t−1)=R 2 tr(H T)

然而，放缩 H t−H t−1⪯tr(H t−H t−1)I 其实是很松的，还依赖于 H t−H t−1 的半正定性，我们之所以用它，是因为 tr 是线性函数，这使得最后的求和可以相消，剩下干净的 R 2 tr(H T)，便于分析。事实上，更紧凑且不需要假设 H t⪰H t−1 的放缩是

‖θ t−φ‖2 H t−H t−1≤‖θ t−φ‖2 λ max(H t−H t−1)≤R 2[λ max(H t−H t−1)]+

其中[x]+=max(x,0)，这等价于说 H t−H t−1⪯[λ max(H t−H t−1)]+I，λ max 是指最大特征值。利用这个结果，我们得到

T∑t=1(‖θ t−φ‖2 H t−‖θ t+1−φ‖2 H t)≤R 2(λ max(H 1)+T∑t=2[λ max(H t−H t−1)]+)

注意，λ max 不是线性函数，所以我们无法进一步相消了。不过，尽管这个结果不如 R 2 tr(H T)干净，但它在单调性成立时其实是总不差于（通常还严格更优）R 2 tr(H T)的，所以这实际是一个更强、更通用的结果。

新的结论[#](https://spaces.ac.cn/archives/11885#%E6%96%B0%E7%9A%84%E7%BB%93%E8%AE%BA)

回顾整个推导过程，单调性 H t⪰H t−1 唯一被用到的地方，就是上一节的放缩。因此，将它换成 λ max 版本后，前面所有的收敛结论都可以原封不动地推广到一般情形，只需要把 R 2 tr(H T)统一替换成 R 2 Λ T，其中

Λ T≜λ max(H 1)+T∑t=2[λ max(H t−H t−1)]+

具体地，式(7)的一般版本是：

∑T t=1 η t E[g t⋅(θ t−φ)]∑T t=1 η t≤E[R 2 Λ T 2∑T t=1 η t+∑T t=1 η 2 t‖g t‖2 H−1 t 2∑T t=1 η t]

加权平均版收敛结论是

∑T t=1 η t E[L(θ t)−L(θ∗)]∑T t=1 η t≤E[R 2 Λ T 2∑T t=1 η t+∑T t=1 η 2 t‖g t‖2 H−1 t 2∑T t=1 η t]

两个终点收敛结论分别是

E[L(θ T)−L(θ∗)]≤E[R 2 Λ T 2∑T t=1 w t+∑T t=1 w 2 t‖g t‖2 H−1 t 2∑T t=1 w t]E[L(θ T)−L(θ∗)]≤E[R 2 Λ T 4 η 1:T+T−2∑t=1 η 2 t 4 η t+1:T‖g t‖2 H−1 t+η T−1 2(‖g T−1‖2 H−1 T−1+‖g T‖2 H−1 T)]

留意 Λ T 有两个基本性质：第一，显然 Λ T 始终非负，所以新上界没有退化风险；第二，当 H t 的单调性成立时有[λ max(H t−H t−1)]+≤tr(H t−H t−1)，从而 Λ T≤tr(H T)，即新结论确实涵盖了旧结论。

延伸思考[#](https://spaces.ac.cn/archives/11885#%E5%BB%B6%E4%BC%B8%E6%80%9D%E8%80%83)

至此，第二个脚手架也被拆除。这样看来，H t 的非单调性并没有实质妨碍收敛证明，这是不是意味着RMSProp、Adam等优化器没有收敛问题了呢？

非也。能写出收敛结论，不代表能保证收敛。以式(22)为例，如果将 R,‖g t‖2 H−1 t 都视为与 t 和 T 无关的常数，那么右端的最小值在 η t 为常数时取到，此时 η 1:T 随 T 线性增长，若 Λ T 也随 T 线性甚至超线性增长，那么右端在 T→∞时便无法趋于零，即无法保证收敛。

从这个论证过程可以看出，其实这跟 H t 的单调与否并无直接关系，只要 Λ T 关于 T 的增长速度大于等于线性，那么便可能出现无法收敛的现象。对于AdaGrad来说，可以证明在梯度有界的假设下有 Λ T≤tr(H T)∼√T，即 Λ T 至多以 O(√T)速度增长，低于线性，所以收敛性得以保证。

但像RMSProp、Adam等优化器的滑动平均式预条件子，虽然 H t 本身更为平稳，但 H t−H t−1 的特征值可能反复交替变号，而 Λ T 累计的是每一步变化的[λ max]+，极端情况下，变化中有持续的、稳定的正方向，那它就会匀速增长，从而呈现线性的 Λ T，导致收敛失败。

不过，反过来想，这某种程度上也论证了RMSProp、Adam等实践有效的原理，因为一般 Λ T 的增长速度没那么糟糕，反而可能因为 H t 的平稳性，使得它们的 Λ T 增长比AdaGrad还要平缓，从而实践效果更佳。还有最重要的一点，我们现在只是讨论损失上界的收敛性，上界不收敛原则上无法断言损失不收敛。

文章小结[#](https://spaces.ac.cn/archives/11885#%E6%96%87%E7%AB%A0%E5%B0%8F%E7%BB%93)

本文在上一篇的收敛框架之上拆掉了两个“脚手架”：一是允许学习率 η t 动态变化，推导出相应的平均收敛和终点收敛结论，初步解释LR Decay对优化器的通用性；二是对于非单调的 H t，讨论了最小改动思想下的修正方案，以及推导了无需单调性假设的更一般的收敛结论。

总体来说，本文的信息密度较大，我们跳过了不少证明细节，因为关键的证明技巧在前面关于SGD的系列文章中已经详细给出，所以本文更多是直接给出关键的步骤与结果。

_转载到请包括本文地址：[https://spaces.ac.cn/archives/11885](https://spaces.ac.cn/archives/11885 "让炼丹更科学一些（十）：单调性假设的拆与补")_

_更详细的转载事宜请参考：_[《科学空间FAQ》](https://spaces.ac.cn/archives/6508#%E6%96%87%E7%AB%A0%E5%A6%82%E4%BD%95%E8%BD%AC%E8%BD%BD/%E5%BC%95%E7%94%A8 "《科学空间FAQ》")