非光滑凸情形Adam 型算法的最优个体收敛速率--688IT编程网

DOI : 10.11992/tis.202006046

非光滑凸情形Adam 型算法的最优个体收敛速率

黄鉴之1，丁成诚1，陶蔚2，陶卿1

（1. 中国人民解放军陆军炮兵防空兵学院信息工程系，安徽合肥 230031; 2. 中国人民解放军陆军工程大学指挥控制工程学院，江苏南京 210007）

l 1摘要：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 al-gorithms 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 Jianzhi 1，DING Chengcheng 1，TAO Wei 2，TAO Qing 1

(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; moreov

er, 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 l 1-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 是目前深度学习中广泛采用的一种优化算法[1]

。与经典梯度下降不同的是，Adam 同时

使用了自适应步长和动量两种技巧。其中自适应步长技巧使算法对超参数不敏感，动量技巧可以加速算法在处理凸优化问题时的收敛速率，在处理非凸问题时帮助算法避开鞍点甚至局部极值点。与仅使用单一技巧的方法相比，Adam 在典

收稿日期：2020−06−28.正则化收敛速率

基金项目：国家自然科学基金项目(61673394；62076252).通信作者：陶卿. E-mail ：**************.

第 15 卷第 6 期智　能　系　统　学　报

Vol.15 No.62020 年 11 月

CAAI Transactions on Intelligent Systems

Nov. 2020

型卷积深度学习的实验中具有一定的优势[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 (nes-

terov accelerated gradient)型动量法。其中，Heavy-ball 直接在当前点计算梯度；而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 等提出了AMS-Grad 和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]

。

l 13)本文选择了典型的范数约束下的hinge 损失函数优化问题，通过与几种具有最优收敛速率算法的比较，验证了理论的正确性和算法在保持稀疏性方面的良好性能。

第 6 期黄鉴之，等：非光滑凸情形Adam 型算法的最优个体收敛速率

·1141·

1 典型自适应及动量算法的收敛性

考虑有约束优化问题：

f (w )Q ⊆R n w ∗式中：为凸函数；为有界闭凸集。记是式(1)的一个最优解。

梯度下降法是解决问题式(1)的经典方法，基于梯度反方向总是指向目标函数下降的方向这一事实，具体迭代步骤为

πQ Q αt =α/√

t α

g t f (w )w t 式中：为集合上的投影算子

[18]

；，为大于0的常数；是函数在点处的次

梯度。

f (w t −w ∗)

w t = t ∑j =1

w j /t f (w t )−f (w ∗)平均收敛速率指的是的收敛速率，

其中。与之对应，个体收敛速率指

的是的收敛速率。通常来说，对于非

光滑问题，个体收敛更难获得最优速率。

O (1/√t

)

Agarwal 等[19]

证明非光滑一般凸情形下投影

次梯度式(2)能获得的最优平均收敛速率，即

AdaGrad 的具体迭代步骤为

V t d ×d i V t ,i V t ,i =

t ∑

j =1

g 2j ,i i

−1/2t

V −1/2

t ,i

t ∑j =1

g 2j ,i −1/2αV −1/2t

O d ∑i =1

g 1:t ,i 2 g 1:t {g 1,g 2,···,g t }d ×t g 1:t ,i g 1:t i O (√t )式中：为维对角矩阵，将矩阵第维上的元素表示为，为过去所有梯度第个元素的算数平方和, 矩阵中对角元素。显然，可以将AdaGrad 算法的步长理解为，因为梯度累积的影响，算法会自动增

加稀疏维度的步长，减小其他维度的步长。对于

凸的目标函数，AdaGrad 能取得的

regret 界，其中为构成的维

矩阵，表示由矩阵第行组成的向量。由

此可以看出，AdaGrad 在最坏情况下能取得的regret 界，当梯度是稀疏时该regret 界会变得

更紧[2]

。

RMSProp 算

法采用EMA 的形式改变Ad-aGrad 算法中矩阵项算数平方和的计算方式，克服了当梯度较稠密时步长衰减过快的问题。RM-SProp 算法中矩阵的计算方式可以表示为

β∈[0,1);diag(·)ββ=0.9式中：表示只保留矩阵对角元素，

其余元素置0。通过设置不同的，分配给过去梯度的权重会以指数方式衰减，起到主要作用的仅限于最近的几个梯度，实际应用中一般取。

相较于梯度下降法，

Heavy-ball 型动量法使用动量作为迭代的方向，EMA 形式Heavy-ball 型动量法可以表示为

βt ∈[0,1)O (1/√t )式中。通过巧妙设置步长和动量参数，

Heavy-ball 型动量法具有的最优个体收敛

速率[12]

。

Adam 是在RMSProp 基础上结合Heavy-ball 型动量技巧发展而来的。具体迭代步骤为

αt =α

√

t β1,t

；β2∈[0,1)β1,t =0.9,β2=0.99式中：。实际应用中一般取。

为了解决Adam 的收敛性问题，AMSGrad 在Adam 自适应矩阵上添加一个使步长衰减的操

β1,t =β1/t O (√t )

改进后的Adam 算法在时能取得的regret 界。

V −1/2t O (1/√t )

比较Heavy-ball 型动量法的式(3)、Adam 的式(4)和AMSGrad 的式(5)可以看出：除了多了一个自适应步长的矩阵外，Adam 、AMS-Grad 的关键迭代步骤和Heavy-ball 型动量法式(3)并无区别。既然自适应步长策略并不影响算法的收敛速率，这就启发我们：Adam 型算法应该和Heavy-ball 型动量法一样具有最优的个体收敛

速率。

2 个体收敛速率分析

本节给出非光滑条件下Adam 算法在个体最

优收敛速率的证明。

p t =t (w t −w t −1)β1,t 为了进行个体收敛性分析，首先借鉴Ghadimi 等[8]

在光滑条件下Heavy-ball 算法收敛速率的证明，引入加权动量项。通常情况下，Adam 动量项的参数在实际应用中一般设定为常数，但对于非光滑问题，这种方式无法获得个体收敛速率。因此本文改变Adam 动量项的

·1142·智　能　系　统　学　报第 15 卷

计算方式为

β1,t β′1,t 通过巧妙地选取和时变参数(见定理1)，可以将Adam 算法的迭代步骤转化为

这个关系式和梯度下降法的关键迭代相似，也和Heavy-ball 型动量法的关键迭代十分类似。正是基于这个关系式，梯度下降法的收敛分析思路可以用于Heavy-ball 型动量法。受文献[12]的启发，巧妙设计了时变步长和动量项参数，得到了个体收敛速率的递归公式，为了得到递归后个体收敛速率的界，这里同样要使用Zinkevich 在线优化时使用的迭代技巧。与文献[12]不同的是，本文需要处理自适应步长矩阵，而不是人为指定的步长，这里我们又借鉴Kingma 在证明在线Adam 的regret 界时使用的技巧。

D ∞=max w ,u ∈Q

∥w −u ∥∞G ∞=max t

∥g t ∥∞w t 引理 1　令，，

设由式(5)生成，则

f (w )αt =α/√

t β1,t =t √

t (t +2)√t −1

ˆV 1/2t ˆV −1/2t −1

β′1,t =1t +2w t 定理 1　设是凸函数，，取

，，由式(5)生成，则

g t 至此，我们成功得到了Adam 算法在非光滑情况下的最优个体收敛速率，然而，批处理形式的Adam 算法每次迭代都使用全部样本计算次梯度，该操作对大规模机器学习问题显然是不可行的。为了解决该问题，将Adam 算法推广至随机形式。

S ={(x 1,y 1),(x 2,y 2),···,(x m ,y m )}∈R d ×{+1,−1}x

y (x i ,y i )f

i (w )=max(0,1−y i (w ,x i ))本文仅考虑二分类问题，假设

训练样本集

，其中和分别对应样本的特征向量和监督值，同时

之间满足独立同分布。并且只考虑最简

单的非光滑稀

疏学习问题“h i n g e 损失”，即

的目标函数为

约束情况下随机形式的Adam 算法迭代步骤

可以表示为

g t ∇f i (w )相对于批处理形式的次梯度，随机优化每

次只选择一个样本计算随机次梯度。由于“hinge 损失”次梯度的计算方式有很多种，这里选择文献[20]的方式：

A +

⊆S A +t

={(x i ,y i )⊆A t ;y i ⟨w ,x i ⟩<1}|A t |=1其中，，实验中选取。

随机Adam 算法：

w 1∈Q αt {αt >0}T t =11)初始化，定义步长为且；

2) for t =1 to T ；

i 3)等可能性选取；

∇f i (w t )4)根据式(7)计算随机次梯度；

β1,t =t √

t (t +2)√t −1

ˆV 1/2t ˆV −1/2t −1β′1,t =1t +25)取，；w t +16)由式(5)计算；

7) end for ；

w T 8)输出。

∇f i (w t )w t g t 因为样本点间满足独立同分布，所以计算得到的随机次梯度是损失函数在点处次梯度的无偏估计。应用文献[21]中将批处理算法收速率转化为随机算法收敛速率的技巧，可以得到定理2。

f (w )αt

=α/√

t β1,t =t √

t (t +2)√t −1

ˆV 1/2t ˆV −1/2t −1

β′1,t =1t +2w t 定理 2　设是凸函数，，取，，由随机Adam 由定理2可知，得到了随机Adam 算法在非光滑条件下的最优个体收敛速率。

3 实验

本节主要对随机Adam 算法的个体收敛速率的理论分析和稀疏性进行实验验证。

3.1 实验数据和比较算法

实验采用6个标准数据集，分别是ijcnn1、covtype 、a9a 、w8a 、CCAT 和astro-physic 。这些数据均来自于LIBSVM 网站，具体描述可见表1。

第 6 期黄鉴之，等：非光滑凸情形Adam 型算法的最优个体收敛速率·1143·

表 1 标准数据集描述

Table 1 Introduction of standard datasets

数据集训练样本数维数稀疏度/%ijcnn149 9902259.09covtype 522 9115422.12a9a 24 70312311.27w8a 49 749300 3.88CCAT 23 14947 2360.16astro-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.99Q l 1{w :∥w ∥1<z }z 步长。Heavy-ball 型动量法的计算方式及步长选取同文献[11]。NAG 型动量法的计算方式及步长选取同文献[10]。根据文献[15]，平均形式输出的Adam 算法步长。个体形式输出的Adam 算法步长设

置与迭代次数有关，其中。本

次实验我们调用SLEP 工具箱来实现投影计算，集合为范数球，根据数据集的不同，的取值也会有相应变化。

10−210−4图1为5种算法的收敛速率对比图，纵坐标表示当前目标函数值与最优目标函数值之差。其中绿、蓝、青、粉、红分别代表平均形式输出的SGD 算法、个体形式输出的Heavy-ball 型动量法、个体形式输出的NAG 型动量法、平均形式输出的Adam 算法、个体形式输出的Adam 算法。可以看到，在5 000步迭代之后，5种算法在6个标准数据集上都达到了的精度，在迭代10 000步后，5种算法在6个标准数据集上都达到了的精度。5种算法的收敛趋势基本相同，这与理论分析基本吻合。

(f) astro-physic

SGD-average