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

摘要：

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

关键词：机器学习、优化、随机梯度下降(SGD)、随机方差消减梯度法(SVRG)、分布式计算

所属期刊栏目：12

分类号：TP181(自动化基础理论)

资助基金：The National Natural Science Foundation of China under Grant No. U1435220;the Major Science and Technol-ogy Project of Beijing under Grant No. D171100003417002;the Civil Aviation Science and Technology Major Project under Grant No. MHRD20160109

在线出版日期：2018-08-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1047-1054