AdaBound详解[首发]
AdaBound：ADAPTIVE GRADIENT METHODS WITH DYNAMIC BOUND OF LEARNING RATE [github][discussion] (ICLR2019)
（消息来源量子位-中国学霸本科生提出AI新算法：速度比肩Adam，性能媲美SGD，ICLR领域主席赞不绝口）
在本篇论文中，作者公布了一个名为AdaBound的神经网络优化算法，简单地说，这个算法训练速度比肩Adam，性能媲美SGD。
这个算法适用于CV、NLP领域，可以用来开发解决各种流行任务的深度学习模型。而且AdaBound对超参数不是很敏感，省去了大量调参的时间。
一、Abstract摘要 & Introduction介绍
自适应方法Adaptive optimization methods诸如AdaGrad，RMSProp和ADAM已经被应用在许多更新学习速度的训练中。但是这些方法也被认为存在许多缺点：SGD：因为它的不稳定性和学习速度容易走入一个极端值（局部最优），所以难以收敛；
Adam：和自适应优化方法AdaGrad、RMSProp等一样，通过让小球在更陡峭的山坡上下降，速率加快，来更快地让结果收敛。虽然Adam算法跑得比SGD更快，却存在两大缺陷：结果可能不收敛、可能找不到全局最优解。也就是说它的泛化能力较差，在解决某些问题上，表现还不如SGD。
而造成这两大缺陷的原因，可能是由于不稳定和极端的学习率。AdaBound是如何解决这个问题的？
作者提供了ADAM和AMSGRAD的新变种，叫做ADA BOUND和AMS BOUND分别采用动态的学习速率边界，来实现从自适应方法到SGD的渐进平稳过渡，并给出了收敛性的理论证明。
作者进一步对各种流行的任务和模型进行实验，这在以往的工作中往往是不够的。实验结果表明，新的变种可以消除自适应方法与SGD的泛化差距，同时在训练早期保持较高的学习速度，并且也保证了在测试数据上的强泛化能力。此外，它们可以对原型带来显著的改进，特别是在复杂的深度网络上。该算法的实现参考作者本人提供的github/Luolc/AdaBound。
二、NOTATIONS AND PRELIMINARIES 符号&前言
Notations
1. 给定一个向量 ，我们使用
表示它的第
-th坐标；
在 -norm 中我们使用
表示
和
的 element-wise；
在 -th 次迭代中的向量
来说，对
的第
-th 个坐标加入一个角标
表示为
。
2. 给定两个向量 ，我们用
表示它们的内积，
表示element-wise product，
表示element-wise division，
表示element-wise maximum 和
来表示element-wise minimum。
3. 我们用 表示所有正定的
矩阵的集合。
4. 对于向量 和正定矩阵
，我们用
表示
，用
来表示
。
5. 对 时投影操作
定义为
，
6. 我们说当 时候对所有
，
边界直径
latex参考：LaTex中插入花体字母 LaTeX 括号总结 LaTeX 中的特殊符号 ****latex建议配置：Latin modern + compressed
Online convex programming
1. 一个灵活框架来分析迭代优化方法就是在线优化问题online optimization problem。它可以被描述为玩家(算法)和对手之间的重复博弈。在步骤 中，算法选择一个决策
，其中
为凸可行集，然后对手选择一个凸损失函数
，算法产生损失
。总损失
与一个固定决策的最小值之间的差异称为
，它由
表示。
2. 在本文中，我们假设可行集 具有有界的直径，并且对于所有
和
都有界
。我们对算法很感兴趣。正式地说，我们的目标是设计一种确保
的算法，这意味着模型的性能平均收敛到最优。具有消失平均
的在线优化算法会产生相应的随机优化算法(Cesa-Bianchi et al., 2002)。因此，在Reddi et al.(2018)之后，我们将在线梯度下降online GD和随机梯度下降SGD作为同义词。
A generic overview of optimization methods
我们遵循Reddi et al.(2018)在算法1中提供了一个通用的优化方法框架，它封装了许多流行的自适应和非自适应方法。这对于理解不同优化方法的属性非常有用。注意,该算法当函数 和
没有特定指明时仍然是抽象的。
在本文中,我们将 称为初始步长，
为算法的学习率。注意看，我们使用的设计由
减少步长也能使用收敛理论证明。然而如此激进的步长通衰减常被解释为经验表现的不佳，而一个简单的固定步长
在实践中通常工作得很好。为了清晰起见，在本文的其余部分中，我们将使用递减格式进行理论分析，使用常数格式进行实证研究。
在这样的框架下，我们可以总结表1中常用的优化方法。我们可以看到 中的缩放项
是
(\romannumeral2)，而自适应方法引入了对过去梯度的平方值进行不同类型的平均。
和
可以看作是
的变体，前者使用指数移动平均作为函数
，而不是
中使用的简单平均。特别是
本质上是
中
时一个特例。
并不像它不列入表有一个简单的表达
。它可以被定义为
，当
通过以下递归：
和
，并且
。
的定义与
相同。由于
的通用性，在本文的其余部分我们将主要关注
，但我们的论点也适用于其他类似的自适应方法，如
和
。
三、THE NON-CONVERGENCE CAUSED BY EXTREME LEARNING RATE
在这一节中，我们通过初步的实验和严格的证明，阐述了当前自适应方法的主要缺陷。如上所述，像ADAM这样的自适应方法被观察到比SGD表现更差。Reddi et al.(2018)提出AMSGRAD来解决这个问题，但是最近的研究指出AMSGRAD并没有比ADAM (Keskar&Socher, 2017;Chen et al., 2018)。由于AMSGRAD的学习率比ADAM要低，所以作者只将学习率高视为ADAM表现不佳的原因。然而，小的可能也是一个陷阱。因此，我们推测ADAM的极大和极小的学习率都可能解释其普通的泛化能力。
为了证实我们的推测，我们使用ADAM对ResNet- 34在CIFAR-10上的几个权重和偏差的学习率进行了抽样。具体来说，我们从不同的层中随机选取9个3x3卷积核，最后一个线性层的偏差。由于同一层的参数通常具有相似的性质，这里我们只展示了在训练结束时，从9个核中分别采样9个权值和最后一层的一个偏置的学习率，并使用热图将其可视化。如图1所示，我们可以发现当模型接近收敛时，学习率由小于0.01的小学习率和大于1000的大学习率组成。
以上分析和观察表明，在训练过程的最后阶段，确实存在学习速率过大或过小的情况。AMSGRAD可能有助于减轻高学习率的影响，但它忽略了事情的另一面。到目前为止，我们仍然有以下两个疑问：
- 第一，微小的学习速率真的会对亚当的收敛造成伤害吗？
- 第二，学习速率的高度取决于初始步长,我们可以使用一个相对较大的初始步长
摆脱学习率太小？
为了回答这些问题，我们为ADAM和RMSPROP显示不佳的收敛行为可以引起的极其微小的学习速率，而且，在某些情况下,无论多么大的初始步长 ,ADAM仍未能找到合适的路径和收敛于一些高次优点。考虑下面的线性函数序列
对于这个函数序列，很容易看到任何满足x<0的点提供了最小遗憾。假设，我们表明,ADAM收敛于一个高度理想的解决方案当
。直觉上，推理如下。该算法每C步得到一个梯度-1，使算法向错误的方向移动。然后，在下一步，它观察梯度2。但是较大的梯度2无法抵消错误方向的影响，因为这一步的学习率被缩小到一个比前一步小得多的值，因此随着时间的增加，x变得越来越大。我们在下面的结果中形式化这个直觉。
我们把所有的证据归入附录。请注意,上面的例子也适用于固定步长。还要注意vanilla SGD没有这个问题。有一个广泛的有效的初始步长选择
的平均后悔SGD渐近趋于0，换句话说，收敛于最优解。在实际训练过程的后期，当算法陷入一些次优点时，这个问题会更加明显。在这种情况下，大多数阶跃的梯度都接近于0，由于指数移动平均的性质，二阶动量的平均值可能变化很大。因此,正确的信号出现的频率相对较低(即梯度2每个C步骤在上面的例子中)可能无法使该算法正确的道路,如果他们在一些错误的信号(即梯度1的示例)，即使正确的大梯度的绝对值。
你可能想知道使用大的有助于我们在实践中通常使用
接近1。然而,下面的结果表明,对于任何常数
和
满足
，存在一个例子中当ADAM平均的后悔渐近零而无论初始步长
为多大。
此外，在更简单的随机优化设置中，得到了更强的结果：
如前所述Reddi et al,.(2018),条件是良性的,通常是满足在实践中使用的参数设置。在收敛证明中也假定了这一条件Kingma & Lei Ba(2015)。上述结果说明了极端学习率的潜在不良影响，如果不解决这个问题，算法不可能获得良好的泛化能力。
四、ADAPTIVE MOMENT ESTIMATION WITH DYNAMIC BOUND
在本节中，我们将开发新的优化方法变体，并提供它们的收敛性分析。我们的目标是设计一种策略，结合自适应方法的优点，即快速的初始进展，以及SGD良好的最终泛化特性。直观地说，我们希望构建一种算法，其行为类似于训练早期的自适应方法，而类似于训练结束时的SGD。
受梯度裁剪gradient clipping的启发，我们在ADAM中使用了基于学习速率的裁剪，提出了算法2中的adrich。考虑在ADAM中应用以下操作:
剪辑学习速率element-wisely输出限制在。SGD(M)和
可以视为情况
。对于ADAM来说，
和
。现在我们可以通过以下步骤提供新的策略。我们使用
和
作为
的函数，而不是不断的降低和上界，
是一个非衰减函数，从 t = 0时，渐近收敛到
。在这种设置下，ADABOUND的行为就像ADAM一开始的行为一样，边界对学习率的影响很小，随着边界越来越受限，逐渐转化为SGD(M)。我们为ADABOUND证明了以下关键结果。
下列结果是上述结果的直接推论
不难看出，ADABOUND的遗憾是以为上界的。类似于Reddi et al。(2018),可以使用一个更温和的动量衰减
和仍然确保
的遗憾。应该指出的是，在AMSGRAD中也可以合并动态边界。得到的算法AMSBOUND也有
的遗憾，收敛性证明与定理4几乎相同(详见附录F)。在下一节中，我们将看到AMSBOUND具有类似于在几个著名任务中丰富的性能。
我们在这一节结束时将与以前的工作进行比较。关于将ADAM转化为SGD的想法，Keskar &也做过类似的工作。Socher(2017)。作者提出了一种首先使用ADAM并在特定步骤将算法切换到SGD的方法。与他们的方法相比，我们的方法有两个优点。
- 首先，是否存在一个固定的转折点来区分ADAM和SGD是不确定的。所以我们用一个连续的转换过程来解决这个问题，而不是”僵硬“的替换。
- 其次，他们引入了一个额外的超参数来决定切换时间，这并不容易进行微调。
对于我们的方法，引入的柔性部件是两个约束函数。我们对不同类型的约束函数的影响进行了实证研究。结果放在附录G为我们发现收敛目标和收敛速度对最终结果不是很重要。为了清晰起见,我们将使用
在剩下的纸，除非另有说明。
五、EXPERIMENTS
在这一节中，我们将对不同的模型进行实证研究，将新变量与常用的优化方法(包括SGD(M)、ADAGRAD、ADAM和AMSGRAD))进行比较。我们关注三个任务:MNIST图像分类任务(Lecun et al.， 1998)， CIFAR-10图像分类任务(Krizhevsky)以及Penn Treebank上的语言建模任务(Marcus et al.， 1993)。我们之所以选择它们，是因为它们的架构具有广泛的重要性和可再现性。表2详细列出了每个任务的设置。我们使用指定的初始化方法从随机的起点运行每个实验三次。为训练指定了固定的时域数预算，下面将介绍衰减策略。我们选择的设置，实现最低的培训损失在最后。
1. HYPERPARAMETER TUNING
优化超参数会对优化算法找到的最终解产生很大的影响，所以我们在这里描述如何优化它们。为了调整步长，我们采用Wilson等人(2017)的方法。我们实现了一个五步长的对数间隔网格。如果最佳性能参数位于网格的极端之一，我们将尝试使用新的网格点，以便最佳性能参数位于网格的中间点之一。具体来说，我们通过以下方式对超参数进行调优：
SGD(M)
为了优化SGD(M)的步长，我们首先在对数尺度上从f100粗调步长，然后微调。是否使用动量取决于具体的模型，但我们将动量参数设置为默认值0.9，用于我们的所有实验。我们发现这种策略是有效的，因为不同的学习模式需要不同的学习速率。例如，SGD中
对肺结核但执行最好的语言建模。在CIFAR-10上ResNet-34架构，SGD的学习率为0.1是必要的。
ADAGRAD
ADAGRAD的初始步长设置为。对于初始累加器值，我们推荐值为0。
ADAM & AMSGRAD
我们对这两种方法使用相同的超参数。最初的步长选择从。我们调节
值在
，
。使用干扰值
。
ADABOUND & AMSBOUND
我们直接应用的ADAM默认hyperparameters(0.001的学习速，)在我们提出的方法。
2. FEEDFORWARD NEURAL NETWORK
针对MNIST数据集上的多类分类问题，我们训练了一个具有隐层的简单全连通神经网络。我们运行了100个epochs，省略了这个实验的衰变方案。图2显示了训练集和测试集上每种优化方法的学习曲线。我们发现，对于训练，所有的算法都能达到接近100%的准确率。对于测试部分，SGD的性能略优于ADAM和AMSGRAD的自适应方法。我们提出的两种方法，ADABOUND ，AMSBOUND，显示出微小的改进，但与之相比他们的原型在测试精度上仍然有明显的提高。
3. CONVOLUTIONAL NEURAL NETWORK
然后利用DenseNet-121 (Huang et al.， 2017)和ResNet-34 (He et al.， 2016)对CIFAR-10标准数据集进行图像分类。在这个实验中，我们使用200个epochs的固定预算，在150个epochs后将学习率降低10。
DenseNet
我们首先在CIFAR-10上运行DenseNet-121模型，结果如图3所示。
我们可以看到，ADAGRAD、ADAM和AMSGRAD等自适应方法在早期训练中表现得比非自适应方法更好。但是到了epoch150，当学习速率衰减时，SGDM开始优于那些自适应方法。对于我们的方法，ADABOUND 和AMSBOUND，它们收敛速度和自适应方法一样快，并且达到了比自适应方法稍高的精度SGDM在培训结束时的测试集。此外，与原型相比，其性能得到了显著提高，测试精度提高了约2%。
ResNet
实验结果如图3所示。正如预期的那样，ResNet-34上的每个算法的总体性能与DenseNet-121上的相似。ADABOUND和AMSBOUND甚至超过SGDM 1%。尽管自适应方法的泛化能力相对较差，但我们提出的方法克服了这一缺点，为其学习速率分配了界限，在CIFAR-10上对DenseNet和ResNet的测试集都获得了几乎最佳的准确率。
4. RECURRENT NEURAL NETWORK
最后，我们对长短时记忆的语言建模任务进行了实验(LSTM)网络(Hochreiter & Schmidhuber, 1997)。从以上两个实验中，我们观察到我们的方法在深度卷积神经网络中比在感知器中表现出更大的改进。因此，我们假设增强与体系结构的复杂性有关，分别运行(L1) 1层、(L2) 2层和(L3) 3层LSTM模型。我们在Penn Treebank上训练他们，运行200个epoch的固定预算。我们使用perplexity作为度量标准来评估性能并报告结果，如图4所示。
我们发现，在所有模型中，ADAM的初始进展最快，但在性能上停滞不前，不如SGD和我们的方法。与以往在图像分类任务实验中出现的现象不同，ADABOUND 和AMSBOUND在训练初期的速度并不快，但曲线比SGD平滑。
5. ANALYSIS
为了研究我们提出的算法的有效性，我们从计算机视觉中选择流行的任务自然语言处理。根据上面的结果，不难发现ADAM和AMSGRAD的表现通常类似，而后者对大多数人来说并没有太大的改善。另一方面，它们的变种，ADABOUND和AMSBOUND，显示了一个快速的速度。与SGD算法相比，收敛性较好，同时也大大超过了两种原始算法在训练结束时测试准确性。这一现象恰恰证实了我们在文中所提到的观点第3节学习速率的大小都会影响收敛性。
此外，我们还对一个感知器、两个深度卷积神经网络和一个递归神经网络组成的不同复杂度的模型进行了实验。感知器在MNIST上使用是最简单的，我们的方法比其他方法的性能稍好。至于DenseNet和ResNet，可以观察到测试精度的明显提高。我们将这种差异归因于模型的复杂性。具体来说，对于深度CNN模型，卷积的和完全的连接的层在任务中扮演不同的角色。另外，不同的卷积层可能是不同的负责不同的角色(Lee et al.， 2009)，这可能导致梯度的明显变化的参数。换句话说，极端的学习速度(巨大的或微小的)可能更频繁地出现在复杂的模型，如ResNet。由于我们的算法是为了避免这些问题而提出的，因此可以直观地解释在复杂体系结构中性能的更大提高。更高的改进在LSTM上的程度与语言建模任务上的分层程度也与上述分析一致。
六、FUTURE WORK
尽管我们的方法取得了较好的效果，但仍存在一些问题有待探索。例如,对简单模型的改进不是很有启发性，我们可以研究如何实现更高对这些模型的改进。此外，我们只讨论了泛化能力弱的原因然而，在自适应方法中，为什么SGD通常在机器学习的不同应用中表现良好仍不确定。最后但并非最不重要的是，对学习速率应用动态边界从自适应方法到SGD的渐进转换只有一种特殊的方式。在那里也许还有其他方法，比如设计良好的衰变也能起作用，这还有待探索。
七、CONCLUSION
我们研究了现有的自适应算法，发现极大或极小的学习率都会导致较差的收敛行为。为证明上述问题，ADAM给出了非收敛性的严格证明。基于SGD较强的泛化能力，我们设计了一种策略来约束ADAM和AMSGRAD的学习速率，以避免剧烈的振荡。我们提出的算法，ADABOUND和AMSBOUND，采用动态边界的学习速率，实现了平稳过渡到SGD。它们在保持自适应方法的快速初始化和超参数不敏感等优点的同时，在多个标准基准上显示了良好的效果。
补充：AMSBOUND
建议去reddit看看最新的讨论，比如说AdaBound在GAN上的结果，作者目前提供了pip下载，tf版本看起来reddit有许多老哥已经在帮作者写了~~
2019/2/28 update 作者提供的pip下载AdaBound会失败，想重新实践的同学可以直接从github上下载源码实验~（亲测了CIFAR确实如作者所说是相对来说最平滑的一条曲线）