第15卷第6期 智能系统学报 Vol.15 No.6 2020年11月 CAAI Transactions on Intelligent Systems Nov.2020 D0L:10.11992tis.202006046 非光滑凸情形Adam型算法的最优个体收敛速率 黄鉴之，丁成诚'，陶蔚2，陶卿 (1.中国人民解放军陆军炮兵防空兵学院信息工程系，安徽合肥23003引；2.中国人民解放军陆军工程大学指挥 控制工程学院，江苏南京210007) 摘要：Adam是目前深度神经网络训练中广泛采用的一种优化算法框架，同时使用了自适应步长和动量 技巧，克服了SGD的一些固有缺陷。但即使对于凸优化问题，目前Adam也只是在线学习框架下给出了和 梯度下降法一样的rgrt界，动量的加速特性并没有得到体现。这里针对非光滑凸优化问题，通过巧妙选 取动量和步长参数，证明了Adam的改进型具有最优的个体收敛速率，从而说明了Adam同时具有自适应 和加速的优点。通过求解l,范数约束下的hige损失问题，实验验证了理论分析的正确性和在算法保持稀 硫性方面的良好性能。 关键词：机器学习；AdaGrad算法；RMSProp算法；动量方法；Adam算法；AMSGrad算法；个体收敛速率；稀疏性 中图分类号：TP181文献标志码：A文章编号：1673-4785(2020)06-1140-07 中文引用格式：黄鉴之，丁成减，陶蔚，等.非光滑凸情形Adam型算法的最优个体收敛速率.智能系统学报，2020,15(6)： 1140-1146 英文引用格式：HUANG Jianzhi,DING Chengcheng,TAO Wei,.etal.Optimal individual convergence rate of Adam-type al- gorithms in nonsmooth convex optimizationJ CAAI transactions on intelligent systems,2020,15(6):1140-1146. Optimal individual convergence rate of Adam-type algorithms in nonsmooth convex optimization HUANG Jianzhi',DING Chengcheng,TAO Wei,TAO Qing' (1.Department of Information Engineering,Army Academy of Artillery and Air Defense of PLA,Hefei 230031,China;2.Command and Control Engineering,Army Engineering University of PLA,Nanjing 210007,China) Abstract:Adam is a popular optimization framework for training deep neural networks,which simultaneously employs adaptive step-size and momentum techniques to overcome some inherent disadvantages of SGD.However,even for the convex optimization problem,Adam proves to have the same regret bound as the gradient descent method under online optimization circumstances;moreover,the momentum acceleration property is not revealed.This paper focuses on nonsmooth convex problems.By selecting suitable time-varying step-size and momentum parameters,the improved Adam algorithm exhibits an optimal individual convergence rate,which indicates that Adam has the advantages of both adaptation and acceleration.Experiments conducted on the /-norm ball constrained hinge loss function problem verify the correctness of the theoretical analysis and the performance of the proposed algorithms in keeping the sparsity. Keywords:machine learning;AdaGrad algorithm;RMSProp algorithm;momentum methods;Adam algorithm;AMS- Grad algorithm;individual convergence rate;sparsity Adam是目前深度学习中广泛采用的一种优 使用了自适应步长和动量两种技巧。其中自适应 化算法"。与经典梯度下降不同的是，Adam同时 步长技巧使算法对超参数不敏感，动量技巧可以 加速算法在处理凸优化问题时的收敛速率，在处 收稿日期：2020-06-28. 理非凸问题时帮助算法避开鞍点甚至局部极值 基金项目：国家自然科学基金项目(61673394：62076252). 通信作者：陶卿.E-mail:qing,tao@ia.ac.cn. 点。与仅使用单一技巧的方法相比，Adam在典
DOI: 10.11992/tis.202006046 非光滑凸情形 Adam 型算法的最优个体收敛速率 黄鉴之1 ，丁成诚1 ，陶蔚2 ，陶卿1 （1. 中国人民解放军陆军炮兵防空兵学院 信息工程系，安徽 合肥 230031; 2. 中国人民解放军陆军工程大学 指挥 控制工程学院，江苏 南京 210007） l1 摘 要 ：Adam 是目前深度神经网络训练中广泛采用的一种优化算法框架，同时使用了自适应步长和动量 技巧，克服了 SGD 的一些固有缺陷。但即使对于凸优化问题，目前 Adam 也只是在线学习框架下给出了和 梯度下降法一样的 regret 界，动量的加速特性并没有得到体现。这里针对非光滑凸优化问题，通过巧妙选 取动量和步长参数，证明了 Adam 的改进型具有最优的个体收敛速率，从而说明了 Adam 同时具有自适应 和加速的优点。通过求解 范数约束下的 hinge 损失问题，实验验证了理论分析的正确性和在算法保持稀 疏性方面的良好性能。 关键词：机器学习；AdaGrad 算法；RMSProp 算法；动量方法；Adam 算法；AMSGrad 算法；个体收敛速率；稀疏性 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2020)06−1140−07 中文引用格式：黄鉴之, 丁成诚, 陶蔚, 等. 非光滑凸情形 Adam 型算法的最优个体收敛速率 [J]. 智能系统学报, 2020, 15(6): 1140–1146. 英文引用格式：HUANG Jianzhi, DING Chengcheng, TAO Wei, et al. Optimal individual convergence rate of Adam-type algorithms in nonsmooth convex optimization[J]. CAAI transactions on intelligent systems, 2020, 15(6): 1140–1146. Optimal individual convergence rate of Adam-type algorithms in nonsmooth convex optimization HUANG Jianzhi1 ，DING Chengcheng1 ，TAO Wei2 ，TAO Qing1 (1. Department of Information Engineering, Army Academy of Artillery and Air Defense of PLA, Hefei 230031, China; 2. Command and Control Engineering, Army Engineering University of PLA, Nanjing 210007, China) Abstract: Adam is a popular optimization framework for training deep neural networks, which simultaneously employs adaptive step-size and momentum techniques to overcome some inherent disadvantages of SGD. However, even for the convex optimization problem, Adam proves to have the same regret bound as the gradient descent method under online optimization circumstances; moreover, the momentum acceleration property is not revealed. This paper focuses on nonsmooth convex problems. By selecting suitable time-varying step-size and momentum parameters, the improved Adam algorithm exhibits an optimal individual convergence rate, which indicates that Adam has the advantages of both adaptation and acceleration. Experiments conducted on the l1 -norm ball constrained hinge loss function problem verify the correctness of the theoretical analysis and the performance of the proposed algorithms in keeping the sparsity. Keywords: machine learning; AdaGrad algorithm; RMSProp algorithm; momentum methods; Adam algorithm; AMSGrad algorithm; individual convergence rate; sparsity Adam 是目前深度学习中广泛采用的一种优 化算法[1]。与经典梯度下降不同的是，Adam 同时 使用了自适应步长和动量两种技巧。其中自适应 步长技巧使算法对超参数不敏感，动量技巧可以 加速算法在处理凸优化问题时的收敛速率，在处 理非凸问题时帮助算法避开鞍点甚至局部极值 点。与仅使用单一技巧的方法相比，Adam 在典 收稿日期：2020−06−28. 基金项目：国家自然科学基金项目 (61673394；62076252). 通信作者：陶卿. E-mail：qing.tao@ia.ac.cn. 第 15 卷第 6 期 智 能 系 统 学 报 Vol.15 No.6 2020 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2020
第6期 黄鉴之，等：非光滑凸情形Adam型算法的最优个体收敛速率 ·1141· 型卷积深度学习的实验中具有一定的优势四。 Adam的最初形式是在梯度下降的基础上使 在梯度下降方法的基础上，首先使用基于梯 用了EMA策略修正步长和Heavy-ball型动量法 度的自适应步长方法是AdaGrad,其主要的思路 修正梯度方向山。尽管Adam在深度学习中有着 是通过对过往所有梯度的外积进行累加的方式进 不错的表现1，但自从Kingma等于2015年提 行步长自适应的调整。虽然AdaGrad在求解非 出Adam后，其收敛性一直是一个具有挑战性的 光滑凸问题时具有和投影次梯度方法一样O() 问题。对于非光滑凸问题，尽管Kingma等声称 的regret界，其中t是算法的迭代步数。AdaGrad 证明了Adam取得了o(vd的regret界，但Reddi 算法最初主要用于正则化学习问题求解，但在深 等却对Adam的收敛性提出了质疑，他们通过理 度学习应用中的效果却很不理想。出现这一问题 论和实验证明，即使是对简单的一维凸函数，Adam 的主要原因是算法对过去梯度的外积单纯做和， 也会出现无法收敛到最优解甚至收敛到最差局部 导致累加项变大得过快。为了克服这一缺陷，Hinton 极值点的现象。出现这一问题的原因在于：采 等采用EMA(exponential moving average)的形 用EMA方式处理梯度时，在迭代后期步长会出 式修改AdaGrad算法累加项的计算方式，提出了 现不降反升的现象，从而会导致目标函数值剧烈 RMSProp算法。RMSProp算法丢弃了相对遥远 波动。为了克服这一问题，Reddi等提出了AMS 的历史梯度信息，保证了若干次迭代后学习能继 Grad和AdamNC两个修改版本。其中，AMSGrad 续进行，较好地适应了目标函数平滑性的局部变 在Adam自适应矩阵上添加了一个确保步长衰减 化。在RMSProp算法的基础上，自适应步长算法 的操作，从而使得在线AMSGrad在一般凸的情况 又有了进一步的发展，典型的算法有AdaDelta等。 下能获得O(V)的regret界。2019年，Wang等 动量法是在经典梯度下降法基础上通过添加 通过对Adam进行适当的变形，得到了强凸情形 动量项演变而来的，广泛用于提高一阶梯度算法 下OIog()的regret界。 的收敛速率。根据动量表示方式的不同以及动量 从目前Adam的各种发展趋势来看，我们更 项中计算梯度位置的不同可以分成两类：一类是 愿意将Adam视为一种利用过去梯度信息同时更 Polyak于1964年提出的Heavy-ball型动量法； 新下降方向和步长的一阶梯度算法框架。本文 另一类是Nesterov!于I983年提出的NAG(nes- 主要研究非光滑凸情形Adam型方法AMSGrad terov accelerated gradient)型动量法。其中，Heay- 的个体收敛速率问题。为了避免叙述上的复杂 ball直接在当前点计算梯度；而NAG会根据当前 性，直接简称为Adam算法。 动量预判下次迭代可能抵达的位置，并在预判的 本文的主要工作有以下3个方面： 位置计算梯度。动量方法的加速性能主要体现在 1)证明了Adam具有O1/Wf的最优个体收 求解凸光滑目标函数时NAG取得的突破，将梯 敛速率。据我们所知，这一理论结果填补了Adam 度下降法的收敛速率0(1/)加速至最优的0(1/)P。 算法在非光滑条件下个体最优收敛性方面研究的 当目标函数光滑且强凸时，虽然动量方法和梯度 缺失，同时也说明了Adam继承了Heay-ball型动 下降法都能达到线性收敛，但动量法由于具有小 量法的优点，体现了动量技巧的特性，可以将个 的收敛因子仍然具有加速性网。 体收敛加速至最优。 对于非光滑凸优化问题，投影次梯度方法目 2)本文的收敛性分析思路具有一定的一般 前获得的最好的个体收敛速率只是o1og)/W。 性，本文首先借鉴了Ghadimi等⑧在光滑条件下 Heavy-ball算法收敛速率的证明方法，得到与梯度 2018年，陶蔚等10-1将NAG步长策略引入到投 下降法相似的迭代公式。为了进一步得到非光滑 影次梯度中，得到了最优个体收敛速率O(1/, 条件下的最优个体收敛速率，与文献[12]类似， 同时保证了良好的稀疏性。2019年，程禹嘉等 本文巧妙设计了时变的步长和动量权重参数，同 证明了Heavy-ball型动量法具有O(1/A的最优 时使用Zinkevich在处理在线优化问题收敛性时 个体收敛速率。由此可以看出，动量方法对非光 使用的技巧，处理变步长与权重导致的递归问题。 滑凸问题同样具有加速作用，只不过体现在个体 3)本文选择了典型的l范数约束下的hinge 收敛速率上。从Heavy-ball型动量法加速个体速 损失函数优化问题，通过与几种具有最优收敛速 率的证明过程来看，主要是借鉴了Ghadimi等s 率算法的比较，验证了理论的正确性和算法在保 在光滑条件下Heavy-ball算法收敛速率的证明。 持稀疏性方面的良好性能
型卷积深度学习的实验中具有一定的优势[1]。 O ( √ t ) t 在梯度下降方法的基础上，首先使用基于梯 度的自适应步长方法是 AdaGrad，其主要的思路 是通过对过往所有梯度的外积进行累加的方式进 行步长自适应的调整[2]。虽然 AdaGrad 在求解非 光滑凸问题时具有和投影次梯度方法一样 的 regret 界，其中 是算法的迭代步数[3]。AdaGrad 算法最初主要用于正则化学习问题求解，但在深 度学习应用中的效果却很不理想。出现这一问题 的主要原因是算法对过去梯度的外积单纯做和， 导致累加项变大得过快。为了克服这一缺陷，Hinton 等 [4] 采用 EMA (exponential moving average) 的形 式修改 AdaGrad 算法累加项的计算方式，提出了 RMSProp 算法。RMSProp 算法丢弃了相对遥远 的历史梯度信息，保证了若干次迭代后学习能继 续进行，较好地适应了目标函数平滑性的局部变 化。在 RMSProp 算法的基础上，自适应步长算法 又有了进一步的发展，典型的算法有 AdaDelta[5] 等。 O(1/t) O ( 1 / t 2 ) 动量法是在经典梯度下降法基础上通过添加 动量项演变而来的，广泛用于提高一阶梯度算法 的收敛速率。根据动量表示方式的不同以及动量 项中计算梯度位置的不同可以分成两类：一类是 Polyak[6] 于 1964 年提出的 Heavy-ball 型动量法； 另一类是 Nesterov[7] 于 1983 年提出的 NAG (nesterov accelerated gradient) 型动量法。其中，Heavyball 直接在当前点计算梯度；而 NAG 会根据当前 动量预判下次迭代可能抵达的位置，并在预判的 位置计算梯度。动量方法的加速性能主要体现在 求解凸光滑目标函数时 NAG 取得的突破，将梯 度下降法的收敛速率 加速至最优的 [7]。 当目标函数光滑且强凸时，虽然动量方法和梯度 下降法都能达到线性收敛，但动量法由于具有小 的收敛因子仍然具有加速性[8]。 O ( log(t)/ √ t ) O ( 1/ √ t ) O ( 1/ √ t ) 对于非光滑凸优化问题，投影次梯度方法目 前获得的最好的个体收敛速率只是 [9]。 2018 年，陶蔚等[10-11] 将 NAG 步长策略引入到投 影次梯度中，得到了最优个体收敛速率 ， 同时保证了良好的稀疏性。2019 年，程禹嘉等[12] 证明了 Heavy-ball 型动量法具有 的最优 个体收敛速率。由此可以看出，动量方法对非光 滑凸问题同样具有加速作用，只不过体现在个体 收敛速率上。从 Heavy-ball 型动量法加速个体速 率的证明过程来看，主要是借鉴了 Ghadimi 等 [8] 在光滑条件下 Heavy-ball 算法收敛速率的证明。 O ( √ t ) O ( √ t ) O ( log(t) ) Adam 的最初形式是在梯度下降的基础上使 用了 EMA 策略修正步长和 Heavy-ball 型动量法 修正梯度方向[1]。尽管 Adam 在深度学习中有着 不错的表现[13-14] ，但自从 Kingma 等于 2015 年提 出 Adam 后，其收敛性一直是一个具有挑战性的 问题。对于非光滑凸问题，尽管 Kingma 等声称 证明了 Adam 取得了 的 regret 界，但 Reddi 等却对 Adam 的收敛性提出了质疑，他们通过理 论和实验证明，即使是对简单的一维凸函数，Adam 也会出现无法收敛到最优解甚至收敛到最差局部 极值点的现象[15]。出现这一问题的原因在于：采 用 EMA 方式处理梯度时，在迭代后期步长会出 现不降反升的现象，从而会导致目标函数值剧烈 波动。为了克服这一问题，Reddi 等提出了 AMSGrad 和 AdamNC 两个修改版本。其中，AMSGrad 在 Adam 自适应矩阵上添加了一个确保步长衰减 的操作，从而使得在线 AMSGrad 在一般凸的情况 下能获得 的 regret 界。2019 年，Wang 等 [16] 通过对 Adam 进行适当的变形，得到了强凸情形 下 的 regret 界。 从目前 Adam 的各种发展趋势来看，我们更 愿意将 Adam 视为一种利用过去梯度信息同时更 新下降方向和步长的一阶梯度算法框架[17]。本文 主要研究非光滑凸情形 Adam 型方法 AMSGrad 的个体收敛速率问题。为了避免叙述上的复杂 性，直接简称为 Adam 算法。 本文的主要工作有以下 3 个方面： O ( 1/ √ t ) 1) 证明了 Adam 具有 的最优个体收 敛速率。据我们所知，这一理论结果填补了 Adam 算法在非光滑条件下个体最优收敛性方面研究的 缺失，同时也说明了 Adam 继承了 Heavy-ball 型动 量法的优点，体现了动量技巧的特性，可以将个 体收敛加速至最优。 2) 本文的收敛性分析思路具有一定的一般 性，本文首先借鉴了 Ghadimi 等 [8] 在光滑条件下 Heavy-ball 算法收敛速率的证明方法，得到与梯度 下降法相似的迭代公式。为了进一步得到非光滑 条件下的最优个体收敛速率，与文献 [12] 类似， 本文巧妙设计了时变的步长和动量权重参数，同 时使用 Zinkevich 在处理在线优化问题收敛性时 使用的技巧，处理变步长与权重导致的递归问题[3]。 3) 本文选择了典型的 l1 范数约束下的 hinge 损失函数优化问题，通过与几种具有最优收敛速 率算法的比较，验证了理论的正确性和算法在保 持稀疏性方面的良好性能。 第 6 期 黄鉴之，等：非光滑凸情形 Adam 型算法的最优个体收敛速率 ·1141·
·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 的形式改变 AdaGrad 算法中矩阵项算数平方和的计算方式，克 服了当梯度较稠密时步长衰减过快的问题。RMSProp 算法中矩阵的计算方式可以表示为 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 基础上结合 Heavyball 型动量技巧发展而来的。具体迭代步骤为 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、AMSGrad 的关键迭代步骤和 Heavy-ball 型动量法式 (3) 并无区别。既然自适应步长策略并不影响算 法的收敛速率，这就启发我们：Adam 型算法应该 和 Heavy-ball 型动量法一样具有最优的个体收敛 速率 。 2 个体收敛速率分析 本节给出非光滑条件下 Adam 算法在个体最 优收敛速率的证明。 pt = t(wt −wt−1) β1,t 为了进行个体收敛性分析，首先借鉴 Ghadimi 等 [8] 在光滑条件下 Heavy-ball 算法收敛速率的 证明，引入加权动量项 。通常情况 下，Adam 动量项的 参数在实际应用中一般设 定为常数，但对于非光滑问题，这种方式无法获 得个体收敛速率。因此本文改变 Adam 动量项的 ·1142· 智 能 系 统 学 报 第 15 卷
第6期 黄鉴之，等：非光滑凸情形Adam型算法的最优个体收敛速率 ·1143· 计算方式为 m,=B1m,+f8 通过巧妙地选取β和6时变参数（见定理1）， 约束情况下随机形式的Adam算法迭代步骤 可以将Adam算法的迭代步骤转化为 可以表示为 w41+P41=,+p,-a,D-12g w41=元o(w,-a,Pm,) (6) 这个关系式和梯度下降法的关键迭代相似， 相对于批处理形式的次梯度g,随机优化每 也和Heavy-ball型动量法的关键迭代十分类似。 次只选择一个样本计算随机次梯度V(w)。由于 正是基于这个关系式，梯度下降法的收敛分析思 “hinge损失”次梯度的计算方式有很多种，这里选 路可以用于Heavy-ball型动量法。受文献[I2] 择文献[20]的方式： 的启发，巧妙设计了时变步长和动量项参数，得 1>.yx Vf(w)= 到了个体收敛速率的递归公式，为了得到递归后 m (7) (Eiy)EA 个体收敛速率的界，这里同样要使用Zinkevich在 其中AS,A={(x)SAy(w,x〉0Z: 线Adam的regret界时使用的技巧。 2)for F1 to T; 引理1令D=maxlbw-l。,Ga。=maxlgll.。, 3)等可能性选取： 设，由式(5)生成，则 4)根据式(7计算随机次梯度Vf(w: 立o,-w6-ra-w 5)取B1.= _P2,EF+2 1 (t+2)Vt-1 6)由式（⑤）计算w+1: s属s 7)end for; 8)输出wro 因为样本点间满足独立同分布，所以计算得 到的随机次梯度Vf(w,)是损失函数在点"，处次 梯度g:的无偏估计。应用文献[21]中将批处理 定理1设f(w)是凸函数，，=a/Vf,取 Bu,=-1Vi 算法收速率转化为随机算法收敛速率的技巧，可 1 (t+2)V1-1 ,民，+2m,由式(5)生 以得到定理2。 成，则 定理2设f(w)是凸函数，=aWF,取 f0w)-fw)sfmo）-fw2+ B,= 后，R,2,由随机Am (t+2)Vt- 1+t 算法生成，则 %2ga2l 2a(1+0台 ELfe,）-fw'】sfwo）-fw2+ 1+t 至此，我们成功得到了Adam算法在非光滑 情况下的最优个体收敛速率，然而，批处理形式 2+a-a2 2a(1+0台 cG。云∑lgul 的Adam算法每次迭代都使用全部样本计算次梯 由定理2可知，得到了随机Adam算法在非 度g,该操作对大规模机器学习问题显然是不可 光滑条件下的最优个体收敛速率。 行的。为了解决该问题，将Adam算法推广至随 3实验 机形式。 本文仅考虑二分类问题，假设训练样本集 本节主要对随机Adam算法的个体收敛速率 S={(1,y),(,2),…,(xm,ym)}∈R×{+1,-1,其中x 的理论分析和稀疏性进行实验验证。 和y分别对应样本的特征向量和监督值，同时 3.1实验数据和比较算法 (x,)之间满足独立同分布。并且只考虑最简 实验采用6个标准数据集，分别是ijcnnl、 单的非光滑稀疏学习问题“hinge损失”，即 covtype、a9a、w8a、CCAT和astro-physic。这些数 f(w)=max(0,1-y,(w,x》的目标函数为 据均来自于LIBSVM网站，具体描述可见表1
计算方式为 mt = β1,tmt +β ′ 1,t gt β1,t β ′ 通过巧妙地选取 和 1,t时变参数(见定理 1)， 可以将 Adam 算法的迭代步骤转化为 wt+1 + pt+1 = wt + pt −αtVˆ −1/2 t gt 这个关系式和梯度下降法的关键迭代相似， 也和 Heavy-ball 型动量法的关键迭代十分类似。 正是基于这个关系式，梯度下降法的收敛分析思 路可以用于 Heavy-ball 型动量法。受文献 [12] 的启发，巧妙设计了时变步长和动量项参数，得 到了个体收敛速率的递归公式，为了得到递归后 个体收敛速率的界，这里同样要使用 Zinkevich 在 线优化时使用的迭代技巧。与文献 [12] 不同的 是，本文需要处理自适应步长矩阵，而不是人为 指定的步长，这里我们又借鉴 Kingma 在证明在 线 Adam 的 regret 界时使用的技巧。 D∞ = max w,u∈Q ∥w−u∥∞ G∞ = max t ∥gt∥∞ wt 引理 1 令 ， ， 设 由式 (5) 生成，则 ∑t j=1 √ j { wj −w ∗ 2 Vˆ 1/2 j − wj+1 −w ∗ 2 Vˆ 1/2 j } + ∑t j=1 1 √ j gj 2 Vˆ −1/2 j ⩽ D 2 ∞ √ t ∑d i=1 Vˆ 1/2 t,i + 2G∞ √ 1−β2 ∑d i=1 g1:t,i 2 f (w) αt = α/ √ t β1,t = t √ t (t+2) √ t−1 Vˆ 1/2 t Vˆ −1/2 t−1 β ′ 1,t= 1 t+2 wt 定 理 1 设 是凸函数， ， 取 ， ， 由式 (5) 生 成，则 f (wt)− f (w ∗ ) ⩽ f (w0)− f (w ∗ ) 1+t + D 2 ∞ √ t 2α(1+t) ∑d i=1 Vˆ 1/2 t,i + αG∞ (1+t) √ 1−β2 ∑d i=1 g1:t,i 2 gt 至此，我们成功得到了 Adam 算法在非光滑 情况下的最优个体收敛速率，然而，批处理形式 的 Adam 算法每次迭代都使用全部样本计算次梯 度 ，该操作对大规模机器学习问题显然是不可 行的。为了解决该问题，将 Adam 算法推广至随 机形式。 S = {(x1, y1),(x2, y2),··· ,(xm, ym)} ∈ R d ×{+1,−1} x y (xi , yi) fi(w) = max(0,1−yi(w, xi)) 本文仅考虑二分类问题，假设训练样本集 ，其中 和 分别对应样本的特征向量和监督值,同时 之间满足独立同分布。并且只考虑最简 单的非光滑稀疏学习问题 “hing e 损 失 ” ， 即 的目标函数为 min w∈Q f (w) = 1 m ∑m i=1 fi(w) 约束情况下随机形式的 Adam 算法迭代步骤 可以表示为 wt+1 = πQ ( wt −αtVˆ −1/2 t mt ) (6) gt ∇fi(w) 相对于批处理形式的次梯度 ，随机优化每 次只选择一个样本计算随机次梯度 。由于 “hinge 损失”次梯度的计算方式有很多种，这里选 择文献 [20] 的方式： ∇fi(w)= 1 m ∑ (xi,yi)∈A + t yixi (7) A + t ⊆ S A + t ={(xi , yi) ⊆ At ; yi⟨w, xi⟩ 0} T 1 t=1 ) 初始化 ，定义步长为 且 ； 2) for t=1 to T； 3) 等可能性选取 i ； ∇f 4) 根据式 (7) 计算随机次梯度 i(wt) ； β1,t = t √ t (t+2) √ t−1 Vˆ 1/2 t Vˆ −1/2 t−1 β ′ 1,t= 1 t+2 5) 取 ， ； 6) 由式 (5) 计算 wt+1； 7) end for； 8) 输出 wT。 ∇fi(wt) wt gt 因为样本点间满足独立同分布，所以计算得 到的随机次梯度 是损失函数在点 处次 梯度 的无偏估计。应用文献 [21] 中将批处理 算法收速率转化为随机算法收敛速率的技巧，可 以得到定理 2。 f (w) αt = α/√ t β1,t = t √ t (t+2) √ t−1 Vˆ 1/2 t Vˆ −1/2 t−1 β ′ 1,t= 1 t+2 wt 定 理 2 设 是凸函数， ， 取 ， ， 由随机 Adam 算法生成，则 E [ f (wt)− f (w ∗ ) ] ⩽ f (w0)− f (w ∗ ) 1+t + D 2 ∞ √ t 2α(1+t) ∑d i=1 Vˆ 1/2 t,i + αG∞ (1+t) √ 1−β2 ∑d i=1 g1:t,i 2 由定理 2 可知，得到了随机 Adam 算法在非 光滑条件下的最优个体收敛速率。 3 实验 本节主要对随机 Adam 算法的个体收敛速率 的理论分析和稀疏性进行实验验证。 3.1 实验数据和比较算法 实验采用 6 个标准数据集，分别是 ijcnn1、 covtype、a9a、w8a、CCAT 和 astro-physic。这些数 据均来自于 LIBSVM 网站，具体描述可见表 1。 第 6 期 黄鉴之，等：非光滑凸情形 Adam 型算法的最优个体收敛速率 ·1143·
·1144· 智能系 统学报 第15卷 表1标准数据集描述 步长a,=lWF。Heavy-ball型动量法的计算方式 Table 1 Introduction of standard datasets 及步长选取同文献[I1]。NAG型动量法的计算 数据集 训练样本数 维数 稀硫度% 方式及步长选取同文献[10]。根据文献[15]： ijcnnl 49990 22 59.09 平均形式输出的Adam算法步长a,=0.1/Vβ= covtype 522911 54 22.12 0.9,B2=0.99。个体形式输出的Adam算法步长设 a9a 24703 123 11.27 置与迭代次数有关，其中a,=0.1/B2=0.99。本 w8a 49749 300 3.88 次实验我们调用SLEP工具箱来实现投影计算， CCAT 23149 47236 0.16 集合Q为1，范数球{w:wl,<z,根据数据集的不 同，z的取值也会有相应变化。 astro-physic 29882 99757 0.08 图1为5种算法的收敛速率对比图，纵坐标 实验对5种随机优化方法进行比较，分别是 表示当前目标函数值与最优目标函数值之差。其 平均形式输出的SGD方法、个体形式输出的 中绿色、蓝色、青色、粉色、红色分别代表平均形 Heavy-ball型动量法、NAG型动量法、平均形式 式输出的SGD算法、个体形式输出的Heavy- 输出的Adam算法及个体形式输出的Adam算 bal型动量法、个体形式输出的NAG型动量法、 法。从理论分析的角度来说，上述5种算法的收 平均形式输出的Adam算法、个体形式输出的 敛界均达到了最优。 Adam算法。可以看到，在5000步迭代之后，5种 3.2实验方法及结论 算法在6个标准数据集上都达到了10-2的精度， 为了算法比较的公平，各个算法在对应数据 在迭代10000步后，5种算法在6个标准数据集 集上运行10次，每次迭代10000步，最后取平均 上都达到了10-4的精度。5种算法的收敛趋势基 值作为输出。SGD算法的计算方式为式(2)，其中 本相同，这与理论分析基本吻合。 10° SGD-avedividual 10f SGD-average NAG-individual idua 10 写102 Adam-individual 103 图 是10 10 SGD-averdividua 10r NAG-individual ￥d Adam-individual 106 10 0 2 4 6 8 10 0 4 6 10 0 2 4 6 8 10 迭代步数/10 迭代步数/10 迭代步数/10 (a)ijcnnl (b)covtype (c)a9a 10° 10 10° 10 10 Adam荒al 10 图102 是1o 室10 SGD-a 103 10r4 二Am-a 10 0 2 10-+ 4 6 8 10 0 2 4 6 8 10 4 6 8 10 迭代步数/10 迭代步数/10 迭代步数/10的 (d)w8a (e)CCAT (f)astro-physic 图1收敛速率对比 Fig.1 Comparison of convergence rates 图2为5种算法的稀疏性对比，纵坐标表示 疏，算法获得的稀疏度也越低。这一结论充分说 各算法对应输出的稀疏度，稀疏度越低，变量中 明，个体解输出比平均解输出能更好地描述样本 非零向量所占比例越小。可以看到，个体形式输 的稀疏性。同时我们观察到在稀疏度一般的前 出的Heavy-ball型动量法、NAG型动量法和 4个数据集上有震荡的现象，这是算法的随机性 Adam算法明显比平均形式输出的SGD算法和 导致的，在维度较大、稀疏度较低的后两个数据 Adam算法拥有更低的稀疏度，同时，数据集越稀 集上该震荡现象消失
表 1 标准数据集描述 Table 1 Introduction of standard datasets 数据集 训练样本数 维数 稀疏度/% ijcnn1 49 990 22 59.09 covtype 522 911 54 22.12 a9a 24 703 123 11.27 w8a 49 749 300 3.88 CCAT 23 149 47 236 0.16 astro-physic 29 882 99 757 0.08 实验对 5 种随机优化方法进行比较，分别是 平均形式输出的 SGD 方法、个体形式输出的 Heavy-ball 型动量法、NAG 型动量法、平均形式 输出的 Adam 算法及个体形式输出的 Adam 算 法。从理论分析的角度来说，上述 5 种算法的收 敛界均达到了最优。 3.2 实验方法及结论 为了算法比较的公平，各个算法在对应数据 集上运行 10 次，每次迭代 10 000 步，最后取平均 值作为输出。SGD 算法的计算方式为式 (2)，其中 αt = 1/ √ t αt = 0.1/ √ tβ1 = 0.9, β2 = 0.99 αt = 0.1/ √ tβ2 = 0.99 Q l1 {w : ∥w∥1 < z} z 步长 。Heavy-ball 型动量法的计算方式 及步长选取同文献 [11]。NAG 型动量法的计算 方式及步长选取同文献 [10]。根据文献 [15]， 平均形式输出的 Adam 算法步长 。个体形式输出的 Adam 算法步长设 置与迭代次数有关，其中 。本 次实验我们调用 SLEP 工具箱来实现投影计算， 集合 为 范数球 ，根据数据集的不 同， 的取值也会有相应变化。 10−2 10−4 图 1 为 5 种算法的收敛速率对比图，纵坐标 表示当前目标函数值与最优目标函数值之差。其 中绿色、蓝色、青色、粉色、红色分别代表平均形 式输出的 SGD 算法、个体形式输出的 Heavyball 型动量法、个体形式输出的 NAG 型动量法、 平均形式输出的 Adam 算法、个体形式输出的 Adam 算法。可以看到，在 5 000 步迭代之后，5 种 算法在 6 个标准数据集上都达到了 的精度， 在迭代 10 000 步后，5 种算法在 6 个标准数据集 上都达到了 的精度。5 种算法的收敛趋势基 本相同，这与理论分析基本吻合。 (f) astro-physic SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 10−2 10−1 100 10−4 10−3 0 2 4 6 8 10 迭代步数/103 相对函数值 (e) CCAT SGD-average Heavy-ball-individual NAG-individual Adam-average 10−2 Adam-individual 10−1 10−4 10−3 0 2 4 6 8 10 迭代步数/103 相对函数值 (d) w8a SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 10−2 10−1 100 10−4 10−3 0 2 4 6 8 10 迭代步数/103 相对函数值 SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 100 10−2 10−4 10−6 0 2 4 6 8 10 (a) ijcnnl 迭代步数/103 相对函数值 SGD-average Heavy-ball-individual NAG-individual Adam-average 10−2 Adam-individual 10−4 10−6 0 2 4 6 8 10 (b) covtype 迭代步数/103 相对函数值 100 SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 10−2 10−1 100 10−4 10−3 0 2 4 6 8 10 (c) a9a 迭代步数/103 相对函数值 图 1 收敛速率对比 Fig. 1 Comparison of convergence rates 图 2 为 5 种算法的稀疏性对比，纵坐标表示 各算法对应输出的稀疏度，稀疏度越低，变量中 非零向量所占比例越小。可以看到，个体形式输 出的 Heavy-ball 型动量法、 NAG 型动量法和 Adam 算法明显比平均形式输出的 SGD 算法和 Adam 算法拥有更低的稀疏度，同时，数据集越稀 疏，算法获得的稀疏度也越低。这一结论充分说 明，个体解输出比平均解输出能更好地描述样本 的稀疏性。同时我们观察到在稀疏度一般的前 4 个数据集上有震荡的现象，这是算法的随机性 导致的，在维度较大、稀疏度较低的后两个数据 集上该震荡现象消失。 ·1144· 智 能 系 统 学 报 第 15 卷
第6期 黄鉴之，等：非光滑凸情形Adam型算法的最优个体收敛速率 ·1145· 1.0 1.0 1.0 0.8 0.8 0.8 0.6 当0.6 A出Aa 0.6 SGD-aver 0.4 0.4 0.4 -Adam-individual iriv 0.2 0.2 0.2 Adam-individual nw 4 6 8 10 0 4 8 2 4 6810 迭代步数/103 迭代步数/10 选代步数/10 (a)ijcnnl (b)covtype (c)a9a 1.0 0.3 0.15r 0.8 0.10 0.6 0.4 NAG-irdividua Adam-individual 0.1 SGD-averein 0.05 0.2 d 6 8 10 0 2 4 6 8 10 0 2 4 6 8 10 迭代步数/10 迭代步数/103 迭代步数/10 (d)w8a (e)CCAT (f)astro-physic 图2稀疏性对比 Fig.2 Comparison of sparsity 4结束语 [5]ZEILER M D.ADADELTA:an adaptive learning rate method EB/0L].(2012-12-22)[2020-04-201.https:/∥arx 本文对非光滑条件下Adam算法的收敛性进 iv.org/abs/1212.5701 行了初步的研究，证明了Adam算法可以获得最 [6]POLYAK B T.Some methods of speeding up the conver- 优的个体收敛速率。本文的结论表明，在最坏情 gence of iteration methods[J].USSR computational math- 况下Adam算法的个体收敛速率和Heavy-ball型 ematics and mathematical physics,1964,4(5):1-17 动量法的个体收敛速率类似。但Adam算法保留 [7]NESTEROV Y E.A method of solving a convex program- 了AdaGrad算法的优，点，个体收敛速率界比Heavy- ming problem with convergence rate O(1/)[J].Soviet bal型动量法更紧。下一步将继续研究强凸情况 mathematics doklady,1983,27(2):372-376. 下Adam算法最优的个体收敛速率问题以及基于 [8]GHADIMI E,FEYZMAHDAVIAN H R,JOHANSSON NAG型动量的Adam算法的最优个体收敛速率 M.Global convergence of the Heavy-ball method for con- vex optimization[C]//Proceedings of 2015 European Con- 问题。 trol Conference.Linz.Austria.2015:310-315. 参考文献： [9]SHAMIR O,ZHANG Tong.Stochastic gradient descent for non-smooth optimization:convergence results and op- [1]KINGMA D P,BA J L.Adam:a method for stochastic op- timal averaging schemes[C]//Proceedings of the 30th Inter- timization[C]//Proceedings of the 3rd International Confer- national Conference on International Conference on Ma- ence for Learning Representations.San Diego,USA,2015. chine Learning.Atlanta,USA,2013:1-71-1-79. [2]DUCHI J.HAZAN E.SINGER Y.Adaptive subgradient [IO]陶蔚，潘志松，储德军，等.使用Nesterov步长策略投影 methods for online learning and stochastic optimization[J]. 次梯度方法的个体收敛性).计算机学报，2018,41(1)： The journal of machine learning research,2011,12: 164176. 2121-2159 TAO Wei,PAN Zhisong,CHU Dejun,et al.The indi- [3]ZINKEVICH M.Online convex programming and general- vidual convergence of projected subgradient methods us- ized infinitesimal gradient ascent[C]//Proceedings of the ing the Nesterov's step-size strategy[J].Chinese journal 20th International Conference on Machine Learning. of computers,2018,41(1)y164-176. Washington.USA.2003:928-935 [11]TAO Wei,PAN Zhisong,WU Gaowei,et al.The strength [4]TIELEMAN T,HINTON G.Lecture 6.5-RMSProp:di- of Nesterov's extrapolation in the individual convergence vide the gradient by a running average of its recent mag- of nonsmooth optimization[J].IEEE transactions on neur- nitude[R].Toronto:University of Toronto,2012. al networks and learning systems,2020,31(7):
SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 1.0 0.6 0.8 0.2 0.4 0 2 4 6 8 10 (a) ijcnnl 迭代步数/103 稀疏度 SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 1.0 0.6 0.8 0.2 0.4 0 2 4 6 8 10 (d) w8a 迭代步数/103 稀疏度 SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 0.3 0.2 0.1 0 2 4 6 8 10 (e) CCAT 迭代步数/103 稀疏度 SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 0.15 0.10 0.05 0 2 4 6 8 10 (f) astro-physic 迭代步数/103 稀疏度 SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 1.0 0.6 0.8 0.2 0.4 0 2 4 6 8 10 迭代步数/103 稀疏度 (b) covtype SGD-average Heavy-ball-individual NAG-individual Adam-average Adam-individual 1.0 0.6 0.8 0.2 0.4 0 2 4 6 8 10 迭代步数/103 稀疏度 (c) a9a 图 2 稀疏性对比 Fig. 2 Comparison of sparsity 4 结束语 本文对非光滑条件下 Adam 算法的收敛性进 行了初步的研究，证明了 Adam 算法可以获得最 优的个体收敛速率。本文的结论表明，在最坏情 况下 Adam 算法的个体收敛速率和 Heavy-ball 型 动量法的个体收敛速率类似。但 Adam 算法保留 了 AdaGrad 算法的优点，个体收敛速率界比 Heavyball 型动量法更紧。下一步将继续研究强凸情况 下 Adam 算法最优的个体收敛速率问题以及基于 NAG 型动量的 Adam 算法的最优个体收敛速率 问题。 参考文献： KINGMA D P, BA J L. Adam: a method for stochastic optimization[C]//Proceedings of the 3rd International Conference for Learning Representations. San Diego, USA, 2015. [1] DUCHI J, HAZAN E, SINGER Y. Adaptive subgradient methods for online learning and stochastic optimization[J]. The journal of machine learning research, 2011, 12: 2121–2159. [2] ZINKEVICH M. Online convex programming and generalized infinitesimal gradient ascent[C]//Proceedings of the 20th International Conference on Machine Learning. Washington, USA, 2003: 928−935. [3] TIELEMAN T, HINTON G. Lecture 6.5-RMSProp: divide the gradient by a running average of its recent magnitude[R]. Toronto: University of Toronto, 2012. [4] ZEILER M D. ADADELTA: an adaptive learning rate method[EB/OL]. (2012–12–22)[2020–04–20]. https://arxiv.org/abs/1212.5701 [5] POLYAK B T. Some methods of speeding up the convergence of iteration methods[J]. USSR computational mathematics and mathematical physics, 1964, 4(5): 1–17. [6] NESTEROV Y E. A method of solving a convex programming problem with convergence rate O(1/k 2 )[J]. Soviet mathematics doklady, 1983, 27(2): 372–376. [7] GHADIMI E, FEYZMAHDAVIAN H R, JOHANSSON M. Global convergence of the Heavy-ball method for convex optimization[C]//Proceedings of 2015 European Control Conference. Linz, Austria, 2015: 310−315. [8] SHAMIR O, ZHANG Tong. Stochastic gradient descent for non-smooth optimization: convergence results and optimal averaging schemes[C]//Proceedings of the 30th International Conference on International Conference on Machine Learning. Atlanta, USA, 2013: 1-71−1-79. [9] 陶蔚, 潘志松, 储德军, 等. 使用 Nesterov 步长策略投影 次梯度方法的个体收敛性 [J]. 计算机学报, 2018, 41(1): 164–176. TAO Wei, PAN Zhisong, CHU Dejun, et al. The individual convergence of projected subgradient methods using the Nesterov’s step-size strategy[J]. Chinese journal of computers, 2018, 41(1): 164–176. [10] TAO Wei, PAN Zhisong, WU Gaowei, et al. The strength of Nesterov’s extrapolation in the individual convergence of nonsmooth optimization[J]. IEEE transactions on neural networks and learning systems, 2020, 31(7): [11] 第 6 期 黄鉴之，等：非光滑凸情形 Adam 型算法的最优个体收敛速率 ·1145·
·1146· 智能系统学报 第15卷 2557-2568. 272-279 [12]程禹嘉，陶蔚，刘字翔，等.Heavy-Ball型动量方法的最 [19]AGARWAL A,BARTLETT P L.RAVIKUMAR P,et al 优个体收敛速率).计算机研究与发展，2019,56(8)： Information-theoretic lower bounds on the oracle com- 1686-1694. plexity of stochastic convex optimization[J].IEEE trans- CHENG Yujia,TAO Wei,LIU Yuxiang,et al.Optimal actions on information theory,2012,58(5):3235-3249. individual convergence rate of the Heavy-ball-based mo- [20]SHALEV-SHWARTZ S.SINGER Y.SREBRO N.et al. mentum methods[J].Journal of computer research and de- Pegasos:primal estimated sub-gradient solver for velopment,2019,56(8):1686-1694. SVM[J].Mathematical programming,2011,127(1):3-30. [13]KIROS R.ZEMEL R S.SALAKHUTDINOV R.et al.A [21]RAKHLIN A,SHAMIR O,SRIDHARAN K.Making multiplicative model for learning distributed text-based gradient descent optimal for strongly convex stochastic attribute representations[C]//Proceedings of the 27th In- optimization[C]//Processing of the 29th International ternational Conference on Neural Information Processing Conference on International Conference on Machine Systems.Montreal,Canada,2014:2348-2356 Learning.Edinburgh,Scotland,2012:1571-1578. [14]BAHAR P,ALKHOULI T,PETER J T,et al.Empirical 作者简介： investigation of optimization algorithms in neural ma- 黄鉴之，硕士研究生，主要研究方 chine translation[J].The Prague bulletin of mathematical 向为凸优化算法及其在机器学习中的 linguistics,2017,108(1):13-25. 应用。 [15]REDDI S J,KALE S,KUMAR S.On the convergence of Adam and beyond[C]//Processing of the 6th International Conference on Learning Representations.Vancouver, Canada,2018. [16]WANG Guanghui,LU Shiyin,TU Weiwei,et al.SAdam: 丁成诚，硕士研究生，主要研究方 a variant of Adam for strongly convex functions[C //Pro- 向为凸优化算法及其在机器学习中的 cessing of the 8th International Conference on Learning 应用。 Representations.Addis Ababa,Ethiopia,2020. [17]CHEN Xiangyi,LIU Sijia,SUN Ruoyu,et al.On the con- vergence of a class of Adam-type algorithms for non-con- vex optimization[C]//Processing of the 7th International Conference on Learning Representations.New Orleans, 陶卿，教授，博士，主要研究方向 为模式识别、机器学习和应用数学。 USA,2019 承担国家自然科学基金、安徽省自然 [18]DUCHI J.SHALEV-SHWARTZ S,SINGER Y,et al.Ef- 科学基金等。发表学术论文60余篇。 ficient projections onto the /1-ball for learning in high di- mensions[C]//Processing of the 25th International Confer- ence on Machine learning.Helsinki,Finland,2008:
2557–2568. 程禹嘉, 陶蔚, 刘宇翔, 等. Heavy-Ball 型动量方法的最 优个体收敛速率 [J]. 计算机研究与发展, 2019, 56(8): 1686–1694. CHENG Yujia, TAO Wei, LIU Yuxiang, et al. Optimal individual convergence rate of the Heavy-ball-based momentum methods[J]. Journal of computer research and development, 2019, 56(8): 1686–1694. [12] KIROS R, ZEMEL R S, SALAKHUTDINOV R, et al. A multiplicative model for learning distributed text-based attribute representations[C]//Proceedings of the 27th International Conference on Neural Information Processing Systems. Montreal, Canada, 2014: 2348−2356. [13] BAHAR P, ALKHOULI T, PETER J T, et al. Empirical investigation of optimization algorithms in neural machine translation[J]. The Prague bulletin of mathematical linguistics, 2017, 108(1): 13–25. [14] REDDI S J, KALE S, KUMAR S. On the convergence of Adam and beyond[C]//Processing of the 6th International Conference on Learning Representations. Vancouver, Canada, 2018. [15] WANG Guanghui, LU Shiyin, TU Weiwei, et al. SAdam: a variant of Adam for strongly convex functions[C]//Processing of the 8th International Conference on Learning Representations. Addis Ababa, Ethiopia, 2020. [16] CHEN Xiangyi, LIU Sijia, SUN Ruoyu, et al. On the convergence of a class of Adam-type algorithms for non-convex optimization[C]//Processing of the 7th International Conference on Learning Representations. New Orleans, USA, 2019. [17] DUCHI J, SHALEV-SHWARTZ S, SINGER Y, et al. Efficient projections onto the l1-ball for learning in high dimensions[C]//Processing of the 25th International Conference on Machine learning. Helsinki, Finland, 2008: [18] 272−279. AGARWAL A, BARTLETT P L, RAVIKUMAR P, et al. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization[J]. IEEE transactions on information theory, 2012, 58(5): 3235–3249. [19] SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos: primal estimated sub-gradient solver for SVM[J]. Mathematical programming, 2011, 127(1): 3–30. [20] RAKHLIN A, SHAMIR O, SRIDHARAN K. Making gradient descent optimal for strongly convex stochastic optimization[C]//Processing of the 29th International Conference on International Conference on Machine Learning. Edinburgh, Scotland, 2012: 1571−1578. [21] 作者简介： 黄鉴之，硕士研究生，主要研究方 向为凸优化算法及其在机器学习中的 应用。 丁成诚，硕士研究生，主要研究方 向为凸优化算法及其在机器学习中的 应用。 陶卿，教授，博士，主要研究方向 为模式识别、机器学习和应用数学。 承担国家自然科学基金、安徽省自然 科学基金等。发表学术论文 60 余篇。 ·1146· 智 能 系 统 学 报 第 15 卷
