分布式随机方差消减梯度下降算法topkSVRG

机器学习问题通常会转换成一个目标函数进行求解,优化算法是求解目标函数中参数的重要工具。随机梯度下降(stochastic gradient descent,SGD)是目前应用最广的算法,因其易受噪声干扰只能达到次线性收敛率,而改进后的随机方差消减梯度法(stochastic variance reduction gradient,SVRG)则可以达到线性的收敛率。SVRG是一种串行单机版算法,为了应对大规模数据集分布式训练问题,设计一种以SVRG算法思想为基础的分布式SVRG的实现算法topk SVRG。改进在于:主节点维护一个全局模型,从节点基于本地数据进行局部模型更新。每轮迭代时,选择与当前全局模型距离最小的k个局部模型进行平均来更新全局模型,参数k调大可以提高收敛速度,调小k可以保证收敛。理论分析了算法的线性收敛性,基于Spark进行算法实现,通过与Mini-Batch SGD、CoCoA、Splash及相关算法的实验比较,topkSVRG可以在高精度要求下更快地收敛。

求解SVM的稀疏随机方差缩减梯度法

针对随机梯度下降(SGD)算法解支持向量机(SVM)中存在步长的选取耗时且收敛速度较慢等问题,提出使用改进的Barzilai-Borwein(BB)法自动计算小批量随机方差减小的梯度法(MSVRG)的步长,来解决光滑化合页损失函数的支持向量机问题。针对高维稀疏数据下,SVRG在外循环的迭代中因全梯度的计算而变得稠密,使用稀疏近似梯度将MSVRG-BB算法拓展得到新的算法:MSSVRG-BB。数值实验表明,MSSVRG-BB算法不仅对初始参数的选取并不敏感,且与先进的小批量算法相比,对于求解大规模高维稀疏数据的线性SVM问题,稀疏近似梯度的使用使运算成本减小进而能够更快地达到收敛上界。

批量减数更新方差缩减梯度下降算法BSUG

机器学习问题通常会转换成求解一个目标函数问题。继随机梯度下降(Stochastic Gradient Descent,SGD)之后,随机方差缩减梯度法(Stochastic Variance Reduction Gradient,SVRG)成为如今优化目标函数参数的主流算法,它由于不受方差影响达到线性收敛而被人们广泛研究。它的提出导致陆续出现如SAGA(Stochastic Average Gradient Average)和SCSG(Stochastically Controlled Stochastic Gradient)等新型方差缩减算法,它们有着过量消耗内存、迭代缓慢等问题。为了实现小成本存储以及快速迭代的目的,设计了一种以SVRG为基础的新型变异方差缩减算法BSUG(Batch Subtraction Update Gradient)。改进在于:使用小批量样本代替全部样本进行平均梯度计算,同时对平均梯度进行减数更新。每轮迭代中,随机抽取一批小样本进行平均梯度计算,同时在内部迭代时通过对过去模型梯度的舍去来达到更新平均梯度的目的。通过合适地降低批大小B,可以减少内存存储以及迭代次数。理论分析算法的收敛性,并基于Python进行算法实现,通过与Mini-Batch SGD、AdaGrad、RMSProp、SVRG和SCSG等算法进行比较证明了BSUG算法的有效性,并且通过对超参数进行探究证明了算法的稳定性。