第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〉<1，实验中选 线优化时使用的迭代技巧。与文献[12]不同的 取Al=1。 是，本文需要处理自适应步长矩阵，而不是人为 随机Adam算法： 指定的步长，这里我们又借鉴Kingma在证明在 1)初始化w1∈Q,定义步长为a,且{a,>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⟩ < 1} |At |=1 其中 ， ，实验中选 取 。 随机 Adam 算法： w1 ∈ Q αt {αt > 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·