·1142· 智能系统学报 第15卷 1典型自适应及动量算法的收敛性 式中：Be[0,l:diag()表示只保留矩阵对角元素， 其余元素置0。通过设置不同的B,分配给过去 考虑有约束优化问题： 梯度的权重会以指数方式衰减，起到主要作用 miof(w) (1) 的仅限于最近的几个梯度，实际应用中一般取 式中：f(w)为凸函数；QsR为有界闭凸集。记 B=0.9。 w是式(1)的一个最优解。 相较于梯度下降法，Heavy-ball型动量法使用 梯度下降法是解决问题式(1)的经典方法，基 动量作为迭代的方向，EMA形式Heavy-ball型动 于梯度反方向总是指向目标函数下降的方向这一 量法可以表示为 事实，具体迭代步骤为 m,=B,m+(1-B,)gw+1=w,-a,m (3) w=o(w,-ag )argminllw -(w:-a:g (2) 式中B,∈[0,1)。通过巧妙设置步长和动量参数， EO Heavy-ball型动量法具有O1/A的最优个体收敛 式中：πe为集合Q上的投影算子11；，=aWG,m 速率。 为大于0的常数；g,是函数f(w)在点m,处的次 Adam是在RMSProp基础上结合Heavy 梯度。 ball型动量技巧发展而来的。具体迭代步骤为 平均收敛速率指的是f(m,-w)的收敛速率， m=B1m+(1-B1)g 其中可=∑如，。 与之对应，个体收敛速率指 V,=B2V1+(1-B2)diag(gg) 的是f(w,)-f(w)的收敛速率。通常来说，对于非 WuI=w:-aVIPm (4) 光滑问题，个体收敛更难获得最优速率。 一：B2∈[0,1)。实际应用中一般取 Agarwal等u证明非光滑一般凸情形下投影 式中：，= VtB 次梯度式(2)能获得0(1/W同的最优平均收敛速 B1.=0.9,B2=0.99。 率，即 为了解决Adam的收敛性问题，AMSGrad在 Adam自适应矩阵上添加一个使步长衰减的操 E[f(w,)-fw】≤01/NA 作，具体形式为 AdaGrad的具体迭代步骤为 V=max V-1.V, Wm =W:-aVPg wHi=w:-aV Pm (5) 式中：V,为d×d维对角矩阵，将矩阵第i维上的 改进后的Adam算法在B=B,/t时能取得 元素表示为V,V=∑g为过去所有梯度第i o(vd的regret界。 人 比较Heavy-ball型动量法的式(3)、Adam的 个元素的算数平方和，P矩阵中对角元素VP= 式(4)和AMSGrad的式(5)可以看出：除了多了 1-1/2 g。显然，可以将AdaGrad算法的步 一个自适应步长的矩阵V2外，Adam、AMS- Grad的关键迭代步骤和Heavy-ball型动量法式 解为αV,因为梯度累积的影响，算法会自动增 (3)并无区别。既然自适应步长策略并不影响算 加稀疏维度的步长，减小其他维度的步长。对于 法的收敛速率，这就启发我们：Adam型算法应该 凸的目标函数，AdaGrad能取得o∑lga的 和Heavy-ball型动量法一样具有最优的个体收敛 速率o(1/W。 regret界，其中g1:为{g1,g2,…,g}构成的d×t维 矩阵，g1表示由矩阵gu第i行组成的向量。由 2个体收敛速率分析 此可以看出，AdaGrad在最坏情况下能取得O(vd) 的regret界，当梯度是稀疏时该regret界会变得 本节给出非光滑条件下Adam算法在个体最 更紧。 优收敛速率的证明。 RMSProp算法采用EMA的形式改变Ad- 为了进行个体收敛性分析，首先借鉴Ghadimi aGrad算法中矩阵项算数平方和的计算方式，克 等8I在光滑条件下Heavy-ball算法收敛速率的 服了当梯度较稠密时步长衰减过快的问题。RM 证明，引入加权动量项p:=1(w,-w-)。通常情况 SProp算法中矩阵的计算方式可以表示为 下，Adam动量项的Bu参数在实际应用中一般设 定为常数，但对于非光滑问题，这种方式无法获 V,=βV-+(1-β)diag(gg) 得个体收敛速率。因此本文改变Adam动量项的1 典型自适应及动量算法的收敛性 考虑有约束优化问题： min w∈Q f (w) (1) f (w) Q ⊆ R n w ∗ 式中： 为凸函数； 为有界闭凸集。记 是式 (1) 的一个最优解。 梯度下降法是解决问题式 (1) 的经典方法，基 于梯度反方向总是指向目标函数下降的方向这一 事实，具体迭代步骤为 wt+1 = πQ (wt −αt gt) = argmin w∈Q ∥w−(wt −αt gt)∥ 2 2 (2) πQ Q αt = α/√ t α gt f (w) wt 式中： 为集合 上的投影算子[18] ； ， 为大于 0 的常数； 是函数 在点 处的次 梯度。 f ( wt −w ∗ ) wt =   ∑t j=1 wj   / t f (wt)− f (w ∗ ) 平均收敛速率指的是 的收敛速率， 其中 。与之对应，个体收敛速率指 的是 的收敛速率。通常来说，对于非 光滑问题，个体收敛更难获得最优速率。 O ( 1/ √ t ) Agarwal 等 [19] 证明非光滑一般凸情形下投影 次梯度式 (2) 能获得 的最优平均收敛速 率，即 E [ f ( wt ) − f (w ∗ ) ] ⩽ O ( 1/ √ t ) AdaGrad 的具体迭代步骤为 wt+1 = wt −αV −1/2 t gt Vt d ×d i Vt,i Vt,i= ∑t j=1 g 2 j,i i V −1/2 t V −1/2 t,i =   ∑t j=1 g 2 j,i   −1/2 αV −1/2 t O   ∑d i=1 g1:t,i 2   g1:t {g1, g2,··· , gt} d ×t g1:t,i g1:t i O ( √ t ) 式中： 为 维对角矩阵，将矩阵第 维上的 元素表示为 ， 为过去所有梯度第 个元素的算数平方和, 矩阵中对角元素 。显然，可以将 AdaGrad 算法的步长理 解为 ，因为梯度累积的影响，算法会自动增 加稀疏维度的步长，减小其他维度的步长。对于 凸的目标函数，AdaGrad 能取得 的 regret 界，其中 为 构成的 维 矩阵， 表示由矩阵 第 行组成的向量。由 此可以看出，AdaGrad 在最坏情况下能取得 的 regret 界，当梯度是稀疏时该 regret 界会变得 更紧[2]。 RMSProp 算法采用 EMA 的形式改变 Ad￾aGrad 算法中矩阵项算数平方和的计算方式，克 服了当梯度较稠密时步长衰减过快的问题。RM￾SProp 算法中矩阵的计算方式可以表示为 Vt = βVt−1 +(1−β)diag( gt g T t ) β ∈ [0,1); diag(·) β β=0.9 式中： 表示只保留矩阵对角元素， 其余元素置 0。通过设置不同的 ，分配给过去 梯度的权重会以指数方式衰减，起到主要作用 的仅限于最近的几个梯度，实际应用中一般取 。 相较于梯度下降法，Heavy-ball 型动量法使用 动量作为迭代的方向，EMA 形式 Heavy-ball 型动 量法可以表示为 mt = βtmt +(1−βt) gtwt+1 = wt −αtmt (3) βt ∈ [0,1) O ( 1/ √ t ) 式中 。通过巧妙设置步长和动量参数， Heavy-ball 型动量法具有 的最优个体收敛 速率[12]。 Adam 是在 RMSProp 基础上结合 Heavy￾ball 型动量技巧发展而来的。具体迭代步骤为 mt = β1,tmt + ( 1−β1,t ) gt Vt = β2Vt−1 +(1−β2)diag( gt g T t ) wt+1 = wt −αtV −1/2 t mt (4) αt = α √ tβ1,t ；β2 ∈ [0,1) β1,t=0.9, β2=0.99 式中： 。实际应用中一般取 。 为了解决 Adam 的收敛性问题，AMSGrad 在 Adam 自适应矩阵上添加一个使步长衰减的操 作，具体形式为 Vˆ t = max{ Vˆ t−1,Vt } wt+1 = wt −αtVˆ −1/2 t mt (5) β1,t = β1/t O ( √ t ) 改进后的 Adam 算法在 时能取得 的 regret 界。 V −1/2 t O ( 1/ √ t ) 比较 Heavy-ball 型动量法的式 (3)、Adam 的 式 (4) 和 AMSGrad 的式 (5) 可以看出：除了多了 一个自适应步长的矩阵 外 ，Adam、AMS￾Grad 的关键迭代步骤和 Heavy-ball 型动量法式 (3) 并无区别。既然自适应步长策略并不影响算 法的收敛速率，这就启发我们：Adam 型算法应该 和 Heavy-ball 型动量法一样具有最优的个体收敛 速率 。 2 个体收敛速率分析 本节给出非光滑条件下 Adam 算法在个体最 优收敛速率的证明。 pt = t(wt −wt−1) β1,t 为了进行个体收敛性分析，首先借鉴 Ghadimi 等 [8] 在光滑条件下 Heavy-ball 算法收敛速率的 证明，引入加权动量项 。通常情况 下，Adam 动量项的 参数在实际应用中一般设 定为常数，但对于非光滑问题，这种方式无法获 得个体收敛速率。因此本文改变 Adam 动量项的 ·1142· 智 能 系 统 学 报 第 15 卷