USC提出拟牛顿法深度学习优化器Apollo，效果比肩SGD和Adam

©作者 | 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 对于这个问题的解决方案很简单直接，用的修正绝对值（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.

更多阅读