usc提出拟牛顿法深度学习优化器apollo，效果比肩sgd和adam -凯发k8官方网
©作者 | xuezhe ma
单位 | usc助理教授
研究方向 |nlp、机器学习
摘要
本文介绍了 apollo，一种针对非凸随机优化的拟牛顿方法。它通过对角矩阵逼近 hessian，动态地将损失函数的曲率应用到优化的过程中。重要的是，apollo 对于 hessian 的对角近似的时间和空间复杂度与自适应一阶优化方法一样。
为了处理目标函数的非凸性，我们用 hessian 的修正绝对值（recified absolute value）来代替原始的 hessian，保证它是正定的。机器视觉和自然语言处理三项任务上的实验表明，apollo 在收敛速度和泛化性能上都比其它随机优化方法（包括 sgd 和 adam 的变体）有了显著的改进。
论文标题：
apollo: an adaptive parameter-wise diagonal quasi-newton method for nonconvex stochastic optimization
论文链接：
https://arxiv.org/abs/2009.13586
代码链接：
https://github.com/xuezhemax/apollo
随机非凸优化和拟牛顿法
本文专注于以下形式的随机非凸优化问题：
其中 是模型的参数， 是随机噪音。拟牛顿法的参数更新公式如下：
为步长（stepsize），又叫学习率（learning rate）。 为每一次参数更新时对 hessian 矩阵的近似。矩阵 的计算满足经典的 secant equation：
其中 。以上公式中不同矩阵模（norm）的选择对应不同的经典算法，例如 l-bfgs [1] 和 dfp [2]。
总结来说，拟牛顿法在深度学习优化问题中存在三个常见问题：
time and memory efficiency（时空复杂度）. 在深度学习的优化问题中，由于模型参数的维度巨大，现有的拟牛顿法无法在实际问题中应用。比如经典的 l-bfgs [1] 算法一般需要记录至少之前 5 到 10 步的迭代历史，这在深度学习问题中是不实际的。而现有的一些为随机非凸问题设计的拟牛顿法，例如 sdlbfgs [3]，甚至需要比 l-bfgs 更多的时间和空间资源。
stochastic variance. 优化过程中的随机性使得对于 hessian 的近似存在较大的方差， 导致优化算法的不稳定甚至失败。
nonconvexity（非凸性）. 目标函数的非凸性导致很难在优化过程中保证 hessian 的正定性。而目标函数的随机性又使得标准的 line search 无法有效的应用。
apollo算法
time and memory efficiency（时空复杂度）。为了降低 apollo 算法的时空复杂度，我们仿效之前的工作，用对角矩阵来近似 hessian，亦即约束每一步 为对角矩阵。为了满足这一约束，我们需要对公式（5）中的 secant equation 进行放松。一个常用的方法是 weak secant equation [4,5]：
但是对于参数为度巨大的深度神经网络来说，weak secant equation 的约束过于微弱。为了得到一个折中的办法，我们利用神经网络参数的性质，将参数分离成不同的参数模块：。例如，一个多层神经网络的参数可以分离成每一层不用功能的参数。这样对于每一个参数都会产生一个weak secant equation，增强了约束能力。
经过简单的推到， 的更新公式为：
stochastic variance. 为了降低优化过程中由于随机噪音导致的不稳定，我们除了应用 adam 中的 exponential moving average（emv）之外，还提出了一个重要的方法：stepsize bias correction。简单来说，我们希望矩阵 的更新可以不受步长的影响。具体的做法是对每一步的 gradient 进行修正： 。这样公式（7）就演变为：
其中 。对于 stepsize bias correction 的具体讨论请参考原文。实际应用中，我们发现 stepsize bias correction 对于 apollo 算法的收敛稳定性起到至关重要的作用。
nonconvexity（非凸性）. 非凸性是阻碍拟牛顿法应用到深度学习优化的最主要困难之一。如下图所示，对于一个非凸点的曲率是负的，因此直接应用拟牛顿法会导致参数更新方向错误。
apollo 对于这个问题的凯发k8官方网的解决方案很简单直接，用 的修正绝对值（rectified absolute value）来代替 。
其中 是一个超参数。现在的问题是我们是否需要增加一个需要调试的超惨 ？幸运的是，我们发现 和 是两个耦合在一起的超参数，而实际中我们可以固定一个而只调试另一个。具体请参考论文中的 theorem 1.
的取值选择。在最初的版本中，我们设定 。但是我们发现这样使得 的取值会比较大，不太符合大家对学习率（learning rate）的直观印象。因此我们在最新的版本中设定 。具体讨论参考论文。
apollo算法的收敛性
我们仿效之前的工作，对 apollo 在凸函数和非凸函数两种情况下的收敛进行了理论分析。具体请参考论文中的 theorem 2 和 theorem 3。
实验
实验部分，我们做了在三个常见的任务上面对比了 apollo 和其他优化算法的效果，包括 image classification, language modeling 以及 neural machine translation。涉及的神经网络模型包括 resnet，lstm 和 transformer。每个实验，我们都用 5 个不同的 random seed，并报告实验结果的平均值。具体的实验配置，请阅读论文。
image classification
language modeling
neural machine translation (wmt-14 english-german)
结语
这篇文章从去年 9 月开始已经在一年内被多次拒稿，实在让我感慨优化领域的水之深。扪心自问，这篇论文我们算是尽心尽力做到能做的最好，也自认无论从算法还是实验结果都有创新的地方。
据我们的有限所知，apollo 是目前第一个能在实际中应用的深度神经网络的优化算法，并能在多个任务和网络结构上取得比肩甚至超过 sgd 和 adam 的效果。然而，仍有审稿人因为各种原因拒稿。其中最多的拒稿原因是 apollo 中提出的一些方法，例如 stepsize bias correction 和 rectified absolute value 没有明确的理论证明。
说一句有些偏激的话，现在深度学习中有哪个实际中有效的方法有严格的理论证明？甚至有一个审稿人的一条意见是，我们的收敛证明是基于 adam，而在他/她看来，adam 的理论证明是达不到发表的标准的。我想说的是，在当下论文井喷的时代，做自己心中觉得真正有用的研究才是一个研究员最该坚持的事。
参考文献
[1] charles george broyden. the convergence of a class of double-rank minimization algorithms. ima journal of applied mathematics, 6(1):76–90, 1970.
[2] william c davidon. variable metric method for minimization. siam journal on optimization, 1(1):1–17, 1991.
[3] xiao wang, shiqian ma, donald goldfarb, and wei liu. stochastic quasi-newton methods for nonconvex stochastic optimization. siam journal on optimization, 27(2):927–956, 2017.
[4] john e dennis, jr and henry wolkowicz. sizing and least-change secant methods. siam journal on numerical analysis, 30(5):1291–1314, 1993.
[5] jl nazareth. if quasi-newton then why not quasi-cauchy. siag/opt views-and-news, 6: 11–14, 1995.
[6] sashank j reddi, satyen kale, and sanjiv kumar. on the convergence of adam and beyond. in international conference on learning representations, 2018.
[7] x chen, m hong, s liu, and r sun. on the convergence of a class of adam-type algorithms for non-convex optimization. in 7th international conference on learning representations, iclr 2019, 2019.
更多阅读
#投 稿 通 道#
让你的文字被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。paperweekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
paperweekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。
???? 稿件基本要求：
• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注
• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无凯发k8官方网的版权问题
• paperweekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算
???? 投稿通道：
• 投稿邮箱：hr@paperweekly.site
• 来稿请备注即时凯发k8官方网的联系方式（微信），以便我们在稿件选用的第一时间联系作者
• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿
△长按添加paperweekly小编
????
现在，在「知乎」也能找到我们了
进入知乎凯发k8官方网首页搜索「paperweekly」
点击「关注」订阅我们的专栏吧
·
总结
以上是凯发k8官方网为你收集整理的usc提出拟牛顿法深度学习优化器apollo，效果比肩sgd和adam的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇：
- 下一篇：