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

来源：计算机科学与探索杂志2018年第7期北京时间：

作者：王建飞，亢良伊，刘杰，叶丹

单位：1. 中国科学院 软件研究所 软件工程技术研发中心，北京 1001902. 中国科学院大学，北京 100190

摘要：机器学习问题通常会转换成一个目标函数进行求解，优化算法是求解目标函数中参数的重要工具。随机梯度下降（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）,分布式计算