上文《让炼丹更科学一些（九）：经典自适应梯度算法》中，我们为形如$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t \boldsymbol{H}_t^{-1}\boldsymbol{g}_t$的一般更新规则建立了收敛框架，并以它为出发点重新理解了AdaGrad等经典自适应梯度算法。不过，当时的完整结论依赖于两个前提：一是学习率$\eta_t$取常数，二是预条件矩阵$\boldsymbol{H}_t$关于$t$单调不减（半正定意义下）。
前者限制了学习率策略的自由度，后者则把RMSProp、Adam这类滑动平均型算法排除在了理论之外。本文尝试逐一拆掉这两个“脚手架”，把收敛理论推广到更一般的情形。
遗留问题 #
先回顾上一篇文章的核心结论。对一般的更新规则
\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t \boldsymbol{H}_t^{-1}\boldsymbol{g}_t\end{equation}
其中$\boldsymbol{g}_t = \boldsymbol{g}(\boldsymbol{x}_t, \boldsymbol{\theta}_t)$是在样本$\boldsymbol{x}_t$处计算的随机梯度，$\boldsymbol{H}_t$是（可能依赖于数据的）正定预条件矩阵，上文得到的收敛结论是
\begin{equation}\newcommand{tr}{\mathop{\text{tr}}}2\sum_{t=1}^T \eta_t [L(\boldsymbol{x}_t,\boldsymbol{\theta}_t) - L(\boldsymbol{x}_t,\boldsymbol{\theta}^*)] \leq R^2 \tr(\boldsymbol{H}_T) + \sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2 \label{leq:base}\end{equation}
这里$\boldsymbol{\theta}^*$是损失函数的最优点，$R = \max(\Vert\boldsymbol{\theta}_1 - \boldsymbol{\theta}^*\Vert,\cdots,\Vert\boldsymbol{\theta}_T - \boldsymbol{\theta}^*\Vert)$是优化轨迹到最优点的最大距离；一个更实用的理解是：假设优化过程始终在一个直径不超过$R$的超球内进行，必要时这可以通过投影操作来保证。
式$\eqref{leq:base}$的成立还有一个关键前提：对任意$t$，$\boldsymbol{H}_t - \boldsymbol{H}_{t-1}$都是半正定的，简记为$\boldsymbol{H}_t \succeq \boldsymbol{H}_{t-1}$，即$\boldsymbol{H}_t$在半正定序下单调不减。上一篇在此前提下，进一步假设$\eta_t$是常数$\eta$，整理得
\begin{equation}\frac{1}{T}\sum_{t=1}^T L(\boldsymbol{x}_t,\boldsymbol{\theta}_t) - \frac{1}{T}\sum_{t=1}^T L(\boldsymbol{x}_t,\boldsymbol{\theta}^*) \leq \frac{R^2}{2T\eta}\tr(\boldsymbol{H}_T) + \frac{\eta}{2T} \sum_{t=1}^T \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2\end{equation}
然后再通过求右端关于$\boldsymbol{H}$的最小值，获得对最优预条件矩阵的理解——AdaGrad正是这一最优化的产物。而如果将求和换成滑动平均，我们可以衍生出RMSProp、Adam等优化器，但它无法保证$\boldsymbol{H}_t \succeq \boldsymbol{H}_{t-1}$，于是上述收敛理论便不再自动成立。
那么，接下来的问题自然有两个：1、如果$\eta_t$不是常数，结论应当变成什么样？2、如果单调性$\boldsymbol{H}_t \succeq \boldsymbol{H}_{t-1}$不恒成立，又该怎么办？
平均收敛 #
先来考虑一般的动态学习率$\eta_t$。幸运的是，动态学习率不会引入任何证明上的困难，我们几乎可以复用前几篇的所有技巧。首先，按照《让炼丹更科学一些（二）：将结论推广到无界域》的思想，我们需要先对式$\eqref{leq:base}$两边取期望$\mathbb{E}\triangleq \mathbb{E}_{\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_T}$
\begin{equation}2\sum_{t=1}^T \eta_t \mathbb{E}[L(\boldsymbol{\theta}_t) - L(\boldsymbol{\theta}^*)] \leq \mathbb{E}\left[R^2 \tr(\boldsymbol{H}_T) + \sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2\right]\end{equation}
这里有几点注释：1、我们假设$\eta_t$与数据$\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_t$无关；2、除此之外几乎所有变量都数据相关，比如$\boldsymbol{\theta}_t$依赖于$\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_{t-1}$，$\boldsymbol{H}_t$也可能会依赖于数据（比如AdaGrad）；3、$\boldsymbol{g}_t$是$\boldsymbol{g}(\boldsymbol{x}_t,\boldsymbol{\theta}_t)$的简记，自然也不例外；4、$R$如果按$\max$定义，那么它是数据相关的，但如果按有界球理解，那么就无关，我们通常偏好后者。
现在两端除$2\sum_{t=1}^T \eta_t$，可得
\begin{equation}\frac{\sum_{t=1}^T \eta_t \mathbb{E}[L(\boldsymbol{\theta}_t) - L(\boldsymbol{\theta}^*)]}{\sum_{t=1}^T \eta_t} \leq \mathbb{E}\left[\frac{R^2 \tr(\boldsymbol{H}_T)}{2\sum_{t=1}^T \eta_t} + \frac{\sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2}{2\sum_{t=1}^T \eta_t}\right]\end{equation}
这就得到了动态学习率的加权平均版的收敛结论。另一边，不等式$\eqref{leq:base}$有一个更基本的原型是
\begin{equation}2\sum_{t=1}^T \eta_t \boldsymbol{g}_t \cdot (\boldsymbol{\theta}_t -\boldsymbol{\varphi}) \leq R^2 \tr(\boldsymbol{H}_T) + \sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2 \label{leq:base-base}\end{equation}
即其实是先得到上式，然后假设$L$的凸性以及取$\boldsymbol{\varphi}=\boldsymbol{\theta}^*$得到式$\eqref{leq:base}$。基于$\eqref{leq:base-base}$重复本节的证明得
\begin{equation}\frac{\sum_{t=1}^T \eta_t \mathbb{E}[\boldsymbol{g}_t \cdot (\boldsymbol{\theta}_t -\boldsymbol{\varphi})]}{\sum_{t=1}^T \eta_t} \leq \mathbb{E}\left[\frac{R^2 \tr(\boldsymbol{H}_T)}{2\sum_{t=1}^T \eta_t} + \frac{\sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2}{2\sum_{t=1}^T \eta_t}\right]\label{leq:avg-g}\end{equation}
这是下一节要用到的不等式。注意这里的$\boldsymbol{g}_t$其实可以换成任意向量，因为$\boldsymbol{g}_t$取当前点梯度的唯一作用是通过凸性将它跟损失函数联系起来，但这里我们并没涉及到损失，所以单就这个不等式而言，$\boldsymbol{g}_t$也是任意的。
终点收敛 #
对实践来说，终点收敛往往比平均收敛更有参考价值。而为了得到终点收敛的结论，我们直接引入《让炼丹更科学一些（六）：自上而下的精妙构造》证明过的一个不等式：
\begin{equation}\mathbb{E}[L(\boldsymbol{\theta}_T) - L(\boldsymbol{\theta}^*)] \leq \frac{1}{w_{1:T}}\sum_{t=1}^T w_t \mathbb{E}[\boldsymbol{g}(\boldsymbol{x}_t, \boldsymbol{\theta}_t)\cdot(\boldsymbol{\psi}_t - \boldsymbol{\theta}^*)]\label{leq:last-core}\end{equation}
其中$\boldsymbol{\psi}_{t+1} - \boldsymbol{\psi}_t = \frac{w_{1:T}}{w_{t+1:T}}(\boldsymbol{\theta}_{t+1} - \boldsymbol{\theta}_t)$。我们假设读者沿着本系列文章逐篇读下来，所以多数记号就不重复介绍了。不等式$\eqref{leq:last-core}$的唯一条件是$L$的凸性，即只要假设$L$的凸性，以及$\boldsymbol{\psi}$与$\boldsymbol{\theta}$的上述关系，那么就成立不等式$\eqref{leq:last-core}$，跟具体的优化器无关。
不等式$\eqref{leq:last-core}$的作用很直观，就是将终点收敛转化为平均收敛，从而可以对接上一节的结论。现在我们设$\boldsymbol{\psi}_{t+1} = \boldsymbol{\psi}_t - w_t \boldsymbol{H}_t^{-1} \boldsymbol{g}_t$，取$\boldsymbol{\psi}_1 = \boldsymbol{\theta}_1$，那么由两者的关系可推得
\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \frac{w_t w_{t+1:T}}{w_{1:T}}\boldsymbol{H}_t^{-1} \boldsymbol{g}_t\end{equation}
对不等式$\eqref{leq:last-core}$的右端利用式$\eqref{leq:avg-g}$，我们得到
\begin{equation}\mathbb{E}[L(\boldsymbol{\theta}_T) - L(\boldsymbol{\theta}^*)] \leq \mathbb{E}\left[\frac{R^2 \tr(\boldsymbol{H}_T)}{2\sum_{t=1}^T w_t} + \frac{\sum_{t=1}^T w_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2}{2\sum_{t=1}^T w_t}\right]\end{equation}
严格来说，这里的$R$应当是$\boldsymbol{\psi}$轨迹到$\boldsymbol{\theta}^*$的距离上界；在“有界球”的理解下，只要两条轨迹都处在同一个球内（必要时通过投影保证），就可以用同一个$R$表示。于是，只要$\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t \boldsymbol{H}_t^{-1}\boldsymbol{g}_t$的$\eta_t$能表示成$\frac{w_t w_{t+1:T}}{w_{1:T}}$，那么它就成立如上收敛结论，这就将之前标量版学习率的终点收敛结论推广到了矩阵版学习率。
这里可以马上得到一个符合实践的推论：根据《让炼丹更科学一些（五）：基于梯度精调学习率》的经验，如果我们假设$\Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2$接近常数（或者以某个常数为上界，对右端做进一步放缩），那么上式右端的最小值在$w_t$为常数时取到，而$w_t$为常数对应于$\eta_t$的线性衰减，这就肯定了线性衰减的LR Schedule对一般的自适应学习率优化器的通用性。
除了上述隐式结论外，根据“显式版本”一节的思路，我们还可以得到显式结论：
\begin{equation}\mathbb{E}[L(\boldsymbol{\theta}_T) - L(\boldsymbol{\theta}^*)] \leq \mathbb{E}\left[\frac{R^2\tr(\boldsymbol{H}_T)}{4\eta_{1:T}} + \sum_{t=1}^{T-2} \frac{\eta_t^2}{4\eta_{t+1:T}} \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2 + \frac{\eta_{T-1}}{2}\Big(\Vert\boldsymbol{g}_{T-1}\Vert_{\boldsymbol{H}_{T-1}^{-1}}^2 + \Vert\boldsymbol{g}_T\Vert_{\boldsymbol{H}_T^{-1}}^2\Big)\right]\label{leq:last-xianshi}\end{equation}
保证单调 #
现在再来看第二个问题：当单调性$\boldsymbol{H}_t \succeq \boldsymbol{H}_{t-1}$不恒成立时，该如何“补救”。一个朴素的想法是在原优化器上做尽可能小的改动，使其满足所希望的单调性。具体来说，设有半正定矩阵序列$\boldsymbol{H}_1,\boldsymbol{H}_2,\cdots$，我们希望找到一个与之最接近的新序列$\hat{\boldsymbol{H}}_1,\hat{\boldsymbol{H}}_2,\cdots$，并且恒成立$\hat{\boldsymbol{H}}_t \succeq \hat{\boldsymbol{H}}_{t-1}$。新序列的构造方式是
\begin{equation}\hat{\boldsymbol{H}}_1 = \boldsymbol{H}_1,\qquad \hat{\boldsymbol{H}}_t = \hat{\boldsymbol{H}}_{t-1} + [\boldsymbol{H}_t - \hat{\boldsymbol{H}}_{t-1}]_+\end{equation}
其中$[\boldsymbol{S}]_+$是指将实对称矩阵$\boldsymbol{S}$的所有特征值都取$\max(\cdot,0)$后得到的新矩阵。这个构造方式很直观，容易看出$\hat{\boldsymbol{H}}_t \succeq \hat{\boldsymbol{H}}_{t-1}$的必然性，同时可以证明它在迹度量下的最优性。
命题：在同时满足$\succeq \hat{\boldsymbol{H}}_{t-1}$和$\succeq\boldsymbol{H}_t$的所有半正定矩阵$\boldsymbol{S}$中，上述$\hat{\boldsymbol{H}}_t$的迹最小。
证明：设$\boldsymbol{H}_t - \hat{\boldsymbol{H}}_{t-1}$的特征值分解为$\boldsymbol{V}\boldsymbol{\Lambda}\boldsymbol{V}^{\top}$，记$\boldsymbol{N}=\boldsymbol{V}^{\top}(\boldsymbol{S} - \hat{\boldsymbol{H}}_{t-1})\boldsymbol{V}$，那么两个条件分别给出$\boldsymbol{N}\succeq\boldsymbol{0}$和$\boldsymbol{N}\succeq\boldsymbol{\Lambda}$，这又可以分别推出$N_{i,i}\geq 0$和$N_{i,i}\geq \Lambda_{i,i}$，或等价地$N_{i,i}\geq \max(\Lambda_{i,i},0)$。于是
\begin{equation}\tr(\boldsymbol{S}) - \tr(\hat{\boldsymbol{H}}_{t-1}) = \tr(\boldsymbol{S} - \hat{\boldsymbol{H}}_{t-1}) = \tr(\boldsymbol{N}) \geq \tr([\boldsymbol{H}_t - \hat{\boldsymbol{H}}_{t-1}]_+)\end{equation}
取$\boldsymbol{S} = \hat{\boldsymbol{H}}_t = \hat{\boldsymbol{H}}_{t-1} + [\boldsymbol{H}_t - \hat{\boldsymbol{H}}_{t-1}]_+$正好能让等号成立。证毕。推论：如果本就恒成立$\boldsymbol{H}_t\succeq\boldsymbol{H}_{t-1}$，那么$\hat{\boldsymbol{H}}_t=\boldsymbol{H}_t$。
有了$\hat{\boldsymbol{H}}_t$后，我们用$\hat{\boldsymbol{H}}_t$替代原本的$\boldsymbol{H}_t$，即将更新规则改为
\begin{equation}\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \eta_t \hat{\boldsymbol{H}}_t^{-1}\boldsymbol{g}_t\end{equation}
这样就保证了单调性，可以用回前面的收敛结论，只需将$\boldsymbol{H}$换成$\hat{\boldsymbol{H}}$，同时对原始优化器的改动最小化。特别地，当$\boldsymbol{H}_t$是对角矩阵时，$\hat{\boldsymbol{H}}_t$的更新规则可以简化成更直观的
\begin{equation}\hat{\boldsymbol{H}}_t = \max(\hat{\boldsymbol{H}}_{t-1}, \boldsymbol{H}_t)\end{equation}
这里的$\max$是指逐元素取最大者。如果用它替换掉Adam的二阶矩，那么就得到了经典的AMSGrad优化器，它的收敛性质更好，代价是多出一组状态变量。同时，跟AdaGrad一样，保证$\boldsymbol{H}_t$单调性的优化器在实践中往往会有过于保守的担忧，所以AMSGrad实际上也没有流行起来。
回到源头 #
如果坚持不修改优化器，那么就只能设法从结论入手了。这一节我们回到源头，重新审视上一篇文章的证明过程，看看$\boldsymbol{H}_t$的单调性究竟用在了哪里？答案是，我们利用$\boldsymbol{H}_t - \boldsymbol{H}_{t-1}$的半正定性给出放缩$\boldsymbol{H}_t - \boldsymbol{H}_{t-1}\preceq \tr(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})\boldsymbol{I}$，然后
\begin{equation}\Vert\boldsymbol{\theta}_t-\boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t-\boldsymbol{H}_{t-1}}^2 \leq \Vert\boldsymbol{\theta}_t-\boldsymbol{\varphi}\Vert^2 \tr(\boldsymbol{H}_t - \boldsymbol{H}_{t-1}) \leq R^2 \tr(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})\end{equation}
随后再
\begin{equation}\begin{aligned}\require{cancel}
\sum_{t=1}^T (\Vert\boldsymbol{\theta}_t - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t}^2 - \Vert\boldsymbol{\theta}_{t+1} - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t}^2) =&\, \Vert\boldsymbol{\theta}_1 - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_1}^2 - \Vert\boldsymbol{\theta}_{T+1} - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_T}^2 + \sum_{t=2}^T \Vert\boldsymbol{\theta}_t - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t - \boldsymbol{H}_{t-1}}^2 \\
\leq&\, R^2 \tr(\boldsymbol{H}_1) \cancel{- \Vert\boldsymbol{\theta}_{T+1} - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_T}^2} + \sum_{t=2}^T R^2 \tr(\boldsymbol{H}_t - \boldsymbol{H}_{t-1}) \\
=&\, R^2 \tr(\boldsymbol{H}_T)
\end{aligned}\end{equation}
然而，放缩$\boldsymbol{H}_t - \boldsymbol{H}_{t-1}\preceq \tr(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})\boldsymbol{I}$其实是很松的，还依赖于$\boldsymbol{H}_t - \boldsymbol{H}_{t-1}$的半正定性，我们之所以用它，是因为$\tr$是线性函数，这使得最后的求和可以相消，剩下干净的$R^2 \tr(\boldsymbol{H}_T)$，便于分析。事实上，更紧凑且不需要假设$\boldsymbol{H}_t \succeq \boldsymbol{H}_{t-1}$的放缩是
\begin{equation}\Vert\boldsymbol{\theta}_t-\boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t-\boldsymbol{H}_{t-1}}^2 \leq \Vert\boldsymbol{\theta}_t-\boldsymbol{\varphi}\Vert^2 \lambda_{\max}(\boldsymbol{H}_t - \boldsymbol{H}_{t-1}) \leq R^2 [\lambda_{\max}(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})]_+\end{equation}
其中$[x]_+ = \max(x,0)$，这等价于说$\boldsymbol{H}_t - \boldsymbol{H}_{t-1}\preceq [\lambda_{\max}(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})]_+\boldsymbol{I}$，$\lambda_{\max}$是指最大特征值。利用这个结果，我们得到
\begin{equation}\sum_{t=1}^T (\Vert\boldsymbol{\theta}_t - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t}^2 - \Vert\boldsymbol{\theta}_{t+1} - \boldsymbol{\varphi}\Vert_{\boldsymbol{H}_t}^2) \leq R^2 \left(\lambda_{\max}(\boldsymbol{H}_1) + \sum_{t=2}^T [\lambda_{\max}(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})]_+ \right)\end{equation}
注意，$\lambda_{\max}$不是线性函数，所以我们无法进一步相消了。不过，尽管这个结果不如$R^2 \tr(\boldsymbol{H}_T)$干净，但它在单调性成立时其实是总不差于（通常还严格更优）$R^2 \tr(\boldsymbol{H}_T)$的，所以这实际是一个更强、更通用的结果。
新的结论 #
回顾整个推导过程，单调性$\boldsymbol{H}_t \succeq \boldsymbol{H}_{t-1}$唯一被用到的地方，就是上一节的放缩。因此，将它换成$\lambda_{\max}$版本后，前面所有的收敛结论都可以原封不动地推广到一般情形，只需要把$R^2 \tr(\boldsymbol{H}_T)$统一替换成$R^2 \Lambda_T$，其中
\begin{equation}\Lambda_T \triangleq \lambda_{\max}(\boldsymbol{H}_1) + \sum_{t=2}^T [\lambda_{\max}(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})]_+\end{equation}
具体地，式$\eqref{leq:avg-g}$的一般版本是：
\begin{equation}\frac{\sum_{t=1}^T \eta_t \mathbb{E}[\boldsymbol{g}_t \cdot (\boldsymbol{\theta}_t -\boldsymbol{\varphi})]}{\sum_{t=1}^T \eta_t} \leq \mathbb{E}\left[\frac{R^2 \Lambda_T}{2\sum_{t=1}^T \eta_t} + \frac{\sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2}{2\sum_{t=1}^T \eta_t}\right]\end{equation}
加权平均版收敛结论是
\begin{equation}\frac{\sum_{t=1}^T \eta_t \mathbb{E}[L(\boldsymbol{\theta}_t) - L(\boldsymbol{\theta}^*)]}{\sum_{t=1}^T \eta_t} \leq \mathbb{E}\left[\frac{R^2 \Lambda_T}{2\sum_{t=1}^T \eta_t} + \frac{\sum_{t=1}^T \eta_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2}{2\sum_{t=1}^T \eta_t}\right]\label{leq:avg-gen}\end{equation}
两个终点收敛结论分别是
\begin{align}\mathbb{E}[L(\boldsymbol{\theta}_T) - L(\boldsymbol{\theta}^*)] \leq&\, \mathbb{E}\left[\frac{R^2 \Lambda_T}{2\sum_{t=1}^T w_t} + \frac{\sum_{t=1}^T w_t^2 \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2}{2\sum_{t=1}^T w_t}\right] \\
\mathbb{E}[L(\boldsymbol{\theta}_T) - L(\boldsymbol{\theta}^*)] \leq&\, \mathbb{E}\left[\frac{R^2 \Lambda_T}{4\eta_{1:T}} + \sum_{t=1}^{T-2} \frac{\eta_t^2}{4\eta_{t+1:T}} \Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2 + \frac{\eta_{T-1}}{2}\Big(\Vert\boldsymbol{g}_{T-1}\Vert_{\boldsymbol{H}_{T-1}^{-1}}^2 + \Vert\boldsymbol{g}_T\Vert_{\boldsymbol{H}_T^{-1}}^2\Big)\right]\end{align}
留意$\Lambda_T$有两个基本性质：第一，显然$\Lambda_T$始终非负，所以新上界没有退化风险；第二，当$\boldsymbol{H}_t$的单调性成立时有$[\lambda_{\max}(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})]_+ \leq \tr(\boldsymbol{H}_t - \boldsymbol{H}_{t-1})$，从而$\Lambda_T \leq \tr(\boldsymbol{H}_T)$，即新结论确实涵盖了旧结论。
延伸思考 #
至此，第二个脚手架也被拆除。这样看来，$\boldsymbol{H}_t$的非单调性并没有实质妨碍收敛证明，这是不是意味着RMSProp、Adam等优化器没有收敛问题了呢？
非也。能写出收敛结论，不代表能保证收敛。以式$\eqref{leq:avg-gen}$为例，如果将$R,\Vert\boldsymbol{g}_t\Vert_{\boldsymbol{H}_t^{-1}}^2$都视为与$t$和$T$无关的常数，那么右端的最小值在$\eta_t$为常数时取到，此时$\eta_{1:T}$随$T$线性增长，若$\Lambda_T$也随$T$线性甚至超线性增长，那么右端在$T\to \infty$时便无法趋于零，即无法保证收敛。
从这个论证过程可以看出，其实这跟$\boldsymbol{H}_t$的单调与否并无直接关系，只要$\Lambda_T$关于$T$的增长速度大于等于线性，那么便可能出现无法收敛的现象。对于AdaGrad来说，可以证明在梯度有界的假设下有$\Lambda_T \leq \tr(\boldsymbol{H}_T) \sim \sqrt{T}$，即$\Lambda_T$至多以$\mathcal{O}(\sqrt{T})$速度增长，低于线性，所以收敛性得以保证。
但像RMSProp、Adam等优化器的滑动平均式预条件子，虽然$\boldsymbol{H}_t$本身更为平稳，但$\boldsymbol{H}_t-\boldsymbol{H}_{t-1}$的特征值可能反复交替变号，而$\Lambda_T$累计的是每一步变化的$[\lambda_{\max}]_+$，极端情况下，变化中有持续的、稳定的正方向，那它就会匀速增长，从而呈现线性的$\Lambda_T$，导致收敛失败。
不过，反过来想，这某种程度上也论证了RMSProp、Adam等实践有效的原理，因为一般$\Lambda_T$的增长速度没那么糟糕，反而可能因为$\boldsymbol{H}_t$的平稳性，使得它们的$\Lambda_T$增长比AdaGrad还要平缓，从而实践效果更佳。还有最重要的一点，我们现在只是讨论损失上界的收敛性，上界不收敛原则上无法断言损失不收敛。
文章小结 #
本文在上一篇的收敛框架之上拆掉了两个“脚手架”：一是允许学习率$\eta_t$动态变化，推导出相应的平均收敛和终点收敛结论，初步解释LR Decay对优化器的通用性；二是对于非单调的$\boldsymbol{H}_t$，讨论了最小改动思想下的修正方案，以及推导了无需单调性假设的更一般的收敛结论。
总体来说，本文的信息密度较大，我们跳过了不少证明细节，因为关键的证明技巧在前面关于SGD的系列文章中已经详细给出，所以本文更多是直接给出关键的步骤与结果。
转载到请包括本文地址：https://kexue.fm/archives/11885
更详细的转载事宜请参考：《科学空间FAQ》