深度学习有一个melody：model, evaluation, loss, optimization, and dataset. 它们相互交织，每个部分都对最终的performance有一定影响。所以其实脱离了melody单独谈optimization是耍流氓行为。实际应用中肯定是要结合具体的task(dataset)和model architecture等来选择优化演算法的。但优化演算法要不要单独研究呢？我觉得还是有一定必要的。一方面是速度上，好的优化演算法是真的快（比如FISTA，或是各种分散式的演算法）；另一方面，人们也的确想来理解不同的演算法区别到底在哪里，以及怎么来选择。

本文是基于一些实践以及相关的论文而谈的。很多见解也被放在了我们的一篇论文里：

Nostalgic Adam: Weighting more of the past gradients when designing adaptive learning rate 。 欢迎大家阅读、批评、引用！

引言 深度学习优化演算法总览

深度学习中的优化演算法常用的主要有两种，基于梯度的和不基于梯度的。我个人觉得不基于梯度的演算法现在还不是很成熟。基于梯度的肯定都是一阶梯度，因为二阶梯度的话是存不下那么大的Hessian矩阵的。一阶梯度演算法可以被概括为如下表达式： x_{t+1} = x_t - frac{alpha_t}{psi(g_1, ..., g_t)}phi(g_1, ..., g_t), 其中 phi(g_1, ..., g_t) 可以看作对gradient的一个估计。最为简单的形式就是SGD: x_{t+1} = x_t - alpha_t g_t, 以及目前可能是最常用的momentum形式： x_{t+1} = x_t - alpha_t m_t, m_t = eta_1 m_{t-1} + (1-eta_1)g_t. 这类演算法其实已经讨论的非常多了，乃至对应的dynamics都已经分析清楚了，见下面这篇Weijie Su的经典论文：

A Differential Equation for Modeling Nesterovs Accelerated Gradient Method: Theory and Insights?

arxiv.org

Nesterov, momentum，加上SGD，这可以算作一类演算法。

另一类演算法是所谓的adaptive演算法， 最早是2012年AdaGrad被提出，后来Adam的「又快又好」让这类演算法大行其道。不过近年来又因其在一些task上的generalization performance不如SGD类演算法而被诟病。在上面的框架下，Adam的演算法可以被写作 x_{t+1} = x_t - frac{alpha_t}{v_t^{1/2}} m_t, \ m_t = eta_1 m_{t-1} + (1-eta_1)g_t, \ v_t = eta_2 v_{t-1} + (1-eta_2)g_t^2.

同时，因为Adam类演算法构造的有一些「违反直觉」，很多人都不是特别理解这个演算法的本质（实际上是不理解 v_t 的含义）。这类演算法的理论研究比较少。我之后主要谈的是这类演算法。

近年来关于Adam类演算法的研究

  1. Non-convergence Issue. 这方面最重要的工作就是18年ICLR的best paper: On the Convergence of Adam and Beyond. 他们对Adam的证明进行了分析，发现了两个bugs，其中比较致命的bug是 v_t 的估计，Adam的 v_t 会导致这一项不恒正： Gamma_t = frac{sqrt{V_{t+1}}}{alpha_{t+1}} - frac{sqrt{V_t}}{alpha_t} ，他们还找出了一个例子让Adam不收敛。解决方案是用 hat{v}_t = max(v_t, hat{v}_{t-1}) 来在 x_t 的更新式中代替 v_t ，这个演算法叫做AMSGrad。作者认为这样可以让演算法拥有"long-term" memory。（我后面会说实际上并没有）

这篇文章是很有启发性的，之后有好多篇文章是基于这篇文章又给出了一些改进的Adam variants. 比如有一篇叫AdaShift，作者从AMSGrad一文中的那个反例出发进行分析，获得了一个新演算法。但实际上这个反例是非常artificial的，最不自然的就是repetitive gradients，即梯度是周期性反复出现的，这在实际情况中是不可能出现的。另一个比较有意思的工作是AdaBound，我之前已经有过一些讨论了：

如何评价优化演算法 AdaBound??

www.zhihu.com图标

这些文章有一个共同点是都觉得不能像Adam一样完全地「信任」当下的gradient。我们的论文要更进一步：我们要求在设计 v_t 时，要对过去的gradient给予更大的权重。演算法的motivation也是从证明里来的，这个我放到后面说。

2. Generalization

之前在各种优化演算法爆炸性增长的时候（14年左右）大家还没来得及关心泛化，都关心演算法快慢，调参难易等等。但现在越来越多的人注意到泛化才是最重要的。而17年的时候，终于有人写了篇论文来怼Adam类演算法的泛化问题，标题也起的很悲观：

The Marginal Value of Adaptive Gradient Methods in Machine Learning?

arxiv.org

粗暴地总结就是论文对一些常见的task做了实验，得出了adaptive演算法的泛化很烂的结论。但事实是否的确如此呢？我觉得并不是。从实践看，像Google最新的BERT就是用AdamW优化的；从理论看，我觉得有一篇文章很能说明问题：

Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients?

proceedings.mlr.press

这篇文章发表在2018年的ICML。文章有两个亮点很吸引我，第一就是讨论了SGD类演算法和Adam类演算法分别在什么时候work；另一个是基于second-moment的假设，对 v_t 的作用进行了一个分析。细节可能需要大家自己去读文章，我这里就谈第一个点。

上图中比较了SGD和SSD(即Adam类）演算法在一个二次问题中，不同noise, 不同条件数以及二次矩阵是否为对角矩阵(rotated or axis-aligned) 情况下的performance。文章中还对这个model problem做了比较充分的理论分析。一些简单的结论有：

a. 梯度的noise大时，Adam类比SGD类好；

b. loss看作二次函数时，二次矩阵的数值越大，SGD越好（文中的量 p_{diag}(Q) := frac{sum|q_{i,i}|}{sum|q_{i,j}|} ).

c. 问题的条件数越大，SGD越不好。

这些结论，配合实验（论文里还做了很多实验）都说明了其实SGD类演算法和Adam类演算法的performance是相当problem-dependent的。这也可能可以解释为什么某些问题上SGD(momentum)的确比Adam好一大截。

在实际做选择的时候，不可能真的去算条件数或是noise，更可行的是把两类演算法都试试，一类不行就试另一类。

3. v_t 的作用

刚才已经说了，Dissecting Adam里面对 v_t 的作用有过讨论，但是是基于 v_t 是 mathbb{E}[g_t^2] 的approximation这一假设的。这个假设对不对呢？很难说。有一篇叫PAdam的工作，把Adam中的 v_t^{1/2} 替换成了 v_t^p, ;0<P> ，发现不仅理论上依然收敛，实验结果也非常说的过去。然后在我们论文的supplement里面，我们证明了一个. 这些可能都说明了把 v_t 解释成second-moment estimate是不太科学的。

不过 v_t 是怎么其作用的还真不好说。我个人目前的理解与AdaGrad中的一个比较直觉的解释类似，直接搬运过来吧：

「the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features.」

大意就是 v_t 实际上是在根据不同feature的出现频率在balance它们的更新速度：经常出现的feature v_t 就会大一些，那么一倒数就会让对应的 x_t 更新慢一点。这一理解可以帮助我们理解一个叫SWATS的工作(Improving Generalization Performance by Switching from Adam to SGD)。这个工作的大意是先用Adam，找到一个合适的 v_t 之后就固定下来，转成SGD。这似乎告诉我们在每个coordinate上存在著一个optimal rescaling factor v_{t,k} ，我们的目的就是把它们找到，来平衡不同coordinate的更新速度。

这个理解是相当直观的，但「很有可能」有点道理。像目前算是站得住脚的AMSGrad, AdaBound和NosAdam（勉强算吧），都符合这个特点，即rescaling factor在逐渐的固定下来。这是一个很有意思的问题，也许会再出几篇不错的paper。

我们的演算法Nostalgic Adam

说了这么多别人家的演算法，我也要谈一谈我们的演算法究竟是什么，可以为我们提供什么insight。我们的第一个想法是让 Adam中的 eta_2 变起来，与 t 相关，即 eta_{2,t} . 再把它表示成两项之商 eta_{2,t} = frac{B_{t-1}}{B_t} ，由此任意一个递增正数列 {B_t} 都可以定义出一系列的 eta_{2,t} in [0,1) ，如果再定义 b_t := B_t - B_{t-1} ，则 {b_t} 是任意一个正数列。那么之前所说的收敛证明中要求的 Gamma_t = frac{sqrt{V_{t+1}}}{alpha_{t+1}} - frac{sqrt{V_t}}{alpha_t} 要正定的条件意味著什么呢？

Lemma3.1: The positive semi-definiteness of Gamma_t = frac{sqrt{V_{t+1}}}{alpha_{t+1}} - frac{sqrt{V_t}}{alpha_t} is satisfied if and only if frac{B_t}{t} is non-increasing.

而如果 {b_t} 是个单调序列（在Adam中它单调增），我们又可以证明 frac{B_t}{t} is non-increasing if and only if b_t is non-increasing. 这是与Adam挺重要的一个区别。注意到 v_t = sum_{k=1}^t g_k^2 frac{b_k}{B_t} , 我们可以看到 b_t 序列的不增就意味著，在 v_t 的计算中，我们要对过去的 g_k^2 给予更多的权重。

演算法的核心就这么简单，写成伪代码就是：

除了 frac{B_t}{t} 序列不增，我们还需要另一个收敛性条件，但这两个收敛性条件都是很容易check的，而且可以在设计 b_k, B_t 的时候都完成，完全是data-independent。下面是收敛性的定理。

其实我们还证明过一个非凸情况下的收敛性，不过完全是follow相关文章的证明，新意不大（见On the Convergence of A Class of Adam-Type Algorithms）。

特别的呢，我们找出了满足上述收敛条件的一组参数，它们是hyperharmonic series，因此这个特殊情形也叫NosAdam-HH，即 b_k = k^{-gamma}, B_t = sum_{k=1}^t k^{-gamma} 。之后做的实验都是用的这个具体的演算法。NosAdam其实只是一个框架。

为什么会出现Nostalgic这种现象？

我觉得一个有意思的发现是不够的，我们肯定是要努力去解释解释（虽然可能是强行解释）。我们先来把几个演算法的 v_t 写出来。

v_t^{(Adam)} = sum_{k=1}^t (1-eta_2)eta_2^{t-k}g_k^2, ;;;;v_t^{(NosAdam)} = sum_{k=1}^t g_k^2 frac{b_k}{B_t} ,

AMSGrad不太好直接写，但可以写作 v_t^{(NosAdam)} = v_{t-n}^{(Adam)} ，这里n是depends on data的，即取的是 {v_k}_{k=1}^t 中最大的 v_k . AdaShift也可以用上式表示，不过n是个常数。

这样一来，我们就可以作图了：

weight comparison among Adam, NosAdam, AMSGrad/AdaShift

从这个比较首先可以看出Adam的一个缺陷，就是 v_t 过分以来最近的gradient，这样以来万一gradient一直很小， v_t 就会特别小，那么步长就会很大，就不稳定了（乃至发散）。

AMSGrad一文中的例子太artificial了，我这里给一个新的例子（参考了老板的老板的文章LSGD），同时提供一种从landscape来思考演算法的视角，个人觉得还是比较有意思而且promising的：

我这里就只放图不多解释了，简单说就是在这个底部比较平坦的情况下，Adam会不收敛，但是NosAdam完全OK。

那AMSGrad又有什么问题呢？它的确客服了发散，但它最大的问题是 hat{v}_t 容易被极端值影响，而且一旦变大就没法变小了，下面是一个例子：

一个更真实的例子是在sharp local minimum处，由于梯度比较大，可能会造成AMSGrad中的 hat{v}_t 过大，而且无法变小，因此被trap住：

但每种方法都有其优劣。NosAdam的坏处是对初始条件依赖比较大——它需要有一个「美好的童年」，否则是没必要nostalgic的。我也构造了一个NosAdam不如Adam的例子，即initiate在local minima附近：

这一系列例子都很清楚地展现出了Adam类演算法在不同landscape下的表现，尤其是对initial condition的sensitivity。至于实际的initial condition究竟如何呢？有一些相关的工作发现，有skip connections的architecture（即ResNet类网路）配合上Kaimings initialization能有相当好的loss landscape，放两张图:

摘自论文&amp;amp;quot;Visualizing the Loss Landscape of Neural Nets&amp;amp;quot;
ResNet56 on CIFAR10，我自己画的

个人觉得这个角度（loss landscape）对优化演算法的思考是有益的，它可以帮我们（部分地）理解很多优化演算法为什么work，为什么不work，以及什么时候work或不work。比如从上图的ResNet56 on CIFAR10的 loss landscape可以看出，NosAdam应该是会work的（跟我们的例子中的landscape基本一样）。

一些实验结果

首先我得承认我是手残，实验做的很渣，没有在ImageNet很好地跑过（试过，太耗时间就没再试了……），对于下面的实验，代码可见github.com/andrehuang/N。

结语

虽然夹带著私货，写本文的初衷其实还是想把深度学习中的一阶优化演算法有一个比较清楚的讨论，这也是我过去这一年来断断续续折腾和思考的结果。我觉得上面的讨论还是能够让我们对一阶优化演算法有一个比较清晰的认识的。

至于take-home message，

to practioner：如果Adam类演算法不行，就上momentum；如果momentum不行，就上Adam类（AdamW, AMSGrad...)，特别地，别忘了NosAdam。

to theory-lover: 文章里有好多坑可以做呀！ v_t 的作用？怎样从landscape的角度进一步把问题分析清楚（more sensitivity analysis?) ？以及那个关于 v_t 的猜想是否是对的——数据分布均匀与否是否会影响两类演算法的表现？（这个肯定是可以上手做的）

希望对大家能有一些帮助吧！


推荐阅读：
相关文章