陶卿,博士,教授,主要研究方向为模式识别、机器学习、应用数学.E-mail:qing.tao@ia.ac.cn.
张泽东,硕士研究生,主要研究方向为模式识别、机器学习.E-mail:1632783823@qq.com.
陇盛,硕士研究生,主要研究方向为模式识别、机器学习.E-mail:ls15186322349@163.com.
鲍蕾,博士,讲师,主要研究方向为模式识别、计算机视觉.E-mail:baolei1219@sina.cn.
同时使用动量和自适应步长技巧的自适应矩估计(Adaptive Moment Estimation, Adam)型算法广泛应用于深度学习中.针对此方法不能同时在理论和实验上达到最优这一问题,文中结合AdaBelief灵活调整步长提高实验性能的技巧,以及仅采用指数移动平均(Exponential Moving Average, EMA)策略调整步长的Heavy-Ball动量方法加速收敛的优点,提出基于AdaBelief的Heavy-Ball动量方法.借鉴AdaBelief和Heavy-Ball动量方法收敛性分析的技巧,巧妙选取时变步长、动量系数,并利用添加动量项和自适应矩阵的方法,证明文中方法对于非光滑一般凸优化问题具有最优的个体收敛速率.最后,在凸优化问题和深度神经网络上的实验验证理论分析的正确性,并且证实文中方法可在理论上达到最优收敛性的同时提高性能.
ZHANG Zedong, master student. His research interests include pattern recognition and machine learning.
LONG Sheng, master student. His research interests include pattern recognition and machine learning.
BAO Lei, Ph.D., lecturer. Her research interests include pattern recognition and computer vision.
Adaptive moment estimation algorithms with momentum and adaptive step techniques are widely applied in deep learning. However, these algorithms cannot achieve the optimal performance in both theory and experiment. To solve the problem, an AdaBelief based heavy-ball momentum method, AdaBHB, is proposed. The AdaBelief technique of adjusting step size flexibly is introduced to improve the algorithm performance in experiments. The heavy ball momentum method with step size adjusted by exponential moving average strategy is employed to accelerate convergence. According to the convergence analysis techniques of AdaBelief and Heavy-ball momentum methods, time-varying step size and momentum coefficient are selected skillfully and the momentum term and adaptive matrix are added. It is proved that AdaBHB gains the optimal individual convergence rate for non-smooth general convex optimization problems. Finally, the correctness of the theoretical analysis of the proposed algorithm is verified by experiments on convex optimization problems and deep neural networks, and AdaBHB is validated to obtain the optimal convergence in theory with performance improved.
随机梯度下降法[1]是解决优化问题的经典算法之一, 在其基础上添加动量和自适应步长技巧是机器学习领域用于提升优化算法性能常用的两种方式.动量方法利用梯度的历史累积信息调整解向量的更新方向, 而自适应步长技巧利用梯度的历史信息调整梯度在不同维度上的步长.从理论分析的角度上说:动量方法能加速梯度下降方法的收敛速率, 避开非凸优化中的局部极小点和鞍点[2, 3]; 自适应步长方法能降低对人为指定步长的依赖, 在处理稀疏学习问题时具有更紧的收敛界[4, 5].
Kingma等[6]同时采用动量的指数移动平均(Exponential Moving Average, EMA)形式和自适应步长调整技巧, 提出自适应矩估计(Adaptive Moment Estimation, Adam), 其中EMA是指当前位置梯度与历史累积梯度的一个凸组合, 可通过调整凸组合中权系数的大小, 强调当前位置的梯度信息, 并逐渐遗忘历史梯度信息.动量的EMA形式使Adam在深度学习的实际应用中取得一定成功[7], 同时具有较好的直观解释, Adam也因此成为目前深度学习中使用最普遍的一种优化算法.但是, Reddi等[8]重新审视Adam的收敛性分析, 发现即使对于简单的凸优化问题, Adam都无法收敛到全局极小值, 这一问题也称为Reddi问题.虽然Reddi等[8]提出AMSGrad和AdamNC修正算法, 但在线AMSGrad在一般凸情况下只获得O(
为了进一步提升Adam性能, 学者们开始试图对自适应步长方法进行更精细的改进[10].特别是Zhuang等[11]提出AdaBelief, 在Adam的基础上将动量的EMA形式看成是下一次迭代的预估方向, 根据当前位置梯度方向是否与动量的EMA形式方向一致而灵活地调整步长.当梯度方向与动量的EMA形式方向一致时, 选择相信, 采用较大的步长; 当两者方向相反时, 选择怀疑, 采用较小的步长.AdaBelief的这种步长策略更好地适应问题自身的特征, 同时具有Adam快速收敛特性和随机梯度下降法的泛化性能.实验表明, AdaBelief在训练和测试精度方面均取得较优的实际效果, 但由于其使用与Adam一样的EMA策略, 仍无法避免收敛性方面存在的Reddi问题, 导致未能较好体现动量的加速性能.
实际上, 使用动量的EMA形式不仅在收敛性分析上导致目前仍无法解决的困难, 在实际应用中还存在其它问题.Zou等[12]指出, EMA形式的动量仅利用当前步的学习率信息, 当动量系数趋近于1时, 动量的EMA 策略会导致算法迭代陷入停滞, 但Heavy-Ball动量由于利用历史的学习率信息, 不会出现此问题.为此, Tao等[13]在Heavy-Ball型动量方法中放弃对动量使用EMA策略, 提出仅采用EMA策略调整步长的动量方法, 即自适应重球(Adaptive Heavy-Ball, AdaHB), 克服理论分析中采用平均输出方式与实际应用中却采用最后一次迭代作为输出的不一致问题.与文献[13]一样, 本文称以所有迭代平均为最终输出时的收敛速率为平均收敛速率, 称最后一步迭代作为输出时的收敛速率为个体收敛速率.相比平均, 个体输出在处理稀疏优化问题时往往具有更好的稀疏性, 但是却更难获得个体收敛速率[14, 15].对于非光滑凸问题, 相比使用动量EMA策略的Adam, AdaHB获得O(1/
在不影响Adam收敛性证明的基础上, AdaBelief的步长调整技巧提高实际性能.另一方面, 仅采用EMA策略调整步长的Heavy-Ball动量方法可获得最优的个体收敛速率.因此, 本文结合AdaBelief步长调整的思想与Heavy-Ball动量方法, 提出基于AdaBelief的Heavy-Ball动量方法(AdaBe-lief Based Heavy-Ball Moment Method, AdaBHB).结合采用EMA策略调整步长的Heavy-Ball型动量方法的个体收敛性, 与AdaBelief的平均收敛性分析的一般思路, 并借鉴AdaBelief中处理步长项的方法, 证明本文方法在非光滑凸情形下具有O(1/
本节介绍动量方法和自适应算法, 以及它们的收敛性.
考虑约束优化问题:
其中, f(w)为目标函数, 一般为凸函数, Q⊆Rn为有界闭凸集.投影次梯度方法的迭代步骤[1]为
wt+1=wt-α tgt.
其中:wt为w在第t次迭代的输出; α t为设置的衰减学习率, 一般凸情形下取α t=α /
对于投影次梯度等算法, 平均收敛速率是指f(
w* 为问题的最优解.个体收敛速率是指f(wt)-f(w* )的收敛速率.非光滑凸条件下投影次梯度算法的平均收敛速率为O(1/
为了简单起见, 与文献[8]和文献[13]一样, 在算法的更新公式中省略偏差修正步骤.Adam更新公式如下[6]:
mt=β 1, tmt-1+(1-β 1, t)gt, Vt=β 2, tVt-1+(1-β 2, t)
其中:为了收敛性分析的需要, 均采取时变的学习率α t代替常数α ; β 1, t为时变动量的加权系数, β 2, t为自适应矩阵的加权系数; mt为EMA形式的动量; Vt为自适应矩阵;
可以看出, Adam与投影次梯度算法的不同主要体现在使用动量的EMA形式mt调整参数更新方向, 并采用自适应矩阵Vt调整参数更新的每维步长.
AMSGrad具体形式如下:
它只是在Adam自适应矩阵上添加一个使步长衰减的操作, 获得O(
AdaBelief更新公式如下:
mt=β 1, tmt-1+(1-β 1, t)gt, St=β 2, tSt-1+(1-β 2, t)(gt-mt)2, wt+1=wt-α tm
可以看出, AdaBelief仅是在Adam的基础上更改计算自适应矩阵的方式, 自适应矩阵由原来的
Heavy-Ball动量方法的迭代公式为
wt+1=wt-α tgt+β t(wt-wt-1),
其中, α t为设置的衰减学习率, β t∈ [0, 1)为动量系数[2], wt-wt-1为动量项.当动量系数为常数时, 分别将Heavy-Ball动量和EMA动量展开为梯度累加和的形式, 可得
HB: wt+1=wt-
可以看出, Heavy-Ball动量在参数更新时利用α i(i=1, 2, …, t)的信息, 而动量的EMA形式仅利用α t的信息, 另外当动量系数β 趋近于1时, (1-β )→ 0, 使用动量的EMA形式时, wt+1≈ wt, 而使用Heavy-Ball动量却不会出现这样的问题[12].
AdaHB迭代公式为
Vt=β 2, tVt-1+(1-β 2, t)
AdaHB只是在Heavy-Ball动量的基础上引入Adam的自适应矩阵Vt, δ 为常数因子, 确保分子不为0.通过
本节提出基于AdaBelief的Heavy-Ball动量方法(AdaBHB), 给出在目标函数为非光滑一般凸情况下算法的最优个体收敛性证明.
将AdaBelief策略下的自适应步长技巧与AdaHB结合, 提出AdaBHB, 迭代形式为
St=β 2tSt-1+(1-β 2t)[gt-(wt-wt-1)]2,
不同于AdaHB, AdaBHB中自适应矩阵St的更新借鉴AdaBelief的思想, 即对当前梯度与动量项差值的外积矩阵对角阵进行EMA平均, 与之不同的是动量项不再采用EMA形式的动量mt, 而是借鉴AdaHB的思想, 采用Heavy-Ball动量wt-wt-1.
在进行最优个体收敛性的证明时, 参考Tao等[13]提出的仅采用EMA策略调整步长的Heavy-Ball动量方法的收敛性分析思路, 引入加权动量项
pt=t(wt-wt-1),
巧妙选取时变步长α t和动量因子β 1t, 从而将AdaBHB的迭代方式转化为类似于投影次梯度法的形式[13]:
wt+1+pt+1=wt+pt-
借鉴此方法处理迭代, 得到如下引理1.为了证明的简洁性, 这里的证明采用无约束情况下的证明方式, 有约束情况下的证明只需在此基础上利用投影的非扩张性即可.
引理1 令
pt=t(wt-wt-1),
假设wt由式(1)产生, 取
β 1t=
则有
wt+1+pt+1=wt+pt-
证明 根据迭代式(1), 并令
pt=t(wt-wt-1),
有
wt+1+pt+1=wt+1+(t+1)(wt+1-wt)=(t+2)wt+1-(t+1)wt=wt-(t+2)α t
代入
α t=
可得
wt+1+pt+1=wt+pt-
证毕可以看出, 不同于AdaHB, AdaBHB的自适应矩阵由原来的
基于式(2)可证明定理1, 但为了解决变步长和动量系数导致的递归问题, 先提出引理2.
引理2 令
D=
假设‖ gt‖ ≤ G, 存在常数c, 使得
证明 使用Zhuang等[11]证明在线AdaBelief的regret界时采用的迭代技巧, 进行如下整理:
$\sum^{T}_{t=1} \sqrt{t}\{|| wt-w*||^{2}_{\dot{s}t}-||wt+1-w*||^{2}_{\dot{s}t}\}+\sum^{T}_{t=1} \frac{1}{\sqrt{t}}||gt||^{2}_{\dot{s}_{t}-1}≤ \\ ||w1.w*||^{2}_{\dot{s}1}\sum^{T}_{t=2} \{\sqrt{t}wt-w*||^{2}_{\dot{s}t}\sqrt{t-1}wt-w*||^{2}_{\dot{s}t-1} \}\frac{1}{\sqrt{c}}\sum^{T}_{t=1}\frac{G^{2}}{\sqrt{t}} \\ ||w1-w*+||^{2}_{\dot{s}_{1}}\sum^{T}_{t=2} \{||\sqrt{t}t-w*-||^{2}_{\dot{s}t}||\sqrt{t-1}t-w*||^{2}_{\dot{s}_{t-1}}\} \frac{G^{2}}{\sqrt{c}}\sum^{T}_{t=1}\frac{1}{\sqrt{t}} \\ ||w1-w*+||^{2}_{\dot{s}_{1}}\sum^{T}_{t=2}\sum^{d}_{i=2} \{,i-)2w,*i(\sqrt{t}\widehat{S}t,i\sqrt{t-1}\widehat{S}_{t-1,i})\}2\frac{G^{2}}{\sqrt{c}}-1\sqrt{T}≤ \\ \sum^{d}_{i=1}\{D^{2}_{\widehat{S}1,i}\}\sum^{T}_{t=2}\sum^{d}_{i=1}\{D^{2}_{(} (\sqrt{t}\widehat{S}_{t,i}\sqrt{t-1}\widehat{S}_{t-1,i})\}\frac{G^{2}}{\sqrt{c}}1)\sqrt{T}+D^{2}_{\sqrt{T}}\sum^{d}_{i=1}\widehat{S}_{T,i}-\frac{G^{2}}{\sqrt{c}}).\sqrt{T}$
证毕
定理1 设f(w)为一般凸函数, 取
β 1t=
假设存在常数c, 使得
f(wT)-f(w* )≤
证明 由引理1及投影的非扩张性可得
‖ wt+1+pt+1-w*
等式两边同时乘以
将上式从t=1, 2, …, T累加, 得
2α (1+T)(f(wT)-f(w* ))≤ 2α (f(w0)-f(w* ))+
根据引理2, 可得
f(wT)-f(w* )≤
证毕
推论1 设f(w)为一般凸函数, 取
β 1t=
wt由式(1)产生, 则
f
推论1也表明个体收敛速率比平均收敛速率更难以获得.综上所述, 获得AdaBHB在非光滑一般凸条件下的个体收敛速率.然而上述证明都是在批处理条件下完成的, 所以这种操作并不适用于大规模数据集.为了使AdaBHB适合处理大规模机器学习问题, 接下来将算法推广至随机形式.
考虑较简单的二分类问题, 训练样本集:
S={(xi, yi)|i=1, 2, …, m}⊆Rn× {1, -1},
其中, xi为样本特征, yi为样本的标签值, 假设(xi, yi)是独立同分布的.
假设非光滑学习问题的损失函数为hinge损失, 即
fi(w)=max{0, 1-yi< w, xi> },
则优化目标函数为:
由于hinge损失函数的次梯度有多种计算方式, 这里采用文献[18]的方式进行计算, 即
fi(wt)=
其中,
At⊆S,
实验中设定|At|=1, i是算法迭代到第t步时为计算当前梯度而随机抽取的样本序号.当样本满足独立同分布条件时, 经过随机抽取方式计算得到的随机次梯度fi(wt)就是梯度在wt处的无偏估计.
约束条件下随机形式的AdaBHB的迭代公式如下:
wt+1=PQ
相比批处理形式下次梯度gt的每次计算都需遍历样本集, 随机次梯度fi(wt)只需选取一个样本即可.
AdaBHB的执行步骤如下所示.
算法 AdaBHB
输入 循环次数T
输出 wT
初始化 向量w1∈ Q
For t=1 to T
等可能地选取i=1, 2, …, m
根据式(3)计算次梯度fi(wt)
取β 1t=
通过式(4)计算wt+1
End for
从算法中可看出, 随机形式的算法只是将批处理形式下目标函数的梯度替换为无偏估计.Rakhlin等[19]给出将批处理算法的regret界转换为随机算法regret界的技巧, 该技巧对于定理1同样成立.与文献[14]和文献[15]类似, 本文可将定理1推广至随机形式, 得到定理2.
定理2 设f(w)为一般凸函数, 取
β 1t=
wt由式(4)产生, 则
E(f(wT)-f(w* ))≤
由定理2可知, AdaBHB具有O(1/
凸优化实验中的问题模型为支持向量机中常见的hinge损失.本文采用Astro、A9a、Covtype、Ijcnn1、Rcv1、W8a标准数据集, 均来源于LIBSVM网站.
在深度学习实验中, 按照Wang等[20]和Tao等[13]的思路, 模型为典型的ResNet-18网络及构造的一般4层卷积神经网络(Convolutional Neural Net-work, CNN), 采用CIFAR10、CIFAR100和MNIST常用标准数据集.CIFAR10数据集包含50 000个训练样本, 10 000个测试样本.CIFAR100数据集包含50 000个训练样本, 10 000个测试样本.MNIST数据集包含60 000个训练样本, 10 000个测试样本.
为了验证AdaBHB既在理论上具有最优收敛性, 又在实验上具有良好效果, 对比算法选取理论上收敛性最优的Heavy-Ball(HB)算法、AdaHB, 以及在实验上表现良好的随机梯度下降(Stochastic Gradient Descent, SGD)、Adam、Ada-Belief.
两组实验使用相同的参数设置.对于所有算法共同具有的超参数α , 采取从{1, 0.1, 0.01, 0.001, 0.0001}中线性搜索的方式, 并取其中最优的一次实验结果, 作为算法的最终输出.对比算法的其它参数设置均采用文献中该算法在实验表现最佳的参数.SGD的学习率α t=α /
α t=
为了降低随机因素产生的影响, 各算法在每个数据集上均运行5次, 取平均值作为最后输出.
在凸优化实验中, 调用有效投影稀疏学习(Spares Learning with Efficient Projections, SLEP)工具箱的函数, 实现投影的计算, PQ为l1范数球
{w∶ ‖ w≤ z‖ 1}
上的投影算子.根据数据集的不同, z对应选取不同的值, 并且各算法均取相同的约束参数.从理论分析的角度出发, AdaBHB应具有最优的收敛速率.
各算法在6个数据集上的收敛速率对比如图1所示, 图中纵坐标表示当前目标函数值与最优目标函数值之差.由图可见, 在100步迭代之后, 各算法在6个标准数据集上都达到10-4的精度, 收敛趋势基本相同, AdaBHB收敛最快, 这与理论分析是吻合的.
在深度学习实验中, 采用参数权重衰减和批量归一化策略以减少过拟合, 所用的损失为交叉熵.图2为各算法在2个网络上的损失对比, 图3为各算法在2个网络上的测试精度对比.
由图2和图3可见, AdaBHB在损失降低速率上明显占优, 这也促进其在测试精度上效果良好.在其它深度学习网络上的实验也验证AdaBHB取得较优的实验效果, 因此具有普遍性.由于论文篇幅限制, 本文仅展示较典型的残差网络Res-Net18和CNN4上的结果.
实验表明, AdaBHB不仅在非光滑凸条件下理论上可获得最优的个体收敛速率, 并且在深度学习实验中也取得性能的提升.这也说明AdaBelief 的步长调整技巧可作为一般性的减少震荡、提升算法泛化性能的方法.AdaBHB结合传统动量方法的优点, 可发展出更多性能良好的优化算法.
本文结合AdaBelief的步长调整技巧和Heavy-Ball型动量项, 提出基于AdaBelief的Heavy-Ball动量方法(AdaBHB), 证明算法具有最优的个体收敛速率, 并在深度学习实验中得到验证.今后将研究强凸情况下AdaBHB的个体收敛速率, 以及将Nesterov加速梯度(Nesterov Accelerated Gradient, NAG)型动量与AdaBelief的步长调整技巧结合的优化算法的收敛速率等问题.