优化器十：RMSProp与AdaDelta

前言

  本文我们介绍RMSProp与AdaDelta算法。

RMSProp

  在之前的文章中

$$ \theta^{(\tau+1)}_i=\theta^{(\tau)}_i-\frac{\eta}{\sqrt{\sum\limits_{k=1}^{\tau}\beta^{\tau-k}\left(g^{(k)}_i \right)^2+\varepsilon}}\cdot g^{(\tau)}_i\tag{1} $$

其中$\beta\in(0,1)$。参考HB优化器，我们可以得到一种multi-stage形式的类似算法：

$$ \begin{align} \boldsymbol{v}^{(\tau)}&=\beta\boldsymbol{v}^{(\tau-1)}+(1-\beta)\boldsymbol{g}^{(\tau)}\odot\boldsymbol{g}^{(\tau)}\\ \boldsymbol{\theta}^{(\tau+1)}&=\boldsymbol{\theta}^{(\tau)}-\frac{\eta}{\sqrt{\boldsymbol{v}^{(\tau)}}+\varepsilon}\odot\boldsymbol{g}^{(\tau)} \end{align}\tag{2} $$

这便是Hinton提出的RMSProp算法。看上去似乎只是添加了一个指数衰减项，而事实上其理论分析变得非常困难，参考资料2给出了非凸情况下的收敛速度：

定理1

  设有$\mathcal L\in\mathcal C_{L}^{1,1}$，$\mathbb{E}[\|\boldsymbol{g}_{\tau}\|^2]\leq G^2$，$\beta^{(\tau)}=1-\beta^{(0)}/\tau$，$\eta^{(\tau)}=\eta/\sqrt{\tau}$，则：

$$ \mathbb{E}[\|\nabla \mathcal L(\boldsymbol{\theta}^{(\tau)}) \|^2]\leq O(\frac{\log \tau}{\sqrt{\tau}})\tag{3} $$

如果觉得资料2写的不是特别清楚的话，可以参考更加详细的资料3。很遗憾RMSProp依然没有取得理论上更快的收敛速度。

RMSProp的PyTorch实现

  与AdaGrad一样，PyTorch也内置了RMSProp算法的实现。除了标准版的RMSProp外还内置了一个centered版本的RMSProp，这是在2013年一篇用LSTM做生成任务的论文中提出的RMSProp变种：

$$ \begin{align} \boldsymbol{v}^{(\tau)}&=\beta\boldsymbol{v}^{(\tau-1)}+(1-\beta)\boldsymbol{g}^{(\tau)}\odot\boldsymbol{g}^{(\tau)}\\ \boldsymbol{m}^{(\tau)}&=\beta\boldsymbol{m}^{(\tau-1)}+(1-\beta)\boldsymbol{g}^{(\tau)} \\ \boldsymbol{\theta}^{(\tau+1)}&=\boldsymbol{\theta}^{(\tau)}-\frac{\eta}{\sqrt{\boldsymbol{v}^{(\tau)}-\boldsymbol{m}^{(\tau)}\odot\boldsymbol{m}^{(\tau)}}+\varepsilon}\odot\boldsymbol{g}^{(\tau)} \end{align}\tag{4} $$

至于这种centered版本与原始版本的性能差异这里就不展开了，感兴趣的读者可以自行进行理论分析。

AdaDelta

  我们知道RMSProp是从AdaGrad学习率衰减过快的角度出发，引入了历史梯度衰减因子。而Zeiler同样得出了这一点，但是却是独立发现的，并未参考RMSProp。我们引入记号，记：

$$ RMS[\boldsymbol{g}]=\sqrt{\boldsymbol{v}+\varepsilon}\tag{5} $$

其中$\boldsymbol{v}$是（2）式中的$\boldsymbol{v}$，$RMS[\boldsymbol{g}]$是历史梯度平方的指数平均的开方。Zeiler进一步认为此时的参数更新量：

$$ \Delta \boldsymbol{\theta}^{(\tau)} =-\frac{\eta}{RMS[\boldsymbol{g}]}\odot\boldsymbol{g}^{(\tau)} $$

中分子分母的单位不一致，将分子换成$RMS[\boldsymbol{\theta}]$则我们得到了AdaDelta算法：

$$ \begin{align} \boldsymbol{v}^{(\tau)}&=\beta\boldsymbol{v}^{(\tau-1)}+(1-\beta)\boldsymbol{g}^{(\tau)}\odot\boldsymbol{g}^{(\tau)}\\ \boldsymbol{m}^{(\tau)}&=\beta\boldsymbol{m}^{(\tau-1)}+(1-\beta)\boldsymbol{\theta}^{(\tau-1)}\odot\boldsymbol{\theta}^{(\tau-1)} \\ \boldsymbol{\theta}^{(\tau+1)}&=\boldsymbol{\theta}^{(\tau)}-{\color{Red}\eta}\cdot\frac{\sqrt{\boldsymbol{m}^{(\tau)}+\varepsilon}}{\sqrt{\boldsymbol{v}^{(\tau)}+\varepsilon}}\odot\boldsymbol{g}^{(\tau)} \end{align}\tag{2} $$

  在AdaDelta的原论文中并没有$\eta$，而在工程实践中为了获得更好的性能会加上这一项。由于在分子上加上了$RMS[\boldsymbol{\theta}]$导致理论分析变得极为困难，到目前为止还没有关于AdaDelta理论收敛速度的证明。

实验

  那么本文介绍的三个算法：RMSProp、centered RMSProp与AdaDelta与AdaGrad相比效果如何呢？它们之间相比又如何呢？参见：

References

1. https://www.cs.toronto.edu/~tijmen/csc321/slides/lecture_slides_lec6.pdf
2. A Sufficient Condition for Convergences of Adam and RMSProp，Fangyu Zou，Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition（CVPR），2019
3. 非凸随机设定下两类 RMSProp 算法的收敛性，叶美彤，东北师范大学硕士学位论文，2021
4. Generating sequences with recurrent neural networks，Alex Graves，arXiv preprint arXiv:1308.0850，2013
5. ADADELTA: An Adaptive Learning Rate Method，Matthew D. Zeiler，arXiv preprint arXiv:1212.5701，2012