引用本文

史加荣, 王丹, 尚凡华, 张鹤于. 随机梯度下降算法研究进展. 自动化学报, 2021, 47(9): 2103−2119 doi: 10.16383/j.aas.c190260

Shi Jia-Rong, Wang Dan, Shang Fan-Hua, Zhang He-Yu. Research advances on stochastic gradient descent algorithms. Acta Automatica Sinica, 2021, 47(9): 2103−2119 doi: 10.16383/j.aas.c190260

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190260

关键词

随机梯度下降算法，机器学习，深度学习，梯度下降算法，大规模学习，逻辑回归，卷积神经网络

摘要

在机器学习领域中, 梯度下降算法是求解最优化问题最重要、最基础的方法. 随着数据规模的不断扩大, 传统的梯度下降算法已不能有效地解决大规模机器学习问题. 随机梯度下降算法在迭代过程中随机选择一个或几个样本的梯度来替代总体梯度, 以达到降低计算复杂度的目的. 近年来, 随机梯度下降算法已成为机器学习特别是深度学习研究的焦点. 随着对搜索方向和步长的不断探索, 涌现出随机梯度下降算法的众多改进版本, 本文对这些算法的主要研究进展进行了综述. 将随机梯度下降算法的改进策略大致分为动量、方差缩减、增量梯度和自适应学习率等四种. 其中, 前三种主要是校正梯度或搜索方向, 第四种对参数变量的不同分量自适应地设计步长. 着重介绍了各种策略下随机梯度下降算法的核心思想、原理, 探讨了不同算法之间的区别与联系. 将主要的随机梯度下降算法应用到逻辑回归和深度卷积神经网络等机器学习任务中, 并定量地比较了这些算法的实际性能. 文末总结了本文的主要研究工作, 并展望了随机梯度下降算法的未来发展方向.

文章导读

作为人工智能目前最活跃的一个研究分支, 机器学习根据经验数据来设计、开发算法, 其目的是探索数据的生成模式, 并用来发现模式和进行预测[1-2]. 深度学习是一类更广的机器学习方法, 允许由多个处理层组成的计算模型来学习具有多个抽象级别的数据表示[3]. 伴随着深度学习的崛起, 机器学习重新受到了学术界和工业界的广泛关注. 机器学习技术已广泛地应用在计算机视觉、推荐系统、语音识别和数据挖掘等领域中.

回归与分类等监督学习是机器学习中最常见的一类学习问题, 它提供了包含输入数据和目标数据的训练数据集. 为了探讨输入与目标之间的关系, 需要先建立含参数的表示模型, 再通过最小化所有样本的平均损失函数来获得最优的参数, 此处的优化模型通常为经验风险最小化(Empirical risk minimization, ERM)[4]. 梯度下降法是求解ERM模型最常用的方法, 也是二阶方法和黎曼优化的重要基础. 传统的梯度下降法在计算目标函数的梯度时, 需计算每个样本对应的梯度, 总计算复杂度线性地依赖于样本数目. 随着数据规模的日益增大, 求解所有样本的梯度需要相当大的计算量, 因而传统的梯度下降算法在解决大规模机器学习问题时往往不再奏效[5].

随机梯度下降算法(Stochastic gradient descent, SGD)源于1951年Robbins和Monro[6]提出的随机逼近, 最初应用于模式识别[7]和神经网络[8]. 这种方法在迭代过程中随机选择一个或几个样本的梯度来替代总体梯度, 从而大大降低了计算复杂度. 1958年Rosenblatt等研制出的感知机采用了随机梯度下降法的思想, 即每轮随机选取一个误分类样本, 求其对应损失函数的梯度, 再基于给定的步长更新参数[9]. 1986年Rumelhart等分析了多层神经网络的误差反向传播算法, 该算法每次按顺序或随机选取一个样本来更新参数, 它实际上是小批量梯度下降法的一个特例[9]. 近年来, 随着深度学习的迅速兴起, 随机梯度下降算法已成为求解大规模机器学习优化问题的一类主流且非常有效的方法. 目前, 随机梯度下降算法除了求解逻辑回归、岭回归、Lasso、支持向量机[10]和神经网络等传统的监督机器学习任务外, 还成功地应用于深度神经网络[11-12]、主成分分析[13-14]、奇异值分解[13, 15]、典型相关分析[16]、矩阵分解与补全[17-18]、分组最小角回归[19-20]、稀疏学习和编码[21-22]、相位恢复[23] 以及条件随机场[24]等其他机器学习任务.

随着大数据的不断普及和对优化算法的深入研究, 衍生出随机梯度下降算法的许多不同版本. 这些改进算法在传统的随机梯度下降算法的基础上引入了许多新思想, 从多个方面不同程度地提升了算法性能. 搜索方向的选取和步长的确定是梯度下降算法研究的核心. 按照搜索方向和步长选取的方式不同, 将随机梯度下降算法的改进策略大致分为动量、方差缩减、增量梯度和自适应学习率等四种类型. 其中, 前三类方法主要是校正梯度或搜索方向, 适用于逻辑回归、岭回归等凸优化问题; 第四类方法针对参数变量的不同分量自适应地设置步长, 适用于深度神经网络等非凸优化问题.

在传统梯度下降算法的基础上添加动量项可以有效避免振荡, 加速逼近最优解. 采用动量更新策略的方法主要包括经典动量算法(Classical momentum, CM)[25] 和Nesterov加速梯度算法(Nesterov＇ s accelerated gradient, NAG)[26-27]. 简单版本的随机梯度下降算法在随机取样的过程中产生了方差并且随着迭代次数的增加而不断累加, 无法保证达到线性收敛. 为此, 研究者们相继提出了一系列基于方差缩减的随机梯度下降算法, 主要包括随机方差缩减梯度算法(Stochastic variance reduced gradient, SVRG)[28]、近端随机方差缩减梯度算法(Proximal stochastic variance reduction gradient, Prox-SVRG)[29]、Katyusha[30] 和MiG[31] 等. 前述方法没有充分利用历史梯度信息, 而增量梯度策略通过“以新梯度替代旧梯度”的方式, 充分考虑了历史梯度且达到了减少梯度计算量的目的, 该类型的主要算法包括随机平均梯度算法(Stochastic average gradient, SAG)[32]、SAGA[33] 和Point-SAGA[34]. Allen-Zhu[30]根据算法在强凸条件下的复杂度将前三类随机梯度下降算法分为三代, 复杂度随代数的增加而降低. 在深度神经网络中, 自适应学习率的随机梯度下降法通过使用反向传播所计算出的梯度来更新参数[35]. 与前三类算法不同, 自适应算法在训练过程中会根据历史梯度信息, 针对参数的不同分量自动调整其对应的学习率. 这类算法主要包括Adagrad[36]、Adadelta[37]、Adam (Adaptive moment estimation)[38]和Nadam (Nesterov-accelerated adaptive moment estimation)[39]等.

目前, 各种版本的随机梯度下降算法大多以黑箱优化器的形式在TensorFlow、PyTorch和MxNet等各大主流平台供用户调用, 但背后的算法原理却鲜为人知. 2017年Ruder在文献[40]中介绍了几种深度学习领域中的随机梯度下降算法, 但缺乏一些最新的研究成果、算法之间的联系以及实际数据集上的实验对比. 国内学者提出过一些随机梯度下降算法的改进策略, 但尚未有人发表过此方向的综述性论文. 因此, 本文的工作对于关注梯度下降算法理论及其在深度学习中应用的研究者具有参考意义. 本文针对随机梯度下降算法展开研究, 讨论了动量、方差缩减、增量梯度和自适应学习率等四类更新策略下主要算法的核心思想、迭代公式以及算法之间的区别与联系. 对于逻辑回归、岭回归、Lasso和深度神经网络等机器学习任务, 设计了相应的数值实验, 并对比了几种具有代表性的随机梯度下降算法的性能. 文末对研究工作进行了总结, 并展望了随机梯度下降算法面临的挑战与未来的发展方向.

图 1  条件数对收敛速度的影响

图 3  SGD、CM和NAG的参数更新示意图

图 4  学习率对优化过程的影响

本文对近年来随机梯度下降算法的研究进展及主要研究成果进行了综述. 根据算法的更新策略, 将几种具有代表性的随机梯度下降算法分为四类, 包括基于动量的算法、基于方差缩减的算法、基于增量梯度的算法以及自适应学习率的算法. 本文介绍了这些算法的原理、核心思想以及相互之间的区别与联系, 并通过数值实验对算法的实际性能进行了对比. 实验结果表明: 在逻辑回归等经典机器学习任务中, Katyusha和MiG等第3代算法普遍具有较好的性能, 而SGD和NAG等第1代算法的实验性能最差; 在深度卷积神经网络中, Adam的实验性能最好. 当前, 国内外提出的随机梯度下降算法种类繁多, 但理论不完善且评价标准尚未统一. 因此, 随机梯度下降算法仍将是未来的研究热点. 下面几个方向在今后的研究中值得关注.

1)与二阶算法相比, 随机梯度下降算法的收敛速度相对较慢, 且需要更多的迭代次数. 第2代和第3代改进算法虽然有效地提升了收敛速度, 但耗费了较大的时间成本和内存成本. 随着数据规模的扩大和模型复杂度的提升, 单线程下的随机梯度下降算法已经不能满足大规模机器学习应用的需求[72-73]. Zinkevich等[74]提出了首个并行式随机梯度下降算法SimuParallelSGD, 这种方法适合于大规模学习范式和MapReduce框架. 文献[75]提出了Hogwild!! 算法, 它对稀疏数据采用无锁异步更新策略, 从而有效地减少了特征更新时的冲突. 陈振宏等[76]提出了一种基于差异合并的分布式随机梯度下降算法DA-DSGD, 从性能的加权合并、模型规范化两方面提高了算法性能. 目前, 研究者们已经实现了SVRG、SAGA和MiG等改进算法的分布式和并行化版本, 但收敛速度却有待进一步提升[31, 77-78]. 如何根据算法特点、数据对象和应用平台, 设计并实现不同改进策略下的随机梯度下降算法的分布式与并行化版本, 使其在实际应用中发挥出较高的性能水平, 这是未来值得探索的问题.

2)学习率是随机梯度下降算法中一个非常重要的超参数, 直接影响算法在实际应用中的性能. 一些学者按照αt=c1/(tv+c2)的形式对每轮学习率进行设置, 但这种形式在实际应用中收敛速度较慢, 且c1, c2和v的取值仍难以确定[79]. 另一些学者则认为应先在固定步长下快速寻找最优解的邻域, 再考虑更为精确的优化方案[80]. 目前, 寻找最优学习率在理论和实践上仍是一个巨大的挑战.

3)随机梯度下降算法在每轮迭代过程中计算复杂度较低, 但只利用了一阶梯度, 忽略了目标函数的二阶信息及曲率, 从而限制了实际性能和收敛速度[81]. 如何结合一阶与二阶方法各自的长处，进一步设计迭代效率俱佳的随机梯度下降算法，是未来值得研究的问题.

4)近年来, 研究者们将目光投向非凸的ERM模型, 并且提出了一些行之有效的解决方案[82-85], 其中具有代表性的策略包括添加动量跳出局部最优解[86]、使用方差缩技术减少梯度方差[87]和添加梯度噪声逃离鞍点[88]等. 然而, 对于更为一般的非凸、非光滑的优化问题却并未取得太大的突破, 目前仅有Prox-SAGA[89]、Prox-SVRG+[90]等算法, 但性能并不理想. 随机梯度下降算法在非凸、非光滑条件下的策略研究, 不仅是当前面临的困局, 也是未来最具有应用价值的研究方向.

5)对于非凸的优化问题, 梯度下降法通常存在两个缺陷: 易于陷入局部最优、无法逃离鞍点. 而演化计算/智能计算无需计算梯度和确定步长, 且往往具有较好的全局收敛性. 如何将随机梯度下降算法与演化计算/智能计算方法相结合, 将是一个非常值得关注的研究方向.

作者简介

史加荣

西安建筑科技大学教授. 主要研究方向为机器学习. 本文通信作者.E-mail: shijiarong@xauat.edu.cn

王丹

西安建筑科技大学硕士研究生. 主要研究方向为机器学习和随机优化算法. E-mail: wangdan_edu@163.com

尚凡华

西安电子科技大学教授. 主要研究方向为机器学习, 并行/分布式计算. E-mail: fhshang@xidian.edu.cn

张鹤于

西安电子科技大学硕士研究生. 主要研究方向为深度学习和分布式随机优化. E-mail: heyuzhang@stu.xidian.edu.cn