新浪博客

随机梯度下降算法研究进展

2022-07-22 17:06阅读：

http://blog.sina.cn/dpool/blog/u/1304706164

引用本文

史加荣, 王丹, 尚凡华, 张鹤于. 随机梯度下降算法研究进展. 自动化学报, 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]

我的更多文章

下载客户端阅读体验更佳

APP专享