针对梯度下降算法提出了一种新型的适用于高维情况下学习率设置方法，称之为ADADELTA。这种方法仅仅使用一阶导数信息，具有良好的动态适应性，并且与原始随机梯度下降算法相比具有更小的计算开销。这种方法不需要人工调节学习率而且对噪声梯度信息、不同模型结构、不同的数据模式以及超参数（某个参数是随机变量时，该参数的分布中的参数就是超参数，即参数的参数）的选择表现出较强的鲁棒性。作者在同一台电脑上进行MNIST数字识别以及在分布式环境中对一个大规模的声音数据库进行语音识别，与其他方法相比，ADADELTA的方法得到了更好的结果。（Matthew D. Zeiler，2012年，论文摘要）
1988年，[Becker&LeCun]提出一种用矩阵对角线元素来近似逆矩阵的方法：
diag函数指的是构造Hessian矩阵的对角矩阵，μ是常数项，防止分母为0。
2012年，[Schaul&S. Zhang&LeCun]借鉴了AdaGrad的做法，提出了更精确的近似：
E[gt−w : t]指的是从当前t开始的前w个梯度状态的期望值。
E[gt−w^2:t ]指的是从当前t开始的前w个梯度状态的平方的期望值。
同样是基于Gradient的Regularizer，不过只取最近的w个状态，这样不会让梯度被惩罚至0。
ADADELTA METHOD
1.窗口和近似概率期望
计算E[gt−w:t]，需要存储前w个状态，比较麻烦。AdaDelta使用了类似动量因子的平均方法：
当ρ=0.5时，这个式子就变成了求梯度平方和的平均数。如果再求根的话，就变成了RMS(均方根)：
其中，ϵ是防止分母为0的常数。再把这个RMS作为Gradient的Regularizer：
这样，就有了一个改进版的AdaGrad。该方法即Tieleman&Hinton的RMSProp，RMSProp和AdaDelta是同年出现的。但是RMSProp并没有正式发表，RMSProp通过引入一个衰减系数，让r每回合都衰减一定比例，类似于Momentum中的做法。
利用了二阶信息做了Gradient优化，在BatchNorm之后，对其需求不是很大。但是没有根本实现自适应的学习率，依然需要线性搜索初始学习率，然后对其逐数量级下降。另外，RMSProp的学习率数值与MomentumSGD差别甚大，需要重新线性搜索初始值。
注：ϵ的建议取值为1，出处是Inception V3，建议不要参考V3的初始学习率。
2. Hessian方法与正确的更新单元
Zeiler用了两个反复近似的式子来说明，一阶方法到底在哪里输给了二阶方法。
首先，考虑SGD和动量法，Δx可以正比到梯度g问题，再正比到一阶导数。而log一阶导又可正比于1/x。
再考虑二阶导Hessian矩阵法，Δx可以正比到Hessian逆矩阵H^−1⋅g问题，再正比到二阶导数。而log二阶导又可正比于x。
可以看到，一阶方法最终正比于1/x，即与参数逆相关：参数逐渐变大的时候，梯度反而成倍缩小。而二阶方法最终正比于x，即与参数正相关：参数逐渐变大的时候，梯度不受影响。因此，Zeiler称Hessian方法得到了Correct Units(正确的更新单元)。
这里为了对比观察，使用了[Becker&LeCun 1988]的近似方法，而是利用Newton’s method对海森逆矩阵进行逼近，逼近项就是等式最右边的部分。让求逆矩阵近似于求对角阵的倒数：
因为之前的梯度的RMS已经表示在E（10）中的分母中。值得注意的是，使用了RMS[Δx]_t−1而不是RMS[Δx]_t，因为此时Δx_t还是未知得。所以我们计算局部光滑逼近∆x_t，给出了∆x得ADADELTA方法:
AdaDelta得伪代码：
Theano实现
def AdaDelta(tparams,grads): p=0.95;e=1e-6 # init delta_x2=[theano.shared(p.get_value() * floatX(0.)) for k, p in tparams.iteritems()] g2 = [theano.shared(p.get_value() * floatX(0.)) for k, p in tparams.iteritems()] # first to update g2 update_g2=[(g2, p * g2 + (1-p) * (g ** 2)) for g2, g in zip(g2, grads)] fn_update_1=theano.function(inputs=[],updates=update_g2) #calc delta_x by RMS delta_x=[-T.sqrt(delta_x2_last + e) / T.sqrt(g2_now + e) * g for g, delta_x2_last, g2_now in zip(grads,delta_x2,g2)] # then to update delta_x2 and param update_delta_x2=[(delta_x2, p * delta_x2 + (1-p) * (delta_x ** 2)) for delta_x2, delta_x in zip(delta_x2, delta_x)] update_param=[(param, param + delta) for param, delta in zip(tparams.values(), delta_x)] fn_update_2=theano.function(inputs=[],updates=update_delta_x2+update_param) #return the update function of theano return fn_update_1, fn_update_2
论文中，给出的两个超参数的合适实验值。ρ=0.95ϵ=1e−6ρ=0.95ϵ=1e−6，Theano的实现在LSTM的教学部分，
【出处：论文ADADELTA: AN ADAPTIVE LEARNING RATE METHOD，URL：https://arxiv.org/pdf/1212.5701.pdf]
发展历史
描述
1847, Augustin-Louis Cauchy,在Méthode générale pour la résolution des systèmes d'équations simultanées. pp. 536–538中提出提出GD。
随机梯度下降（SGD）方法是1951年由Robbins和Monro提出的，至今已有60年历史。在当前的深度学习研究中，这种方法至关重要，一般被用在反向传播过程中。
SGD方法中的高方差振荡使得网络很难稳定收敛，所以有研究者提出了一种称为动量（Momentum）的技术。1986年，momentum（动量）算法在Rumelhart, Hinton和Williams关于反向传播学习的开创性论文中首次出现。
1983年，Yurii Nesterov提出Nesterov accelerated gradient算法,它是一种二阶优化算法，计算量庞大,求逆矩阵的时间复杂度近似O(n3)，计算代价太高，不适合大数据。Yurii Nesterov在1983年发表了一篇关于解决动量问题的论文，因此，我们把这种方法叫做Nestrov梯度加速法。
2011年，Duchi, J., Hazan, E.,对随机梯度算法进行修改提出提出Adagrad算法。Adagrad方法是通过参数来调整合适的学习率η，对稀疏参数进行大幅更新和对频繁参数进行小幅更新。因此，Adagrad方法非常适合处理稀疏数据。
2012年，Matthew D. Zeiler.在Google实习时提出了Adadelta算法。这是一个AdaGrad的延伸方法，它倾向于解决其学习率衰减的问题。Adadelta不是累积所有之前的平方梯度，而是将累积之前梯度的窗口限制到某个固定大小w。AdaDelta方法的另一个优点是，已经不需要设置一个默认的学习率。Matthew D. Zeiler亦是Hinton的亲传弟子之一，还是商业天才，Phd毕业之后，创办了Clarifai，估值五百万刀。Clarifai的杰出成就是赢得了ImageNet 2013冠军.
在之前的方法中计算了每个参数的对应学习率，但是为什么不计算每个参数的对应动量变化并独立存储呢？这就是Adam算法提出的改良点。2014年，Kingma, D. P., & Ba, J.提出Adam算法，可看作是目前最常用的优化算法之一。这个方法不仅存储了AdaDelta先前平方梯度的指数衰减平均值，而且保持了先前梯度M(t)的指数衰减平均值，这一点与动量类似。
2016年，Dozat, T.将momentum算法应用于Adam算法中，提出Nadam算法。Nadam对学习率有了更强的约束，同时对梯度的更新也有更直接的影响。
2018年，在Adam方法收敛到一个次优解时，观察到一些小批次样本贡献了大幅且有效的信息梯度，但是这种情况很少发生，指数平均后减小了它们的影响，导致模型收敛性差。Reddi等人提出AMSGrad算法对SGD算法进行改进.
下图是对鞍点数据进行优化得可视化显示
从上面的动画可以看出，自适应算法能很快收敛，并快速找到参数更新中正确的目标方向；而标准的SGD、NAG和动量项等方法收敛缓慢，且很难找到正确的方向。
主要事件
年份 | 事件 | 相关论文/Reference |
1951 | Robbins, H., & Monro, S.提出SGD算法 | Robbins, H., & Monro, S. (1951). A stochastic approximation method. The annals of mathematical statistics, 400-407. |
2011 | Duchi, J., Hazan, E.,对随机梯度算法进行修改提出提出Adagrad算法 | Duchi, J., Hazan, E., & Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul), 2121-2159. |
2012 | Zeiler, M. D.对Adagrad提出AdaDelta算法 | Zeiler, M. D. (2012). ADADELTA: an adaptive learning rate method. arXiv preprint arXiv:1212.5701. |
2014 | Kingma, D. P., & Ba, J.提出经典的Adam算法 | Kingma, D. P., & Ba, J. (2014). Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980. |
2016 | Ruder, S.对多种梯度下降算法进行综述回顾 | Ruder, S. (2016). An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747. |
发展分析
瓶颈
局部最小值，从多个数据集情况来看，AdaDelta在训练初期和中期，具有非常不错的加速效果。但是到训练后期，进入局部最小值区之后，AdaDelta就会反复在局部最小值附近抖动。主要体现在验证集错误率上，脱离不了局部最小值吸引盆。
未来发展方向
AdaDelta的二阶近似计算，或者说所有二阶方法，则不会产生这么大的抖动，所以很难从局部最小值中抖出来。尽管SGD速度没有AdaDelta理想，但是它却能从局部最小值中挣脱出来，这也是SGD算法能经历这么长时间磨练得原因。如何让AdaDelta挣脱出局部最小值也是一个研究得问题所在。
Contributor: Ruiying Cai