第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 (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]。 3) 本文选择了典型的 l1 范数约束下的 hinge 损失函数优化问题，通过与几种具有最优收敛速 率算法的比较，验证了理论的正确性和算法在保 持稀疏性方面的良好性能。 第 6 期 黄鉴之，等：非光滑凸情形 Adam 型算法的最优个体收敛速率 ·1141·