第34卷第2期2021年2月
模式识别与人工智能
Pattern Recognition and Artificial Intelligence
Vol.34No.2
Feb.2021
自适应策略下Heav y Ball型动量法的
最优个体收敛速率
黄鉴之1陇盛1陶卿1
1.Department of Information Engineering，Chinese Academy of
People's Liberation Army Artillery Air Defense Academy，
Hefei230031
摘要同时使用自适应步长和动量两种优化技巧的AMSGrad在收敛性分析方面存在比自适应步长算法增加一个对数因子的问题.为了解决该问题，文中在非光滑凸情形下，巧妙选取动量和步长参数，证明自适应策略下Heavy-Ball型动量法具有最优的个体收敛速率，说明自适应策略下Heavy-Ball型动量法兼具动量的加速特性和自适应步长对超参数的低依赖性.求解Z，范数约束下的Hinge损失问题，验证理论分析的正确性.
关键词自适应步长算法，动量算法，AMSGrad，个体收敛速率
引用格式黄鉴之，陇盛，陶卿.自适应策略下Heavy-Ball型动量法的最优个体收敛速率.模式识别与人工智能，2021，34(2):137-145.
DOI10.16451/jki.issn1003-6059.202102005中图法分类号TP181
Optimal Individual Convergence Rate of Heavy-Ball Based Momentum Methods Based on Adaptive Step-Size Strategy
HUANG Jianzhi1，LONG Sheng1，TAO Qing1
ABSTRACT Optimization techniques，including adaptive step-size and momentum，are both utilized in AMSGrad.Compared with the adaptive step-size algorithms，there is one more logarithm f
actor in AMSGrad for convergence analysis.To solve the problem，the non-smooth convex problems are studied in this paper.By selecting the time-varying step-size and momentum parameters correctly，it is proved that the Heavy-ball-based momentum methods with adaptive step-size obtain the optimal individual convergence rate.It is indicated that the Heavy-ball-based momentum methods with adaptive step-size hold the advantages in both adaptation and acceleration.Hinge loss problem under L1-norm constraint is solved to verify the correctness of theoretical analysis.
Key Words Adaptive Step-Size Algorithm，Momentum Algorithm，AMSGrad，Individual Convergence Rate
Citation HUANG J Z，LONG S，TAO Q.Optimal Individual Convergence Rate of Heavy-Ball-Based Momentum Methods Based on Adaptive Step-Size Strategy.Pattern Recognition and Artificial
Intelligence，2021，34(2):137-145.
收稿日期：2020-10-10；录用日期：2020-11-23 Manuscript received October10，2020；
accepted November23，2020
国家自然科学基金项目(No.61673394,62076252)资助Supported by National Natural Science Foundat
ion of China(No. 61673394，62076252)
本文责任编委陈恩红
Recommended by Associate Editor CHEN Enhong
1.中国人民解放军陆军炮兵防空兵学院信息工程系合肥230031
自适应步长和动量是目前深度学习中常用的两种优化技巧.自适应步长技巧利用数据稀疏的特性，保留历史梯度信息，降低算法对超参数的依赖性[|].动量技巧可加速算法在求解凸问题时的收敛速率，在处理非凸问题时可越过鞍点甚至局部极值点[2].同时使用自适应步长和动量技巧的算法有Adam(Adaptive Moment Estimation)⑶、Nadam(Nes ­
138模式识别与人工智能(PR&AI)第34卷
terov Accelerated Adaptive Moment Estimation)［4］A AMSGrad［5］、AdamNC⑸等.但是，上述算法不论是自适应步长还是动量都是建立在指数移动平均的基础上，给算法收敛性分析带来较大困难.
自适应步长方法利用优化过程中的历史梯度信息实现步长的动态调整.常见的自适应步长：1)Du-chi等山在AdaGrad(Adaptive Gradient Algorithm中提出的算数平均型,2)Zou等［6］在RMSProp(Root Mea
n Square Propagation)中提出的指数移动平均(Exponential Moving Average,EMA)型.Mukkama-la等［7］证明，当EMA中衰减参数取特殊变值时，可特化为算数平均.AdaGrad通过对过去所有梯度外积做和的方式实现步长自适应，在一般凸的情况下，可获得和梯度下降法一样0(t)的regret界,t表示迭代步数.AdaGrad最初主要用于求解正则化学习问题，对于稀疏优化问题，由于过往梯度能较好地反映数据稀疏特性，可获得最优的依赖于数据的regret 界.虽然AdaGrad在稀疏优化中具有一些优点，但由于算法在自适应步长方面采用算数平均，对历史梯度赋予相同的权重，在深度学习应用中无法适应函数平滑性的局部变化.为了克服这一缺陷,RMSProp 采用EMA形式修改AdaGrad外积累加方式，丢弃相 对遥远的梯度信息，较好地适应函数平滑性的局部变化，保证若干次迭代后算法还能继续进行.同时, RMSProp也获得依赖数据0(t)的regret界［7］.
动量法是在经典梯度下降法基础上添加动量项演变而来，广泛用于提高一阶梯度算法的收敛速率.同时，因为动量中隐含梯度的平均，也被当作方差减速器使用［8］.近年来，动量法广泛应用于深度神经网络训练，根据动量项计算方式不同，可将动量法分为2类：1)Polyak⑼提出的Heavy-Ball型动量法，2)Nesterov［l0］提出的NAG(Nesterov Accelerated Gradient)型动量法.两者的主要区别在于计算梯度的位置不同,Heavy-Ball型动量法在当前位置计算梯度,NAG型动量法会根据当前动量预估下次迭代可能到达的位置，并在预估的位置计算梯度.动量法的加速特性主要体现在求解光滑凸问题时NAG型动量将梯度下降法0(1/t)的收敛速率加速至0(1/t2).当目标函数光滑强凸时，动量法和梯度下降法均能达到线性收敛，但动量法具有较小的收敛因子，仍具有加速性［11］.
对于非光滑凸优化问题，大多数算法都能获得0(1/t)的最优收敛速率，但这都是在平均输出方式下获得的.在个体收敛速率方面，投影次梯度方法目前获得最好的收敛速率，为0(lnt/t)［12］.陶蔚等［13］和Tao等［14］将NAG步长策略引入投影次梯度中，得到最优个体收敛速率0(1/t)，并保证良好的稀疏性.程禹嘉等［15］证明Heavy-Ball型动量法具有0(1/t)的最优个体收敛速率.由此可看出，动量法对非光滑凸问题同样具有加速作用，只不过体现在个体收敛速率上.从Heavy-ball型动量法加速个体速率的证明过程上看，主要是借鉴Ghadimi等［11］在光滑条件下Heavy-ball算法收敛速率的证明，利用与梯度下降法之间的联系，巧妙设置步长，基于动量项递归得到个体收敛速率.
Kingma等［3］结合EMA型自适应步长和EMA 型动量，提出Adam.Adam在深度学习中具有较优表现，但因其使用EMA策略，导致在算法收敛性分析方面困难较多.尽管Kingma等⑶证明Adam算法在一般凸情形下能取得0(t)的regret界，但Reddi 等［5］却对此结论提出质疑，并提出AMSGrad和AdamNC这两个修正算法.相比Adam,AMSGrad在收敛性分析上增加一个对数因子［16］.从自适应算法的证明过程上看，只要步长策略具有和投影次梯度方法在人为指定步长时的类似规律，就能获得和梯度下降法相同的收敛速率.从动量法的证明过程来看，非光滑凸情形下动量不影响投影次梯度法的平均收敛速率，可加速个体收敛速率.因此为了解决AMSGrad收敛速率增加一个对数因子的问题，本文主要研究自适应策略下Heavy-Ball型动量法的个体收敛速率问题.
基于上述分析，本文在非光滑凸情形下借鉴光滑情形下Heavy-Ball型动量法的证明思路，得到类似梯
度下降法的迭代步骤，同时使用Zinkevich［17］在处理在线优化问题收敛性时使用的技巧，处理变步长与权重导致的递归问题.巧妙选取时变步长和动量项前权重参数，得到非光滑情形下的最优个体收敛速率0(1/t)，解决AMSGrad收敛速率增加一个对数因子的问题，同时也说明自适应策略下Heavy-Ball型动量法兼具动量的加速特性和自适应步长对超参数的低依赖性.选择典型的l范数约束下的Hinge损失函数优化问题，验证理论分析的正确性.
1典型自适应算法和动量算法的收敛性
训练深度神经网络相当于解决如下约束优化
第2期黄鉴之等：自适应策略下Heavy-Ball型动量法的最优个体收敛速率139
问题:
min/(w),(1)
w沂Q
其中，/(w)为损失函数，这里只考虑它为凸函数的情况,0哿R"为有界闭凸集.记w*为式(1)的一个最优解.
1.1梯度下降法
梯度下降法(Gradient Descent,GD)是解决问题(1)常用的算法之一，迭代步骤如下：
w,+1=w t-琢,g t-
其中：w，表示第t次迭代后到达的位置；琢，为人工设置的衰减步长，一般凸情形下取琢,=琢/t，琢>0；g t 为函数f(w)在点w t处的次梯度.
平均收敛速率是指f(w t)-f(w*)的收敛速率，其中
w t=1
移w
i=1
与之对应，个体收敛速率是指f(w t)-f(w*)的收敛速率.通常来说，对于非光滑问题，个体收敛更难获得最优速率.
Agarwal等［18］证明非光滑一般凸情形下梯度下降可获得。(1/t)的最优平均收敛速率，即
f(w t)-f(w*)臆0(1/尿).
在小规模学习问题中,GD对各下降方向选取相同的步长可能会影响算法性能［19］.为了解决该问题，自适应步长算法利用历史梯度信息实现动态调整各下降方向的步长.
1.2自适应步长方法
AdaGrad和RMSProp的迭代步骤可统一写为
w t+1=w t-琢t匕"g t-(2)其中：V t为d伊d维的自适应矩阵，为对角矩阵；
a t=a/7t，琢> 0.
显然，按照GD的表示方式，可将自适应步长方法的步长视为a t V t-"2.
AdaGrad中自适应矩阵V t为过去所有梯度外积矩阵的算数平均：
V t=|移g，
其中,g=diag(g jg［)，表示计算梯度g j的外积再将其对角化.
AdaGrad的步长
(t)-1血
琢t V t-1/2=琢移g;
I j=1丿
为0(1/t)阶.可看到，因为梯度的累积，算法在稀疏的维度上使用较大的步长，在稠密的维度上使用较小的步长，同时在一般凸情形下算法能获得
r d)
0移际L
I>=1丿
依赖于数据的regret界，其中g”，为｛g］忌，…,g t1构成的d伊t维矩阵,g H t,I表示由矩阵g.t第i行组成的向量.
RMSProp中自适应矩阵V t为过去所有梯度外积矩阵的移动指数平均：
V t=0t V t-1+(1-0t)g2,(3)其中0，沂［0,1),—般情况下经验性地将茁取0-9或0.99，当0t为常数时，步长也为0(1/t)阶.采用EMA形式计算自适应矩阵，分配给过去梯度的权重会以指数衰减，起主要作用的仅限于最近个
1-0t
梯度.自适应矩阵V t由递归得到，也可将其改写为累加的形式：
t r t)
V t=移(1-0j)n茁g j.
j=1I k=j+1丿
当
0t
1-1
时，
t i r t
匕=移j n
j=1
r k-1］、
k
\/
g j2,
丿
I k=j+1
整理可得
V t=1移g j.
j=1
这时EMA型自适应矩阵转化为算数平均型自适应矩阵.
由此可见，AdaGrad是RMSProp的一个特例.一般凸情形下，当
1-1臆0t臆1一酌，°< 酌臆1,t逸1
时,RMSProp也能获得
r d)
0移际tj|2
I>=1丿
依赖于数据的regret界［7］.
1.3Heavy-ball型动量法和AMSGrad
与自适应步长法类似,Heavy-ball型动量法中动量也有2种计算形式:1)Polyak⑼提出的以迭代前后两点位置之差为动量的传统Heavy-ball型动量法，迭代步骤如下：
w t+1=w t-a t g t+“t(w t-w t-1),(4)其中,w,-w t_1为动量，沂［0,1)为动量的衰减系
140模式识别与人工智能(PR&AI)第34卷
数.2)利用历史梯度，采用EMA 形式计算动量，迭代
步骤如下：
=f 滋,m t _i  + (1 -滋,)g t ,
w ,+i  = w t  - a t 叫,
其中m t 为动量.
AMSGrad 同时使用EMA 型自适应步长和EMA
型动量，迭代步骤如下：
m t  =/滋t m t  +
(1 - “ t )g t ,
V t  =茁 V t-, +(1 -茁,)g 2, 卒
卒
(5)
V t  = max  {
V t-,,V t  }
,
w t+1 = w , - «t  V t -"2m t -一般凸情形下,AMSGrad 只能获得
° 曲移 Ilg1：t,.lL
I  ; =1 丿
的regret 界，这比单独使用自适应步长技巧的
RMSProp 增加一个对数因子.
从2种自适应步长法的式(2)可看出，只要步 长保持和梯度下降法一样的。(1 / t )阶，就能获得
和梯度下降法一样的收敛速率.程禹嘉等［15］在动量
法式(4)的基础上证明Heavy-Ball 型动量法具有
0(1 / t )的最优个体收敛速率.这2种技巧单独使
用都能达到最优收敛速率，结合本文式(2)中的自
适应步长技巧与式(4)中的动量技巧，提出自适应
策略下Heavy-Ball 型动量法，解决AMSGrad 无法取
得最优收敛性的问题，迭代形式如下：
w t+1 = w t  - «t V -宁g t  +“,(w t  - w t-1),
(6)
其中自适应矩阵采用RMSProp 中式(3)的形式.
2 个体收敛速率分析
根据输出方式的不同，收敛速率分为平均收敛
速率和个体收敛速率.通常来说，对于非光滑问题,
个体收敛速率更难获得，同时，个体收敛速率可通过
简单的累加变换为平均收敛速率，更具有普适性.本
节给出自适应策略下Heavy-Ball 型动量法的个体最 优收敛速率的证明.
因为AdaGrad 是RMSProp 的一个特例，所以本
节只考虑EMA 型自适应矩阵.为了进行个体收敛性
分析，首先借鉴Ghadimi 等［11］在光滑条件下对式
(4)的Heavy-ball 算法收敛速率的证明，引入加权
动量项
Pt  = t ( w t  - w t-1
)-
巧妙选取梯度和动量前的时变参数，可将式(6)的
迭代步骤转化为
w t+1 + Pt+1 = w t  +
P t  -琢V t -"2g t -
(7)
Jt
这个关系式和自适应步长法的关键迭代步骤相
似，正是由于这种相似性，使自适应步长法的收敛性
分析思路可用于自适应策略下Heavy-Ball 型动 量法.
受程禹嘉等［15］的启发，巧妙设计梯度和动量前 的时变参数，得到个体收敛速率的递归公式，为了得
到递归后个体收敛速率的界，这里同样要使用
Zinkevich ［17］在在线优化时使用的迭代技巧.与程
禹嘉等［15］不同的是，文献［17］的迭代技巧需要处
理自适应步长矩阵，而不是人为指定的衰减步长.
基于式(7)，可证明定理1，但为了解决变步长 和权重导致的递归问题，先证明引理1.
引理1 令
2 = max w  - “ ，
u 沂Q
1 —
臆茁t 臆1 —酌,0 < 酌臆1, t 逸1,t  t  t
由式(6)生成W t ，则
移琢{IIw-- w *
V/2 - llw+1- w * V/2
}
+
移；g j
V ；1 /2 臆
t 移吃+2琢(2酌-酌儿移必
臆
2
+ 2琢（2 -酌）
琢
酌
\ '
丿
）d
证明 根据文献［7］引理4. 1可知，
移戶韻I
7
使用Zinkevich ［17］在线优化时使用的迭代技巧进行整理：
移琢{I \w j - w * V/2 - llw+1- w * V/2} + 移；g , V -
d
臆2(2 一酌)t 移隙1 /2
臆
第2期黄鉴之 等：自适应策略下Heavy-Ball 型动量法的最优个体收敛速率141
，移｛J I
Iw- - w * IIV,1/2
- d  - 11Iw  - w * llV ；r  1
｝ + 占l w 1 一 w * II V ；72
+ 移 Ji Ig jl IV ,-1 z 2
琢
琢
J  = 2 '
，移移｛ (w ” - w ； )2(J V  2 -」「邮)｝ + |w 「
=2 i= 1
，
移移｛D 制V ,2 -vj^r V 1-2”)｝
t 移减2 +2琢：一酌)t 移VT  =
i  = 1
i  = 1
D ¥ + 2琢(2 -酌)
琢 酌
\ '
丿
d
+ 1移｛D ¥吧｝
-w * 即 + 移—I  Igjll  V,-"2
d
移 tVtf.
定理1 设f(w )为一般凸函数，取“t=：,f (w t ) -f (w *) 臆f (w o )-f (心 +t  + 1琢
琢t  =
Jt  (t  + 2)
+ 琢(2 -酌)
酌(t  + 1) 0
,w ，由式(5)生成，则
、2 琢(t  + 1))d
移则?•证明 w t+1 + P t+1 = w t+1 + (t  + 1)(w ,+1 - wj  = (t  + 2)w ,+1-(t+1) “ …，-：
g t ，
w t  + 1
+ P t  + 1- w  * IlVy 2
w t
+ P t 琢1 /2
-V  g t  - w
t
2
V 7 2
ll w t
+ P t -w V 1 ‘2
+ :Tl?tllV t -1 /2
-
2
(w t
+ P t  - w
琢
,g t
t
w t
+ P t -w V  ‘2+
g t
V t -1" - 2
(
w t
- w *，話gj  - 2t
(
w t  一 w t-1，話gj  臆
琢
t
ll w t
+ Pt  一 w
V 1 ‘2
2
+ 琢rl |g tl lV t -1，2 - 2岸(f(w ,) -f(w *)) - 2-J ta (f(wj  -f(w_1))
不等式两边同乘琢：
2(t  + 1)[f(wJ  -f(w *)]臆
2t[f(w t-1) -f(w *)] + 琢Tlw  + p t  -w * A  -琢「曲+1 + p t+1 -w * A  + ： g t  V,-"2'
2(t  + 1)[f(wJ  -f(w *)]臆
J l  l w k
+ P k  一 w * J  - J  l w k  + 1 + P k  + 1 - w  * IIV ；/2
\ 丿
2 [f ( W o ) -f( w *)] + 移
J  = 1
根据引理 1 可得
+移琢J  = 1 /2( t  + 1) [/(wj  -f ( w * )]臆 2[/(W o ) -f ( w * ) ] +
f ( w t ) -f ( w *) 臆 f ( w o )-f (旷)+
t  + 1推论1 当
0，= 1 - t
(0
D ¥ + 2琢(2 -酌)
琢
酌
\ 丿
\ dadaptive
D ¥ + 琢(2 -酌)、2琢 (t  + 1)酌(t  + 1)丿
\ d
移尿V t,2,
时，RMSProp 转化为AdaGrad ，此时可得
t 必
ll g 1： t,i  I L
，

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。