机器学习随机优化方法的个体收敛性研究综述

随机优化方法是求解大规模机器学习问题的主流方法,其研究的焦点问题是算法是否达到最优收敛速率与能否保证学习问题的结构。目前,正则化损失函数问题已得到了众多形式的随机优化算法,但绝大多数只是对迭代进行平均的输出方式讨论了收敛速率,甚至无法保证最为典型的稀疏结构。与之不同的是,个体解能很好保持稀疏性,其最优收敛速率已经作为open问题被广泛探索。另外,随机优化普遍采用的梯度无偏假设往往不成立,加速方法收敛界中的偏差在有偏情形下会随迭代累积,从而无法应用。本文对一阶随机梯度方法的研究现状及存在的问题进行综述,其中包括个体收敛速率、梯度有偏情形以及非凸优化问题,并在此基础上指出了一些值得研究的问题。

线性插值投影次梯度方法的最优个体收敛速率

投影次梯度算法(projected subgradient method,PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在对偶平均方法(dual averaging method,DAM)的迭代中嵌入一种线性插值操作,得到一种拟单调的求解非光滑问题的次梯度方法,并证明了在一般凸情形下具有个体最优收敛速率,但其讨论仅限于对偶平均方法.通过使用相同技巧,提出了一种嵌入线性插值操作的投影次梯度方法,与线性插值对偶平均方法不同的是,所提方法还对投影次梯度方法本身进行了适当的修改以确保个体收敛性.同时证明了该方法在一般凸情形下可以获得个体最优收敛速率,并进一步将所获结论推广至随机方法情形.实验验证了理论分析的正确性以及所提算法在保持实时稳定性方面的良好性能.

使用Nesterov步长策略投影次梯度方法的个体收敛性

很多机器学习问题都可以最终转换为优化问题来进行求解,凸优化算法已经被成功用于各种机器学习优化问题中,而在优化算法的研究中是否能获得最优的收敛速率是一个最基本问题.此外,稀疏性是稀疏学习问题中关注的另一个目标.目前,人们已经提出了大量的随机优化方法求解大规模机器学习优化问题,但大部分的研究只是针对平均输出方式获得了最优收敛速率.个体输出方式显然比平均方式的输出具有更好的稀疏性,但使个体收敛速率获得最优具有一定的难度,人们已经将强凸情形下的最优个体收敛性作为公开问题进行广泛研究.对于光滑目标函数的优化问题,著名学者Nesterov提出了一种步长策略,使得梯度方法的收敛速率获得了数量级形式的加速,并且获得了最优的个体收敛速率.目前,Nesterov加速算法已经应用于各种具有光滑损失函数机器学习优化问题中,研究者基于该加速策略提出了大量的随机优化算法.能否将这种技巧推广至非光滑情形获得最优的个体收敛速率显然是有意义的问题.文中考虑在非光滑优化算法中引入这种步长策略.特别地,我们聚焦经典的一阶梯度方法,提出了一种嵌入加速算法步长策略的投影次梯度算法,证明了这种算法在求解非光滑损失函数学习问题时具有最优的个体收敛速率.这是比标准投影次梯度方法只有在平均输出方式下才具有最优收敛速率更强的结论,也是一阶梯度方法在个体最优收敛速率方面比较接近于大家期待的研究成果.与平均方式输出以及线性插值的投影次梯度方法相比,该文所提方法的梯度运算在插值策略之后,因此在求解l1范数约束的hinge损失函数学习问题时具有更好的稀疏性.人工数据集上的实验验证了所提方法的正确性,基准数据集上验证了该方法在保持稀疏性方面具有良好的性能.

Heavy-Ball型动量方法的最优个体收敛速率

动量方法作为一种加速技巧被广泛用于提高一阶梯度优化算法的收敛速率.目前,大多数文献所讨论的动量方法仅限于Nesterov提出的加速方法,而对Polyak提出的Heavy-ball型动量方法的研究却较少.特别,在目标函数非光滑的情形下,Nesterov加速方法具有最优的个体收敛性,并在稀疏优化问题的求解中具有很好的效果.但对于Heavy-ball型动量方法,目前仅仅获得了平均输出形式的最优收敛速率,个体收敛是否具有最优性仍然未知.对于非光滑优化问题,通过巧妙地设置步长,证明了Heavy-ball型动量方法具有最优的个体收敛速率,从而说明了Heavy-ball型动量方法可以将投影次梯度方法的个体收敛速率加速至最优.作为应用,考虑了l1范数约束的hinge损失函数优化问题.通过与同类的优化算法相比,实验验证了该理论分析的正确性以及所提算法在保持稀疏性方面的良好性能.

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

Adam是目前深度神经网络训练中广泛采用的一种优化算法框架,同时使用了自适应步长和动量技巧,克服了SGD的一些固有缺陷。但即使对于凸优化问题,目前Adam也只是在线学习框架下给出了和梯度下降法一样的regret界,动量的加速特性并没有得到体现。这里针对非光滑凸优化问题,通过巧妙选取动量和步长参数,证明了Adam的改进型具有最优的个体收敛速率,从而说明了Adam同时具有自适应和加速的优点。通过求解l_(1)范数约束下的hinge损失问题,实验验证了理论分析的正确性和在算法保持稀疏性方面的良好性能。

基于AdaGrad的自适应NAG方法及其最优个体收敛性

与梯度下降法相比,自适应梯度下降方法(AdaGrad)利用过往平方梯度的算数平均保存了历史数据的几何信息,在处理稀疏数据时获得了更紧的收敛界.另一方面,Nesterov加速梯度方法(Nesterov’saccelerated gradient,NAG)在梯度下降法的基础上添加了动量运算,在求解光滑凸优化问题时具有数量级加速收敛的性能,在处理非光滑凸问题时也获得了最优的个体收敛速率.最近,已经出现了自适应策略与NAG相结合的研究,但现有代表性的自适应NAG方法AcceleGrad由于采取的自适应方式与AdaGrad不同,步长未能在不同维度上体现差异性,仅得到了加权平均方式的收敛速率,个体收敛速率的理论分析尚存在缺失.提出了一种自适应NAG方法,继承了AdaGrad的步长设置方式,证明了所提算法在解决约束非光滑凸优化问题时具有最优的个体收敛速率.在L1范数约束下,通过求解典型的hinge损失函数分类和L1损失函数回归优化问题.实验验证了理论分析的正确性,也表明了所提算法的性能优于AcceleGrad.

梯度有偏情形非光滑问题NAG的个体收敛性

随机优化方法已经成为处理大规模正则化和深度学习优化问题的首选方法,其收敛速率的获得通常都建立在目标函数梯度无偏估计的基础上,但对机器学习问题来说,很多现象都导致了梯度有偏情况的出现.与梯度无偏情形不同的是,著名的Nesterov加速算法NAG(Nesterov accelerated gradient)会逐步累积每次迭代中的梯度偏差,从而导致不能获得最优的收敛速率甚至收敛性都无法保证.近期的研究结果表明,NAG方法也是求解非光滑问题投影次梯度关于个体收敛的加速算法,但次梯度有偏对其影响的研究未见报道.针对非光滑优化问题,证明了在次梯度偏差有界的情况下,NAG能够获得稳定的个体收敛界,而当次梯度偏差按照一定速率衰减时,NAG仍然可获得最优的个体收敛速率.作为应用,得到了一种无需精确计算投影的投影次梯度方法,可以在保持收敛性的同时较快地达到稳定学习的精度.实验验证了理论分析的正确性及非精确方法的性能.

非光滑凸问题投影型对偶平均优化方法的个体收敛性

对于一般凸问题,对偶平均方法的收敛性分析需要在对偶空间进行转换,难以得到个体收敛性结果.对此,文中首先给出对偶平均方法的简单收敛性分析,证明对偶平均方法具有与梯度下降法相同的最优个体收敛速率Ο(ln t√t).不同于梯度下降法,讨论2种典型的步长策略,验证对偶平均方法在个体收敛分析中具有步长策略灵活的特性.进一步,将个体收敛结果推广至随机形式,确保对偶平均方法可有效处理大规模机器学习问题.最后,在L1范数约束的hinge损失问题上验证理论分析的正确性.

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

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

梯度有偏随机DA优化方法的个体收敛界分析

样本不满足独立同分布会使梯度估计在迭代过程中存在偏差,且最优的个体收敛界在噪声的干扰下无法确定。为此,提出一种线性插值随机对偶平均(DA)优化方法。给出DA方法收敛性的证明,在梯度估计有偏的基础上,求解得到一种线性插值DA随机优化方法不产生累积偏差的个体收敛界,以保证正则化损失函数结构下优化方法的个体收敛精度。实验结果表明,与随机加速方法相比,该方法具有较快的个体收敛速率与较高的收敛精度。

双阶段填充采样辅助的昂贵多目标优化

针对代理模型引导多目标优化算法,求解决策变量数量增多的昂贵多目标优化问题时,搜索效率较低的问题,提出一种双阶段填充采样辅助的昂贵多目标优化算法。第一阶段,利用一组方向向量引导产生靠近真实最优解集的样本,加快模型引导算法搜索;第二阶段,由代理模型估计获得估值误差,融合个体与样本之间相似性、个体估值收敛性,选择个体用于真实评价后填充样本集,实现模型性能的提升。在100维和200维的多目标基准测试问题上的实验结果表明,所提算法在同等有限资源内获得了比其它算法更为显著的优势。

基于AdaBelief的Heavy-Ball动量方法

同时使用动量和自适应步长技巧的自适应矩估计(Adaptive Moment Estimation,Adam)型算法广泛应用于深度学习中.针对此方法不能同时在理论和实验上达到最优这一问题,文中结合AdaBelief灵活调整步长提高实验性能的技巧,以及仅采用指数移动平均(Exponential Moving Average,EMA)策略调整步长的Heavy-Ball动量方法加速收敛的优点,提出基于AdaBelief的Heavy-Ball动量方法.借鉴AdaBelief和Heavy-Ball动量方法收敛性分析的技巧,巧妙选取时变步长、动量系数,并利用添加动量项和自适应矩阵的方法,证明文中方法对于非光滑一般凸优化问题具有最优的个体收敛速率.最后,在凸优化问题和深度神经网络上的实验验证理论分析的正确性,并且证实文中方法可在理论上达到最优收敛性的同时提高性能.

基于对偶平均的动量方法研究综述

对偶平均(dual averaging)方法是一种颇具潜力的优化算法,它巧妙地利用过往所有梯度的信息,克服了传统一阶梯度算法无法摆脱的梯度消失的弊端,并得到稳定的收敛速率。而恰恰类似的是,动量方法同样是利用过往的梯度信息,目的在于在非凸优化问题中能够有效地逃离局部最小点和鞍点,而今年来动量方法也广泛活跃在凸优化领域,不单对一般的梯度下降算法起到加速作用,同时在没有光滑性条件的情况下,得到最优个体收敛速率。论文对对偶平均方法和动量方法的研究现状和存在的问题进行综述,分析两者的联系和区别,并在此基础上指出一些值得研究的问题。