自适应策略下Heavy-Ball型动量法的最优个体收敛速率

引用本文

黄鉴之, 陇盛, 陶卿. 自适应策略下Heavy-Ball型动量法的最优个体收敛速率. 模式识别与人工智能, ,34(2): 137-145
HUANG Jianzhi, LONG Sheng, TAO Qing. Optimal Individual Convergence Rate of Heavy-Ball Based Momentum Methods Based on Adaptive Step-Size Strategy. PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, ,34(2): 137-145. 复制到剪切板

Doi: 10.16451/j.cnki.issn1003-6059.202102005
Permissions

《模式识别与人工智能》编辑部所有

自适应策略下Heavy-Ball型动量法的最优个体收敛速率

黄鉴之¹, 陇盛¹, 陶卿¹

1.中国人民解放军陆军炮兵防空兵学院信息工程系合肥 230031

通信作者：

陶卿,博士,教授,主要研究方向为模式识别、机器学习、应用数学.E-mail:qing.tao@ia.ac.cn.

作者简介:

黄鉴之,硕士研究生,主要研究方向为凸优化算法及在机器学习中的应用.E-mail:hjz18302840594@163.com.

陇盛,硕士研究生,主要研究方向为凸优化算法及在机器学习中的应用.E-mail:ls15186322349@163.com.

收稿日期: 2020-10-10 接受日期: 2020-11-23

资助项目: 国家自然科学基金项目(No.61673394,62076252)资助

摘要

同时使用自适应步长和动量两种优化技巧的AMSGrad在收敛性分析方面存在比自适应步长算法增加一个对数因子的问题.为了解决该问题,文中在非光滑凸情形下,巧妙选取动量和步长参数,证明自适应策略下Heavy-Ball型动量法具有最优的个体收敛速率,说明自适应策略下Heavy-Ball型动量法兼具动量的加速特性和自适应步长对超参数的低依赖性.求解 l₁范数约束下的Hinge损失问题,验证理论分析的正确性.

关键词: 自适应步长算法; 动量算法; AMSGrad; 个体收敛速率

中图分类号:TP 181

Optimal Individual Convergence Rate of Heavy-Ball Based Momentum Methods Based on Adaptive Step-Size Strategy

HUANG Jianzhi¹, LONG Sheng¹, TAO Qing¹

1.Department of Information Engineering, Chinese Academy of People's Liberation Army Artillery Air Defense Academy, Hefei 230031

Corresponding author:
TAO Qing, Ph.D., professor. His research interests include pa-ttern recognition, machine learning and applied mathematics.

AboutAuthor:
HUANG Jianzhi, master student. His research interests include convex optimization algorithm and its application in machine lear-ning.
LONG Sheng, master student. His research interests include convex optimization algorithm and its application in machine lear-ning.

Fund:Supported by National Natural Science Foundation of China(No.61673394,62076252)

Abstract

Optimization techniques, including adaptive step-size and momentum, are both utilized in AMSGrad. Compared with the adaptive step-size algorithms, there is one more logarithm factor in AMSGrad for convergence analysis. To solve the problem, the non-smooth convex problems are studied in this paper. By selecting the time-varying step-size and momentum parameters correctly, it is proved that the Heavy-ball-based momentum methods with adaptive step-size obtain the optimal individual convergence rate. It is indicated that the Heavy-ball-based momentum methods with adaptive step-size hold the advantages in both adaptation and acceleration. Hinge loss problem under L1-norm constraint is solved to verify the correctness of theoretical analysis.

Key words: Key Words Adaptive Step-Size Algorithm; Momentum Algorithm; AMSGrad; Individual Convergence Rate

文章图片

本文责任编委陈恩红

Recommended by Associate Editor CHEN Enhong

自适应步长和动量是目前深度学习中常用的两种优化技巧.自适应步长技巧利用数据稀疏的特性, 保留历史梯度信息, 降低算法对超参数的依赖性^[1].动量技巧可加速算法在求解凸问题时的收敛速率, 在处理非凸问题时可越过鞍点甚至局部极值点^[2].同时使用自适应步长和动量技巧的算法有Adam(Adaptive Moment Estimation)^[3]、Nadam(Nesterov Accelerated Adaptive Moment Estimation)^[4]、AMSGrad^[5]、AdamNC^[5]等.但是, 上述算法不论是自适应步长还是动量都是建立在指数移动平均的基础上, 给算法收敛性分析带来较大困难.

自适应步长方法利用优化过程中的历史梯度信息实现步长的动态调整.常见的自适应步长:1)Du- chi等^[1]在AdaGrad(Adaptive Gradient Algorithm中提出的算数平均型, 2)Zou等^[6]在RMSProp(Root Mean Square Propagation)中提出的指数移动平均(Exponential Moving Average, EMA)型.Mukkama- la等^[7]证明, 当EMA中衰减参数取特殊变值时, 可特化为算数平均.AdaGrad通过对过去所有梯度外积做和的方式实现步长自适应, 在一般凸的情况下, 可获得和梯度下降法一样O( $\sqrt[]{t}$ )的regret界, t表示迭代步数.AdaGrad最初主要用于求解正则化学习问题, 对于稀疏优化问题, 由于过往梯度能较好地反映数据稀疏特性, 可获得最优的依赖于数据的regret界.虽然AdaGrad在稀疏优化中具有一些优点, 但由于算法在自适应步长方面采用算数平均, 对历史梯度赋予相同的权重, 在深度学习应用中无法适应函数平滑性的局部变化.为了克服这一缺陷, RMSProp采用EMA形式修改AdaGrad外积累加方式, 丢弃相对遥远的梯度信息, 较好地适应函数平滑性的局部变化, 保证若干次迭代后算法还能继续进行.同时, RMSProp也获得依赖数据O( $\sqrt[]{t}$ )的regret界^[7].

动量法是在经典梯度下降法基础上添加动量项演变而来, 广泛用于提高一阶梯度算法的收敛速率.同时, 因为动量中隐含梯度的平均, 也被当作方差减速器使用^[8].近年来, 动量法广泛应用于深度神经网络训练, 根据动量项计算方式不同, 可将动量法分为2类:1)Polyak^[9]提出的Heavy-Ball型动量法, 2)Nesterov^[10]提出的NAG(Nesterov Accelerated Gradient)型动量法.两者的主要区别在于计算梯度的位置不同, Heavy-Ball型动量法在当前位置计算梯度, NAG型动量法会根据当前动量预估下次迭代可能到达的位置, 并在预估的位置计算梯度.动量法的加速特性主要体现在求解光滑凸问题时NAG型动量将梯度下降法O(1/t)的收敛速率加速至O(1/t²).当目标函数光滑强凸时, 动量法和梯度下降法均能达到线性收敛, 但动量法具有较小的收敛因子, 仍具有加速性^[11].

对于非光滑凸优化问题, 大多数算法都能获得O(1/ $\sqrt[]{t}$ )的最优收敛速率, 但这都是在平均输出方式下获得的.在个体收敛速率方面, 投影次梯度方法目前获得最好的收敛速率, 为O(lnt/ $\sqrt[]{t}$ )^[12].陶蔚等^[13]和Tao等^[14]将NAG步长策略引入投影次梯度中, 得到最优个体收敛速率O(1/ $\sqrt[]{t}$ ), 并保证良好的稀疏性.程禹嘉等^[15]证明Heavy-Ball型动量法具有O(1/ $\sqrt[]{t}$ )的最优个体收敛速率.由此可看出, 动量法对非光滑凸问题同样具有加速作用, 只不过体现在个体收敛速率上.从Heavy-ball型动量法加速个体速率的证明过程上看, 主要是借鉴Ghadimi等^[11]在光滑条件下Heavy-ball算法收敛速率的证明, 利用与梯度下降法之间的联系, 巧妙设置步长, 基于动量项递归得到个体收敛速率.

Kingma等^[3]结合EMA型自适应步长和EMA型动量, 提出Adam.Adam在深度学习中具有较优表现, 但因其使用EMA策略, 导致在算法收敛性分析方面困难较多.尽管Kingma等^[3]证明Adam算法在一般凸情形下能取得O( $\sqrt[]{t}$ )的regret界, 但Reddi等^[5]却对此结论提出质疑, 并提出AMSGrad和AdamNC这两个修正算法.相比Adam, AMSGrad在收敛性分析上增加一个对数因子^[16].从自适应算法的证明过程上看, 只要步长策略具有和投影次梯度方法在人为指定步长时的类似规律, 就能获得和梯度下降法相同的收敛速率.从动量法的证明过程来看, 非光滑凸情形下动量不影响投影次梯度法的平均收敛速率, 可加速个体收敛速率.因此为了解决AMSGrad收敛速率增加一个对数因子的问题, 本文主要研究自适应策略下Heavy-Ball型动量法的个体收敛速率问题.

基于上述分析, 本文在非光滑凸情形下借鉴光滑情形下Heavy-Ball型动量法的证明思路, 得到类似梯度下降法的迭代步骤, 同时使用Zinkevich^[17]在处理在线优化问题收敛性时使用的技巧, 处理变步长与权重导致的递归问题.巧妙选取时变步长和动量项前权重参数, 得到非光滑情形下的最优个体收敛速率O(1/ $\sqrt[]{t}$ ), 解决AMSGrad收敛速率增加一个对数因子的问题, 同时也说明自适应策略下Heavy-Ball型动量法兼具动量的加速特性和自适应步长对超参数的低依赖性.选择典型的l₁范数约束下的Hinge损失函数优化问题, 验证理论分析的正确性.

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

训练深度神经网络相当于解决如下约束优化问题:

$\min_{w \in Q}$ f(w), (1)

其中, f(w)为损失函数, 这里只考虑它为凸函数的情况, Q⊆Rⁿ为有界闭凸集.记w^*为式(1)的一个最优解.

1.1 梯度下降法

梯度下降法(Gradient Descent, GD)是解决问题(1)常用的算法之一, 迭代步骤如下:

w_t₊₁=w_t-α _tg_t.

其中:w_t表示第t次迭代后到达的位置; α _t为人工设置的衰减步长, 一般凸情形下取α _t=α / $\sqrt[]{t}$ , α > 0; g_t为函数f(w)在点w_t处的次梯度.

平均收敛速率是指f( ${\overset{̅}{w}}_{t}$ )-f(w^*)的收敛速率, 其中

${\overset{̅}{w}}_{t}$ = $\frac{1}{t} \overset{t}{\sum_{j = 1}}$ w_j.

与之对应, 个体收敛速率是指f(w_t)-f(w^*)的收敛速率.通常来说, 对于非光滑问题, 个体收敛更难获得最优速率.

Agarwal等^[18]证明非光滑一般凸情形下梯度下降可获得O(1/ $\sqrt[]{t}$ )的最优平均收敛速率, 即

f( ${\overset{̅}{w}}_{t}$ )-f(w^*)≤ O(1/ $\sqrt[]{t}$ ).

在小规模学习问题中, GD对各下降方向选取相同的步长可能会影响算法性能^[19].为了解决该问题, 自适应步长算法利用历史梯度信息实现动态调整各下降方向的步长.

1.2 自适应步长方法

AdaGrad和RMSProp的迭代步骤可统一写为

w_t₊₁=w_t-α _t $V_{t}^{- 1 / 2}$ g_t.(2)

其中:V_t为d× d维的自适应矩阵, 为对角矩阵;

α _t=α / $\sqrt[]{t}$ , α > 0.

显然, 按照GD的表示方式, 可将自适应步长方法的步长视为α _t $V_{t}^{- 1 / 2}$ .

AdaGrad中自适应矩阵V_t为过去所有梯度外积矩阵的算数平均:

V_t= $\frac{1}{t} \overset{t}{\sum_{j = 1}} g_{j}^{2}$ ,

其中, $g_{j}^{2}$ =diag(g_j ${g^{T}}_{j}$ ), 表示计算梯度g_j的外积再将其对角化.

AdaGrad的步长

α _t $V_{t}^{- 1 / 2}$ =α $(\overset{t}{\sum_{j = 1}} g_{j}^{2})^{- 1 / 2}$

为O(1/ $\sqrt[]{t}$ )阶.可看到, 因为梯度的累积, 算法在稀疏的维度上使用较大的步长, 在稠密的维度上使用较小的步长, 同时在一般凸情形下算法能获得

O( $\overset{d}{\sum_{i = 1}} {‖ g_{1 ∶ t, i} ‖}_{2}$ )

依赖于数据的regret界, 其中g_1:_t为{g₁, g₂, …, g_t}构成的d× t维矩阵, g_1:_t_,_i表示由矩阵g_1:_t第i行组成的向量.

RMSProp中自适应矩阵V_t为过去所有梯度外积矩阵的移动指数平均:

V_t=β _tV_t_-1+(1-β _t) $g_{t}^{2}$ , (3)

其中β _t∈ [0, 1), 一般情况下经验性地将β _t取0.9或0.99, 当β _t为常数时, 步长也为O(1/ $\sqrt[]{t}$ )阶.采用EMA形式计算自适应矩阵, 分配给过去梯度的权重会以指数衰减, 起主要作用的仅限于最近 $\frac{1}{1 - β_{t}}$ 个梯度.自适应矩阵V_t由递归得到, 也可将其改写为累加的形式:

V_t= $\overset{t}{\sum_{j = 1}}$ (1-β _j)( $\overset{t}{\prod_{k = j + 1}}$ β _k) $g_{j}^{2}$ .

当

β _t=1- $\frac{1}{t}$

时,

V_t= $\overset{t}{\sum_{j = 1}} \frac{1}{j}$ ( $\overset{t}{\prod_{k = j + 1}}$ ( $\frac{k - 1}{k}$ )) $g_{j}^{2}$ ,

整理可得

V_t= $\frac{1}{t} \overset{t}{\sum_{j = 1}} g_{j}^{2}$ .

这时EMA型自适应矩阵转化为算数平均型自适应矩阵.

由此可见, AdaGrad是RMSProp的一个特例.一般凸情形下, 当

1- $\frac{1}{t}$ ≤ β _t≤ 1- $\frac{γ}{t}$ , 0< γ ≤ 1, t≥ 1

时, RMSProp也能获得

O( $\overset{d}{\sum_{i = 1}} {‖ g_{1 ∶ t, i} ‖}_{2}$ )

依赖于数据的regret界^[7].

1.3 Heavy-ball型动量法和AMSGrad

与自适应步长法类似, Heavy-ball型动量法中动量也有2种计算形式:1)Polyak^[9]提出的以迭代前后两点位置之差为动量的传统Heavy-ball型动量法, 迭代步骤如下:

w_t₊₁=w_t-α _tg_t+μ _t(w_t-w_t_-1), (4)

其中, w_t-w_t_-1为动量, μ _t∈ [0, 1)为动量的衰减系数.2)利用历史梯度, 采用EMA形式计算动量, 迭代步骤如下:

m_t=μ _tm_t_-1+(1-μ _t)g_t,

w_t₊₁₌w_t_-α _tm_t,

其中m_t为动量.

AMSGrad同时使用EMA型自适应步长和EMA型动量, 迭代步骤如下:

m_t=μ _tm_t+(1-μ _t)g_t,

V_t=β _tV_t_-₁+(1-β _t) $g_{t}^{2}$

${\overset{︿}{V}}_{t}$ =max{ ${\overset{︿}{V}}_{t - 1}, V_{t}$ },

w_t₊₁=w_t-α _t ${\overset{︿}{V}}_{t}^{- 1 / 2}$ m_t (5)

一般凸情形下, AMSGrad只能获得

O( $\sqrt[]{\ln t} \overset{d}{\sum_{i = 1}} {‖ g_{1 ∶ t, i} ‖}_{2}$ )

的regret界, 这比单独使用自适应步长技巧的RMSProp增加一个对数因子.

从2种自适应步长法的式(2)可看出, 只要步长保持和梯度下降法一样的O(1/ $\sqrt[]{t}$ )阶, 就能获得和梯度下降法一样的收敛速率.程禹嘉等^[15]在动量法式(4)的基础上证明Heavy-Ball型动量法具有O(1/ $\sqrt[]{t}$ )的最优个体收敛速率.这2种技巧单独使用都能达到最优收敛速率, 结合本文式(2)中的自适应步长技巧与式(4)中的动量技巧, 提出自适应策略下Heavy-Ball型动量法, 解决AMSGrad无法取得最优收敛性的问题, 迭代形式如下:

w_t₊₁=w_t-α _t $V_{t}^{- \frac{1}{2}}$ g_t+μ _t(w_t-w_t_-1), (6)

其中自适应矩阵采用RMSProp中式(3)的形式.

2 个体收敛速率分析

根据输出方式的不同, 收敛速率分为平均收敛速率和个体收敛速率.通常来说, 对于非光滑问题, 个体收敛速率更难获得, 同时, 个体收敛速率可通过简单的累加变换为平均收敛速率, 更具有普适性.本节给出自适应策略下Heavy-Ball型动量法的个体最优收敛速率的证明.

因为AdaGrad是RMSProp的一个特例, 所以本节只考虑EMA型自适应矩阵.为了进行个体收敛性分析, 首先借鉴Ghadimi等^[11]在光滑条件下对式(4)的Heavy-ball算法收敛速率的证明, 引入加权动量项

p_t=t(w_t-w_t_-1).

巧妙选取梯度和动量前的时变参数, 可将式(6)的迭代步骤转化为

w_t₊₁+p_t₊₁=w_t+p_t- $\frac{α}{\sqrt[]{t}} V_{t}^{- 1 / 2}$ g_t.(7)

这个关系式和自适应步长法的关键迭代步骤相似, 正是由于这种相似性, 使自适应步长法的收敛性分析思路可用于自适应策略下Heavy-Ball型动量法.

受程禹嘉等^[15]的启发, 巧妙设计梯度和动量前的时变参数, 得到个体收敛速率的递归公式, 为了得到递归后个体收敛速率的界, 这里同样要使用Zinkevich^[17]在在线优化时使用的迭代技巧.与程禹嘉等^[15]不同的是, 文献[17]的迭代技巧需要处理自适应步长矩阵, 而不是人为指定的衰减步长.

基于式(7), 可证明定理1, 但为了解决变步长和权重导致的递归问题, 先证明引理1.

引理1 令

$D_{\infty}$ = $\underset{u \in Q}{\max_{w \in Q}} {‖ w - u ‖}_{\infty}$ ,

1- $\frac{1}{t}$ ≤ β _t≤ 1- $\frac{γ}{t}$ 0< γ ≤ 1, t≥ 1,

由式(6)生成w_t, 则

$\overset{t}{\sum_{j = 1}} \frac{\sqrt[]{j}}{α} {{‖ w_{j} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2} - {‖ w_{j + 1} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2}$ }+ $\overset{t}{\sum_{j = 1}} \frac{α}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2}$ ≤

$\frac{D_{\infty}^{2}}{α} \sqrt[]{t} \overset{d}{\sum_{i = 1}} V_{t, i}^{1 / 2}$ + $\frac{2 α (2 - γ)}{γ} \sqrt[]{t} \overset{d}{\sum_{i = 1}} V_{t, i}^{1 / 2}$ ≤ ( $\frac{D_{\infty}^{2}}{α}$ + $\frac{2 α (2 - γ)}{γ}$ ) $\overset{d}{\sum_{i = 1}} \sqrt[]{t} V_{t, i}^{1 / 2}$

证明根据文献[7]引理4.1可知,

$\overset{t}{\sum_{j = 1}} \frac{1}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2}$ ≤ $\frac{2 (2 - γ)}{γ} \sqrt[]{t} \overset{d}{\sum_{i = 1}} V_{t, i}^{1 / 2}$ .

使用Zinkevich^[17]在线优化时使用的迭代技巧进行整理:

$\overset{t}{\sum_{j = 1}} \frac{\sqrt[]{j}}{α} {{‖ w_{j} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2} - {‖ w_{j + 1} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2}} + \overset{t}{\sum_{j = 1}} \frac{α}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2} \leq$

$\frac{1}{α} \overset{t}{\sum_{j = 2}} {\sqrt[]{j} {‖ w_{j} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2} - \sqrt[]{j - 1} {‖ w_{j} - w^{*} ‖}_{V_{j - 1}^{1 / 2}}^{2}} + \frac{1}{α} {‖ w_{1} - w^{*} ‖}_{V_{1}^{1 / 2}}^{2} + \overset{t}{\sum_{j = 1}} \frac{α}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2} \leq$

$\frac{1}{α} \overset{t}{\sum_{j = 2}} \overset{d}{\sum_{i = 1}} {($ w_j_{, i}- $w_{, i}^{*})$ ² $(\sqrt[]{j} V_{j}^{1 / 2} - \sqrt[]{j - 1} V_{j - 1}^{1 / 2}} + \frac{1}{α} {‖ w_{1} - w^{*} ‖}_{V_{1}^{1 / 2}}^{2} + \overset{t}{\sum_{j = 1}} \frac{α}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2} \leq$

$\frac{1}{α} \overset{t}{\sum_{j = 2}} \overset{d}{\sum_{i = 1}}$ { $D_{\infty}^{2}$ ( $\sqrt[]{j} V_{j, i}^{1 / 2}$ - $\sqrt[]{j - 1} V_{j - 1, i}^{1 / 2}$ +)}+ $\frac{1}{α} \overset{d}{\sum_{i = 1}} {D_{\infty}^{2} V_{1, i}^{1 / 2}} + \overset{t}{\sum_{j = 1}} \frac{α}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2} \leq$

$\frac{D_{\infty}^{2}}{α} \sqrt[]{t} \overset{d}{\sum_{i = 1}} V_{t, i}^{1 / 2}$ + $\frac{2 α (2 - γ)}{γ} \sqrt[]{t} \overset{d}{\sum_{i = 1}} V_{t, i}^{1 / 2} =$

$(\frac{D_{\infty}^{2}}{α} + \frac{2 α (2 - γ)}{γ}) \overset{d}{\sum_{i = 1}} \sqrt[]{t} \overset{d}{\sum_{i = 1}} V_{t, i}^{1 / 2}$ .

定理1 设f(w)为一般凸函数, 取μ _t= $\frac{t}{t + 2}$ , α _t= $\frac{α}{\sqrt[]{t} (t + 2)}$ , w_t由式(5)生成, 则

f(w_t)-f(w^*)≤ $\frac{f (w_{0}) - f (w^{*})}{t + 1} + (\frac{D_{\infty}^{2}}{2 α (t + 1)} + \frac{α (2 - γ)}{γ (t + 1)} \overset{d}{) \sum_{i = 1}} \sqrt[]{t} V_{t, i}^{1 / 2}$ .

证明 w_t₊₁+P_t₊₁=w_t₊₁+(t+1)(w_t₊₁-w_t)=(t+2)w_t₊₁-(t+1)w_t=w_t+P_t- $\frac{α}{\sqrt[]{t}} V_{t}^{- 1 / 2}$ g_t,

${‖ w_{t + 1} + P_{t + 1} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} =$

${‖ w_{t} + P_{t} - \frac{α}{\sqrt[]{t}} V_{t}^{- 1 / 2} g_{t} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} =$

${‖ w_{t} + P_{t} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} + \frac{α^{2}}{t} {‖ g_{t} ‖}_{V_{t}^{- 1 / 2}}^{2}$ < w_t+P_t-_w* , $\frac{α}{\sqrt[]{t}} g_{t}$ > =

${‖ w_{t} + P_{t} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} + \frac{α^{2}}{t} {‖ g_{t} ‖}_{V_{t}^{- 1 / 2}}^{2} - <$ w_t-w_*, $\frac{α}{\sqrt[]{t}}$ g_t > -2_t< w_t-w_t-₁, $\frac{α}{\sqrt[]{t}} g t >$ ≤

${‖ w_{t} + p_{t} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} + \frac{α^{2}}{t} {‖ g_{t} ‖}_{V_{t}^{- 1 / 2}}^{2} - 2 \frac{α}{\sqrt[]{t}} (f (w_{t}) - f (w*)) - 2 \sqrt[]{t} a (f (w_{t}) - f (w_{t - 1}))$ ,

不等式两边同乘 $\frac{α}{\sqrt[]{t}}$ :

2(t+1)[f(w_t)-f(w^*)]≤

2t[f(w_t_-₁)-f(w* )]+ $\frac{\sqrt[]{t}}{α} {‖ w_{t} + P_{t} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} - \frac{\sqrt[]{t}}{α} {‖ w_{t + 1} + P_{t + 1} - w^{*} ‖}_{V_{t}^{1 / 2}}^{2} + \frac{α}{\sqrt[]{t}} {‖ g_{t} ‖}_{V_{t}^{- 1 / 2}}^{2}$

2(t+1)[f(w_t)-f(w* )]≤

2[f(w₀)-f(w* )]+ $\overset{t}{\sum_{j = 1}}$ ( $\frac{\sqrt[]{j}}{α} {‖ w_{k} + P_{k} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2} - \frac{\sqrt[]{j}}{α} {‖ w_{k + 1} + P_{k + 1} - w^{*} ‖}_{V_{j}^{1 / 2}}^{2}$ )+ $\overset{t}{\sum_{j = 1}} \frac{α}{\sqrt[]{j}} {‖ g_{j} ‖}_{V_{j}^{- 1 / 2}}^{2}$ .

根据引理1可得

2(t+1)[f(w_t)-f(w^*)]≤ 2[f(w₀)-f(w^*)]+ $(\frac{D_{\infty}^{2}}{α} + \frac{2 α (2 - γ)}{γ}) \overset{d}{\sum_{i = 1}} \sqrt[]{t} V_{t, i}^{1 / 2}$ ,

f(w_t)-f(w* )≤ $\frac{f (w_{0}) - f (w^{*})}{t + 1} + (\frac{D_{\infty}^{2}}{2 α (t + 1)} + \frac{α (2 - γ)}{γ (t + 1)}) \overset{d}{\sum_{i = 1}} \sqrt[]{t} V_{t, i}^{1 / 2}$

推论1 当

β _t=1- $\frac{1}{t}$

时, RMSProp转化为AdaGrad, 此时可得

$\sqrt[]{t} V_{t, i}^{1 / 2}$ = $\sqrt[]{\overset{t}{\sum_{j = 1}} g_{j, i}^{2}}$ = ${‖ g_{1 ∶ t, i} ‖}_{2}$ ,

f(w_t)-f(w^*)≤ $\frac{f (w_{0}) - f (w^{*})}{t + 1}$ +

$(\frac{D_{\infty}^{2}}{2 α (t + 1)} + \frac{α}{(t + 1)}$ ) $\overset{d}{\sum_{i = 1}} {‖ g_{1 ∶ t, i} ‖}_{2}$ .

取

α = $\frac{D_{\infty}}{\sqrt[]{2}}$ ,

可得

f(w_t)-f(w^*)≤ $\frac{f (w_{0}) - f (w^{*})}{t + 1}$ + $\frac{\sqrt[]{2} D_{\infty}}{t + 1} \overset{d}{\sum_{i = 1}} {‖ g_{1 ∶ t, i} ‖}_{2}$

到目前为止, 已证明自适应策略下Heavy-Ball型动量法的个体最优收敛速率.但是, 上述证明都是建立在批处理的基础上, 每次迭代都会遍历样本集用于计算次梯度.为了解决大规模学习问题下遍历样本集耗时、资源耗费过多的问题, 将自适应策略下Heavy-Ball型动量法推广至随机形式.

本文仅考虑二分类问题, 假设训练样本集

S={(x₁, y₁), (x₂, y₂), …, (x_m, y_m)}∈ R^d× {1, -1},

其中, x为样本的特征向量, y为监督值, 同时(x_i, y_i)之间满足独立同分布.只考虑最简单的非光滑稀疏学习问题“ hinge损失”

f_i(w)=max{0, 1-y_i(w, x_i)}

的目标函数:

$\min_{w \in Q} f (w) = \frac{1}{m} \overset{m}{\sum_{i = 1}}$ f_i(w).

有约束情况下随机形式的自适应策略下Heavy-Ball型动量法迭代步骤可表示为

w_t₊₁=P_Q(w_t-α _t $V_{t}^{- 1 / 2}$ g_t+μ _t(w_t-w_t_-1)). (8)

相对于批处理形式的次梯度g_t, 随机优化每次只选择一个样本计算随机次梯度▽f_i(w).由于“ hinge损失” 次梯度的计算方式有很多种, 这里选择文献[20]的方式:

▽f_i(w)= $\frac{1}{m} \sum_{(x_{i}, y_{i}) \in A_{t}^{+}}$ y_ix_i, (9)

其中

A_t⊆S, $A_{t}^{+}$ ={(x_i, y_i)∈ A_t:y_i< w, x_i> < 1},

实验中选取|A_t|=1.

随机自适应策略下Heavy-Ball型动量法具体步骤如下.

算法随机自适应策略下Heavy-Ball型动量法

输入循环次数T

输出 w_T

初始化向量w₀∈ Q

For t=1 to T

等可能性选取i=1, 2, …, m

根据式(9)计算随机次梯度▽f_i(w_t)

取μ _t= $\frac{t}{t + 2}$ , α _t= $\frac{α}{\sqrt[]{t} (t + 2)}$

由式(8)计算w_t₊₁

End For

因为样本点满足独立同分布, 所以随机次梯度Ñ f_i(w_t)为损失函数在点w_t处次梯度g_t的无偏估计.应用文献[21]中将批处理算法收敛速率转化为随机算法收敛速率的技巧, 可得到定理2.

定理2 设f(w)为一般凸函数, 取

μ _t= $\frac{t}{t + 2}$ , α _t= $\frac{α}{\sqrt[]{t} (t + 2)}$ ,

w_t由随机自适应策略下Heavy-Ball型动量法生成, 则

E[f(w_t)-f(w^*)]≤ $\frac{f (w_{0}) - f (w^{*})}{t + 1}$ +

$(\frac{D_{\infty}^{2}}{2 α (t + 1)} + \frac{α (2 - γ)}{γ (t + 1)}) \overset{d}{\sum_{i = 1}} \sqrt[]{t} V_{t, i}^{1 / 2}$

由定理2得到随机自适应策略下Heavy-Ball型动量法在非光滑条件下的最优个体收敛速率.

3 实验及结果分析

本节主要对随机自适应策略下Heavy-Ball型动量法个体收敛速率的理论分析进行实验验证.实验主要调用投影函数在l₁范数球上进行投影.作为拓展, 实验也可参考文献[22], 修改投影函数在 $l_{\infty}$ 范数球上进行投影.

实验环境为Windows10操作系统, 3.4 GHz CPU, Intel(R) core(TM)i7处理器, 内存16 GB, 软件环境为Matlab2016a.

实验一共采用ijcnn1、covtype、rcv1、CCAT这4个标准数据集.所有数据均来自于LIBSVM网站(https://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html), 数据集详细描述见表1.

表1 标准数据集 Table 1 Standard datasets

实验共对如下3种随机优化算法进行对比:个体形式输出的Heavy-ball型动量法(简记为Heavy-ball), 个体形式输出的NAG型动量法(简记为NAG), 个体形式输出的自适应策略下Heavy-Ball型动量法(简记为Heavy-ball+HB).从收敛速率角度分析, 上述3种算法都取得最优个体收敛速率.为了保证实验的公平性, 每种算法在对应数据集上运行10次, 每次迭代10 000步, 最后取10次运行的平均值作为输出.Heavy-ball型动量法迭代步骤为式(4), 步长选择取自文献[15], 其中

μ _t= $\frac{t}{t + 2}$ , α _t= $\frac{1}{\sqrt[]{t} (t + 2)}$ .

NAG型动量法的计算方式及步长选择取自文献[13]和文献[14], 迭代步骤如下:

y_t=w_t+θ _t( $θ_{t - 1}^{- 1}$ -1)(w_t-w_t_-1),

w_t₊₁=y_t-η _t▽f(y_t),

其中,

θ _t= $\frac{2}{t + 2}$ , η _t= $\frac{1}{(t + 2) \sqrt[]{t + 2}}$ .

自适应策略下Heavy-Ball型动量法计算方式为式(8), 步长设置与迭代次数有关, 其中,

μ _t= $\frac{t}{t + 2}$ , α _t= $\frac{α}{\sqrt[]{t} (t + 2)}$ , α =0.1.

本次实验调用SLEP工具箱实现投影计算, 集合Q为l₁范数球{w: ${‖ w ‖}_{1} < z}$ , 根据数据集的不同, z的取值也会有相应变化.

图1为3种算法在4个数据集上的收敛速率, 纵坐标表示当前目标函数值与最优目标函数值之差.

	Figure Option View Download New Window
	图1 各算法在4个数据集上的收敛速率对比Fig.1 Convergence rate comparison of different algorithms on 4 datasets

由图1可看到:经过5 000次迭代后, 3种算法的精度都趋于稳定; 经过10 000次迭代后, 3种算法都到10^-5的精度.观察到算法在稀疏度一般的ijcnn1、covtype数据集上有震荡的现象, 这是算法随机性导致的.在维度较大、稀疏度更低的rcv1、CCAT数据集上算法震荡现象消失.3种算法的收敛趋势基本相同, 这与理论分析基本吻合.

4 结束语

本文初步研究非光滑条件自适应策略下Heavy-Ball型动量法, 证明其可得到最优的个体收敛速率.该结论解决AMSGrad收敛速率增加一个对数因子的问题, 同时表明, 在最坏情况下, 自适应策略下Heavy-Ball型动量法具有和Heavy-Ball型动量法相同的收敛速率.在数据稀疏的情况下, 保留自适应步长算法收敛速率依赖数据的特性, 获得的个体收敛速率比单纯使用动量法更快.今后, 将继续研究强凸情形自适应策略下Heavy-Ball型动量法的个体收敛问题.

参考文献

文献选项

[1]	DUCHI J, HAZAN E, SINGER Y. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. Journal of Machine Learning Research, 2011, 12: 2121-2159. [本文引用:2]
[2]	SUN T, LI D S, QUAN Z, et al. Heavy-Ball Algorithms always Escape Saddle Points // Proc of the 28th International Joint Conference on Artificial Intelligence. New York, USA: ACM, 2019: 3520-3526. [本文引用:1]
[3]	KINGMA D P, BA J. Adam: A Method for Stochastic Optimization[C/OL]. [2020-09-29]. http://de.arxiv.org/pdf/1412.6980. [本文引用:3]
[4]	DOZAT T. Incorporating Nesterov Momentum into Adam[C/OL]. [2020-09-29]. http://cs229.stanford.edu/proj2015/054_report.pdf. [本文引用:1]
[5]	REDDI S J, KALE S, KUMAR S. On the Convergence of Adam and Beyond[C/OL]. [2020-09-29]. https://arxiv.org/abs/1904.09237. [本文引用:3]
[6]	ZOU F Y, SHEN L, JIE Z Q, et al. A Sufficient Condition for Convergences of Adam and RMSProp // Proc of the IEEE/CVF Confe-rence on Computer Vision and Pattern Recognition. Washington, USA: IEEE, 2019: 11119-11127. [本文引用:1]
[7]	MUKKAMALA M C, HEIN M. Variants of RMSProp and Adagrad with Logarithmic Regret Bounds // Proc of the 34th International Conference on Machine Learning. New York, USA: ACM, 2017: 2545-2553. [本文引用:4]
[8]	MA J, YARATS D. Quasi-Hyperbolic Momentum and Adam for Deep Learning // Proc of the 7th International Conference for Learning Representations[C/OL]. [2020-09-29]. https://arxiv.org/pdf/1810.06801.pdf. [本文引用:1]
[9]	POLYAK B T. Some Methods of Speeding up the Convergence of Iteration Methods. USSR Computational Mathematics and Mathematical Physics, 1964, 4(5): 1-17. [本文引用:2]
[10]	NESTEROV Y. A Method of Solving a Convex Programming Problem with Convergence Rate O(1 /k²). Soviet Mathematics Doklady, 1983, 27(2): 372-376. [本文引用:1]
[11]	GHADIMI E, FEYZMAHDAVIAN H R, JOHANSSON M. Global Convergence of the Heavy-Ball Method for Convex Optimization // Proc of the European Control Conference. Washington, USA: IEEE, 2015: 310-315. [本文引用:3]
[12]	SHAMIR O, ZHANG T. Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes // Proc of the 30th International Conference on Machine Learning. New York, USA: ACM, 2013: I-71-I-79. [本文引用:1]
[13]	陶蔚, 潘志松, 储德军, 等. 使用Nesterov步长策略投影次梯度方法的个体收敛性. 计算机学报, 2018, 41(1): 164-176. (TAO W, PAN Z S, CHU D J, et al. The Individual Convergence of Projected Subgradient Methods Using the Nesterov's Step-Size Strategy. Chinese Journal of Computers, 2018, 41(1): 164-176. ) [本文引用:2]
[14]	TAO W, PAN Z S, WU G W, et al. The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization. IEEE Transactions on Neural Networks and Learning Systems, 2020, 31(7): 2557-2568. [本文引用:2]
[15]	程禹嘉, 陶蔚, 刘宇翔, 等. Heavy-Ball型动量方法的最优个体收敛速率. 计算机研究与发展, 2019, 56(8): 1686-1694. (CHENG Y J, TAO W, LIU Y X, et al. Optimal Individual Convergence Rate of the Heavy-Ball-Based Momentum Methods. Journal of Computer Research and Development, 2019, 56(8): 1686-1694. ) [本文引用:5]
[16]	ALACAOGLU A, MALITSKY Y, MERTIKOPOULOS P, et al. A New Regret Analysis for Adam-Type Algorithms[C/OL]. [2020-09-29]. https://arxiv.org/pdf/2003.09729v1.pdf. [本文引用:1]
[17]	ZINKEVICH M. Online Convex Programming and Generalized Infinitesimal Gradient Ascent // Proc of the 20th International Conference on Machine Learning. New York, USA: ACM, 2003: 928-936. [本文引用:4]
[18]	AGARWAL A, BARTLETT P, RAVIKUMAR P, et al. Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization. IEEE Transactions on Information Theory, 2012, 58(5): 3235-3249. [本文引用:1]
[19]	KESKAR N S, SOCHER R. Improving Generalization Performance by Switching from Adam to SGD[C/OL]. [2020-09-29]. https://arxiv.org/pdf/1712.07628.pdf. [本文引用:1]
[20]	SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos: Primal Estimated Sub-gradient Solver for SVM // Proc of the 24th International Conference on Machine Learning. New York, USA: ACM, 2007: 807-814 [本文引用:1]
[21]	RAKHLINA, SHAMIR O, SRIDHARAN K. Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization // Proc of the 29th International Conference on Machine Learning. New York, USA: ACM, 2012: 1571-1578. [本文引用:1]
[22]	TAO Q, WU G W, CHU D J. Improving Sparsity and Scalability in Regularized Nonconvex Truncated-Loss Learning Problems. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(7): 2782-2793. [本文引用:1]

2011

0.0

... 自适应步长技巧利用数据稀疏的特性,保留历史梯度信息,降低算法对超参数的依赖性^[1] ...

... 常见的自适应步长:1)Du- chi等^[1]在AdaGrad(Adaptive Gradient Algorithm中提出的算数平均型,2)Zou等^[6]在RMSProp(Root Mean Square Propagation)中提出的指数移动平均(Exponential Moving Average, EMA)型 ...

2019

0.0

... 动量技巧可加速算法在求解凸问题时的收敛速率,在处理非凸问题时可越过鞍点甚至局部极值点^[2] ...

2020

0.0

... 同时使用自适应步长和动量技巧的算法有Adam(Adaptive Moment Estimation)^[3]、Nadam(Nesterov Accelerated Adaptive Moment Estimation)^[4]、AMSGrad^[5]、AdamNC^[5]等 ...

... Kingma等^[3]结合EMA型自适应步长和EMA型动量,提出Adam ...

... 尽管Kingma等^[3]证明Adam算法在一般凸情形下能取得O( t　)的regret界,但Reddi等^[5]却对此结论提出质疑,并提出AMSGrad和AdamNC这两个修正算法 ...

2020

0.0

... 同时使用自适应步长和动量技巧的算法有Adam(Adaptive Moment Estimation)^[3]、Nadam(Nesterov Accelerated Adaptive Moment Estimation)^[4]、AMSGrad^[5]、AdamNC^[5]等 ...

0.0

... 同时使用自适应步长和动量技巧的算法有Adam(Adaptive Moment Estimation)^[3]、Nadam(Nesterov Accelerated Adaptive Moment Estimation)^[4]、AMSGrad^[5]、AdamNC^[5]等 ...

... 尽管Kingma等^[3]证明Adam算法在一般凸情形下能取得O( t　)的regret界,但Reddi等^[5]却对此结论提出质疑,并提出AMSGrad和AdamNC这两个修正算法 ...

2019

0.0

2017

0.0

... Mukkama- la等^[7]证明,当EMA中衰减参数取特殊变值时,可特化为算数平均 ...

... 同时,RMSProp也获得依赖数据O( t)的regret界^[7] ...

... 依赖于数据的regret界^[7] ...

... 证明根据文献[7]引理4 ...

0.0

... 同时,因为动量中隐含梯度的平均,也被当作方差减速器使用^[8] ...

1964

0.0

... 近年来,动量法广泛应用于深度神经网络训练,根据动量项计算方式不同,可将动量法分为2类:1)Polyak^[9]提出的Heavy-Ball型动量法,2)Nesterov^[10]提出的NAG(Nesterov Accelerated Gradient)型动量法 ...

... 3 Heavy-ball型动量法和AMSGrad与自适应步长法类似,Heavy-ball型动量法中动量也有2种计算形式:1)Polyak^[9]提出的以迭代前后两点位置之差为动量的传统Heavy-ball型动量法,迭代步骤如下: ...

1983

0.0

2015

0.0

... 当目标函数光滑强凸时,动量法和梯度下降法均能达到线性收敛,但动量法具有较小的收敛因子,仍具有加速性^[11] ...

... 从Heavy-ball型动量法加速个体速率的证明过程上看,主要是借鉴Ghadimi等^[11]在光滑条件下Heavy-ball算法收敛速率的证明,利用与梯度下降法之间的联系,巧妙设置步长,基于动量项递归得到个体收敛速率 ...

... 为了进行个体收敛性分析,首先借鉴Ghadimi等^[11]在光滑条件下对式(4)的Heavy-ball算法收敛速率的证明,引入加权动量项 ...

2013

0.0

... 在个体收敛速率方面,投影次梯度方法目前获得最好的收敛速率,为O(lnt/t)^[12] ...

2018

0.0

陶蔚, 潘志松, 储德军, 等. 使用Nesterov步长策略投影次梯度方法的个体收敛性. 计算机学报, 2018, 41(1): 164-176.

(TAO

, PAN Z

, CHU D

, et al. The Individual Convergence of Projected Subgradient Methods Using the Nesterov's Step-Size Strategy. Chinese Journal of Computers, 2018, 41(1): 164-176. )

... 陶蔚等^[13]和Tao等^[14]将NAG步长策略引入投影次梯度中,得到最优个体收敛速率O(1/t),并保证良好的稀疏性 ...

... NAG型动量法的计算方式及步长选择取自文献[13]和文献[14],迭代步骤如下: ...

2020

0.0

... 陶蔚等^[13]和Tao等^[14]将NAG步长策略引入投影次梯度中,得到最优个体收敛速率O(1/t),并保证良好的稀疏性 ...

... NAG型动量法的计算方式及步长选择取自文献[13]和文献[14],迭代步骤如下: ...

2019

0.0

程禹嘉, 陶蔚, 刘宇翔, 等. Heavy-Ball型动量方法的最优个体收敛速率. 计算机研究与发展, 2019, 56(8): 1686-1694.

(CHENG Y

, TAO

, LIU Y

, et al. Optimal Individual Convergence Rate of the Heavy-Ball-Based Momentum Methods. Journal of Computer Research and Development, 2019, 56(8): 1686-1694. )

... 程禹嘉等^[15]证明Heavy-Ball型动量法具有O(1/t)的最优个体收敛速率 ...

... 程禹嘉等^[15]在动量法式(4)的基础上证明Heavy-Ball型动量法具有O(1/t)的最优个体收敛速率 ...

... 受程禹嘉等^[15]的启发,巧妙设计梯度和动量前的时变参数,得到个体收敛速率的递归公式,为了得到递归后个体收敛速率的界,这里同样要使用Zinkevich^[17]在在线优化时使用的迭代技巧 ...

... 与程禹嘉等^[15]不同的是,文献[17]的迭代技巧需要处理自适应步长矩阵,而不是人为指定的衰减步长 ...

... Heavy-ball型动量法迭代步骤为式(4),步长选择取自文献[15],其中 ...

0.0

... 相比Adam,AMSGrad在收敛性分析上增加一个对数因子^[16] ...

2003

0.0

... 基于上述分析,本文在非光滑凸情形下借鉴光滑情形下Heavy-Ball型动量法的证明思路,得到类似梯度下降法的迭代步骤,同时使用Zinkevich^[17]在处理在线优化问题收敛性时使用的技巧,处理变步长与权重导致的递归问题 ...

... 与程禹嘉等^[15]不同的是,文献[17]的迭代技巧需要处理自适应步长矩阵,而不是人为指定的衰减步长 ...

... 使用Zinkevich^[17]在线优化时使用的迭代技巧进行整理: ...

2012

0.0

... Agarwal等^[18]证明非光滑一般凸情形下梯度下降可获得O(1/t)的最优平均收敛速率,即 ...

0.0

... 在小规模学习问题中,GD对各下降方向选取相同的步长可能会影响算法性能^[19] ...

2007

0.0

... 次梯度的计算方式有很多种,这里选择文献[20]的方式: ...

2012

0.0

... 应用文献[21]中将批处理算法收敛速率转化为随机算法收敛速率的技巧,可得到定理2 ...

2018

0.0

... 作为拓展,实验也可参考文献[22],修改投影函数在 l∞范数球上进行投影 ...