第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
梯度下降算法综述.docx
梯度下降算法综述
摘要 优化问题是统计机器学习过程中一个关键问题。在诸多算法中，梯度下降算法以其算法简单、收敛
速度快的优点独树一帜。本文立足基础层面，重点介绍优化方法中的梯度下降算法。从收敛性分析、算法
不足以及优化推广等三个方面做了较为系统的阐述。
关键词 梯度下降； 随机梯度； 动量梯度； Adam
1 导言
1.1 关于导数
导数定义如下： '(0)=→0=→0(0+−(0))
一点处沿着 x 轴正方向的变化率。也就是在 x 轴上某一点处，如果’()>0，说明 f(x)的
函数值在 x 点沿 x 轴正方向是趋于增加的；如果’ <0，说明()的函数值在 x 点沿 x 轴
导数反映的是函数 y=f(x)在某一点处沿 x 轴正方向的变化率，是函数 f(x)在 x 轴上某
正方向是趋于减少的。
1.2 偏导数与方向导数
偏导数的定义如下：
方向导数的定义如下：
在其他特定方向上的变化率。而方向导数就是函数在其他特定方向上的变化率。
1.3 梯度
方向导数指的是某一点在某一趋近方向上的导数值。
我们不仅要知道函数在坐标轴正方向上的变化率（即偏导数），而且还要设法求得函数
0,1,…,
=→0=→00,…,+,…, −0,…,,…,
偏 导 数 指 的 是 多 元 函 数 中 ， 函 数=(0,1,...,) 在 某 一 点 处 沿 某 一 坐 标 轴
(0,1,...,)正方向的变化率。
0,1,…,
=→0(0+0,...,+,...,+)−(0,...,,...,)
梯度的定义如下：0,1,…, = 0,…,,…,
算法背后的原理是：目标函数f(x)关于参数 x 的梯度将是目标函数上升最快的方向。对于最
降。即给定一个与参数 x 有关的目标函数f(x)， 求使得 J 最小的参数 x.我们把这个步长又
称为学习速率η。参数更新公式如下：x←x−η⋅∇f(x)
其中∇f(x)是参数的梯度，根据计算目标函数J(θ)采用数据量的不同，梯度下降算法又
1.4 梯度下降
梯度下降算法（Gradient Descent）是神经网络模型训练最常用的优化算法。梯度下降
小化优化问题，只需要将参数沿着梯度相反的方向前进一个步长，就可以实现目标函数的下
可以分为批量梯度下降算法（Batch Gradient Descent），随机梯度下降算法（Stochastic
函数在某一点的梯度是这样一个向量，它的方向与取得最大方向导数的方向一致，而它
的模为方向导数的最大值。
- 1 -
GradientDescent）和小批量梯度下降算法（Mini-batch Gradient Descent）。
个条件对函数值的变化做出了限制。
2.1.2 β平滑
自变量之差模长的常数倍。
2.1.3 β平滑性质 1
满足β平滑[2]的函数有如下性质：
证明如下：
可以把函数值之差转化为积分：
2.1 几个引理
2.1.1
如果标量函数 f(x)f(x)满足如下条件，称其满足 Lipschitz 连续性条件[1]。
Lipschitz（利普希茨）连续
2 梯度下降算法收敛性
梯度下降(Gradient Descent)以η为学习率，在每次迭代中用一阶泰勒展开近似：
设 x 的维度为 n，代价函数 f 是个标量，梯度∇f(x)也是一个 n 维向量。
其中||x||表示向量的模长，L 称为 Lipschitz 常数。对于固定的 f，L 是一个定值。 这
如果函数f(x)的梯度满足值为β的 Lipschitz 连续，称函数f(x)为β平滑：
其中||x||2=xx。这个条件对函数梯度的变化进行了约束：梯度之差的模长，不会超过
x+1←x−η⋅∇f(x)
|(1)−(2)|≤||1−2||
||()−()||2≤||−||2
|()−()−()(−)|≤2||−||2
构造一个插值函数()=(+(−))，其关于 t 的导数：
'()=(+(−))(−)
1(+(−))(−)
()−()=(1)−(0)= 0
= 0
1(+(−))(−)
代入左侧： =| 0
−()(−)|
1(+(−))(−)
1()(−)
− 0
=|
0
1[+− − −()(−)]
两个积分号合并：=|
|
0
1|+− − − −|
≤ 0
1|+− − |−
≤ 0
1|[+− −]−|
≤ 0
利用柯西施瓦茨不等式，≤ ||||2||||2
第二项是和 t 无关的常数，可以直接写入[0,1]的积分中：
1'()
和的绝对值小于绝对值之和：
|
- 2 -
出现了两个梯度相减，可以利用β平滑定义：
证毕
下。于是有
进而:
性质 1 变为：
=2||−||2
2.1.4 β平滑性质 2
满足β平滑的凸函数，符合如下性质：
考虑一个新的点=−1(()−())，把左式（函数值）差拆解成两部分：
≤ 0
1||(−)||2||−||2
≤ 0
特别地，如果 f 是凸函数，过[y,f(y)]点的切线()=()+()−()在曲线之
1||+− −||2| − |2
1
=||(−)||2
0
()=()+()−()<()
()−()−()(−)>0，
()−()−()(−)≤2||−||2
− ≤ − −12||()−()||2
()−()=()−()+()−()
()−()≤()(−)=()(−)+()(−)
− ≤ − +2− − +2||−||2
两部分相加，合并− 项：
()−()≤()(−)+[ −](−)+2||−||2
前两项已经凑齐了，带入−=1(()−())：
− ≤ − +1 − −
+212|| −||2= − −1|| −||2
对比性质 1 和性质 2：|()−()−()(−)|≤2||−||2
− ≤ − −12||()−()||2
两者都比较了函数值之差和不同点线性拟合之差。
对于性质 1 来说，β越小，越接近线性函数，右侧第二项越小。
对于性质 2 来说，第二项还包含了梯度之差，也受到β影响。
第一部分，根据函数 f 的凸性，易得：
第二部分，直接利用性质 1
- 3 -
2.2 收敛性证明
2.2.1x的极限
证明新解x+1比当前解x更接近最终解∗[3]。
考察新解到最终解的距离||+1−∗||2=||−()−∗||2
打开平方号： =||−∗||2−2()(−∗)+2||()||2
利用β平滑的性质 2，考察在x点的线性拟合：
()−(∗)≤()(−∗)−12||()−(∗)||2
由于∗为最终解，∗ =0, >(∗)：
()(−∗)−12||()||2≥0
−()(−∗)≤−12||()||2
代入前式：||+1−∗||2≤||−∗||2−||()||2+2||()||2
=||−∗||2−(1−)||()||2
只要学习<1，就可以保证：||+1−∗||2≤||−∗||2
2.2.2()的极限
利用β平滑的性质 1，比较两次迭代的代价：
收敛条件的物理意义
最优解的代价，比较两次迭代“距极限的距离”：
利用前面提到的凸函数性质以及柯西-施瓦茨不等式，构造一个关系：
(+1)−()≤()(+1−)+2||+1−||2
=−||()||2+22||()||2=−(1−2)||()||2
(+1)−(∗)≤[()−(∗)]−(1−2)||()||2
−∗ ≤ −∗ ≤||||⋅||−∗||
[+1 −∗]≤[ −∗]−(1−2)[ −∗]2
||−∗||2
−||||≤− −∗
||−∗||
||0−∗||2≥||−∗||2
前小节已证：
可以去除分母中的 t：
这就是“距极限距离”之差一式的最后一项，代进去：
- 4 -
[+1 −∗]≤[ −∗]−(1−2)[ −∗]2
||0−∗||2
两边同除正数[+1 −∗][ −∗]：
+1 −∗ +(1−2)
1
||0−∗||2 −∗
1
−∗ ≤
+1 −∗
+1−∗ >1：
由前小节，可知−∗
+1 −∗ +(1−2)
1
1
−∗ ≤
||0−∗||2
从 0 到−1 累加上不等式：1
0 −∗ ≥(1−2)
1
−∗ −
||0−∗||2
−∗ ≥(1−2)
1
||0−∗||2
(1−2)⋅1
1
−∗ ≤||0−∗||2
左边第二项是正数：
随机向量，并要求它的期望值将是函数在当前向量上的次梯度。
3.1 次梯度
极限
3 随机梯度下降
在随机梯度下降中，我们不要求更新方向精确地基于梯度。相反，我们允许方向是一个
代价序列 到最优代价的差小于数列1的常数倍，说明代价序列的收敛率为O(1)。
凸函数:→在点0的次导数，实数 c 使得：
−0 ≥(−0)
对于所有 I 内的，在点0的次导数的集合是一个非空闭区间[,]。其中 a 和 b 是单侧
=→0− −(0)
−0
=→0+ −(0)
−0
它们一定存在，且满足a≤b。
所有次导数的集合[,]称为函数在0的次微分。
如果:→是一个实变量凸函数，定义在欧几里得空间内的凸集，则该空间内的向
量称为函数在点0的次梯度，如果对于所有 U 内的 x，都有：
−0 ≥(−0)
所有次梯度的集合称为次微分，记为(0)。次微分总是非空的凸紧集。
将次导数和次微分的概念推广到多元函数，就可以得到次梯度了。
需要注意以下 3 点：
- 5 -
从该方法的定义，引出随机梯度下降算法（Stochastic Gradient Descent），即：
+1=−∙
3.3 随机梯度下降
次梯度算法梯度每次更新是根据某一个样本计算获得，而不是通过所有样本更新次梯度，
() )−∗≤22+22
→∞(
(3)用次梯度对原函数做出的泰勒一阶展开估计总是比真实值要小；次梯度可能不唯一。
3.2 次梯度下降的收敛性
(1)次梯度是指在函数上的点满足以上条件的∈
(2)函数不一定要是凸函数，非凸函数也可以，即对于凸函数或者非凸函数而言，满足
上述条件的均为函数在该点的次梯度。但是凸函数总是存在次梯度，而非凸函数则不一定
存在次梯度，即使可微。
如果为凸函数，且次梯度算法满足参数为 G 的 Lipschitz 条件，如果固定步长为，
其中为初值0与最优点∗之间的二范数距离，2=||0−∗||2。
如果令22+22 =，每部分等于2，则可以得到：η= 2,t=2=222
因此，次梯度的收敛速度为O(12)，跟梯度下降算法收敛速度O(1)相比，要慢许多。
其中，是第次迭代随机选取的样本。
当函数可微连续时，=()，就是随机梯度下降。用每个样本的当前梯度水平来更新。
L=12=1
L=12[− +]2
[− +]2
目标 w∗,b∗=argmin,12=1
w∗,b∗=argmin,12[− +]2
[− +]2
=−=1
[− +]
=−[− +]
+1=−
+1=−=+[−
[−
=+=1
+]
+]
，1≈2≈3≈∙∙∙≈,+1≈
=12()
1、冗余信息的计算上。考虑一个特殊情况，min
+2≈+3≈∙∙∙≈2,很多项是冗余的，min
=12()
与min
[1 ++1]的优化结果
3.4 梯度下降算法与随机梯度下降的比较
GD
SGD
L´eon Bottou 等[4]提出了 GD 与 SGD 算法的三个区别：
满足：
其定义为：
损失
函数
优化
迭代
过程
- 6 -
样例求和，需要更多的计算。如果数据集比较大，可能会面临内存不足问题，而且其收敛速
度一般比较慢。SGD 算法针对训练集中的一个训练样本计算的，又称为在线学习，即得到了
一个样本，就可以执行一次参数更新。所以其收敛速度会快很多，但是有可能出现目标函数
值震荡现象，因为高频率的参数更新导致了高方差。
是相近的。 如果采取 GD 去迭代，每一次要算2个梯度。但是如果用 SGD，每一次选一个
计算梯度，得到的下降方向，就等于 GD 算个得到的下降方向。
2、训练速度上。GD 算法其()是在整个训练集上计算的，权值更新的每一步对多个
3、计算复杂度上。GD 在强凸的情况下收敛速度最差的情况下，至少需要迭代( 1 )
||]≤的精度，加上 GD 每一次需要计算个梯度，所以总
次，才能达到[||1
的计算复杂度是 ( 1 ) 。SGD 在最差的情况下，我们需要迭代次数是(1)，但是
因为 SGD 每一次算一个梯度，所以它的计算复杂度也是(1)。如果 n 特别大，那么 SGD 在
计算复杂度上依然有优势。
=1 −∗
另外金驰等[5]提出，SGD 还有一个极佳的特性是可以逃离鞍点和局部最小点。主要思
想是传统的 GD 算法在鞍点位置就容易收敛，因为导数为 0。而 SGD 算法在鞍点附近时，由
于它每步选择样本计算梯度方向的随机性，使得在鞍点附近可以有很大的机会沿着负特征值
方向前进，搜索下一个局部最优点。
汪宝彬等[6]还给出了正则化格式下随机梯度下降法的收敛速度。利用线性迭代的方法,
并通过参数选择,得到了随机梯度下降法的收敛速度
4 其他衍生方法介绍
4.1 小批量随机梯度下降法[7]（mini-batch SGD ）
4.1.1 主要思想
其主要思想就是每次只拿总训练集的一小部分来训练，比如一共有 5000 个样本，每次
拿 100 个样本来计算损失函数，更新参数。50 次后完成整个样本集的训练，为一轮（epoch）。
由于每次更新用了多个样本来计算损失函数，就使得损失函数的计算和参数的更新更加具有
代表性。不像原始 SGD 很容易被某一个样本给带偏 。损失的下降更加稳定，同时小批量的
计算，也减少了计算资源的占用。
4.1.2 迭代过程
小批量梯度下降，是对批量梯度下降以及随机梯度下降的一个折中办法。其思想是：每
次迭代 使用 b = batch_size 个样本来对参数进行更新。对应的目标函数（代价函数）为：
= =12=1
( −)2
∂L=1=1
( −)
−
|=
θ+1=θ−=1
- 7 -
对目标函数求偏导：
每次迭代对参数进行更新：
4.1.3 批数选择带来的影响：
1、在合理地范围内，增大批数的好处：
a. 内存利用率提高了，大矩阵乘法的并行化效率提高。
b. 跑完一次 epoch（全数据集）所需的迭代次数减少，对于相同数据量的处理速度进
一步加快。
c. 在一定范围内，一般来说批数越大，其确定的下降方向越准，引起训练震荡越小。
2、盲目增大批数的坏处：
a. 内存利用率提高了，但是内存容量可能撑不住了。
b. 跑完一次 epoch（全数据集）所需的迭代次数减少，要想达到相同的精度，其所花
费的时间大大增加了，从而对参数的修正也就显得更加缓慢。
c. 批数增大到一定程度，其确定的下降方向已经基本不再变化。
4.2 动量梯度下降法(gradient descent with momentum)
4.2.1 主要思想
回顾一下梯度下降法每次的参数更新公式：
可以看到，每次更新仅与当前梯度值相关，并不涉及之前的梯度。
而动量梯度下降法则对各个 mini-batch 求得的梯度∇W使用指数加权平均得到
+1=− ，+1=−
+1=+ 1−+1,0=0,
+1=+ 1−+1,0=0
并使用新的参数更新之前的参数。
4.2.2 主要优点
相比于小批量随机梯度下降，动量法在每个时间步的自变量更新量近似于将前者对应的
时间步的自变量更新量做了加权移动平均。
所以动量法中，自变量在各个方向上的移动幅度不仅取决当前梯度，还取决于过去各个
梯度在各个方向上是否一致。
例如：若梯度在水平方向上为正（向右）、而在竖直方向上时正（向上）时负（向下），
自变量在水平方向的移动幅度逐渐增大，而在竖直方向的移动幅度逐渐减小。这样，我们就
可以使用较大的学习率，从而使自变量向最优解更快移动。一方面收敛速度更快，另一方面
可以逃离鞍点。
4.3 共轭梯度下降
4.3.1 主要思想
共轭梯度法[8][9]是最优化理论中最常用的方法之一，它是介于最速下降法与牛顿法之
间的一种优化方法。其主要思想是，下降方向是负梯度方向与上一次迭代产生的搜索方向的
组合。该组合可以是线性组合，也可以是非线性的组合。
迭代过程为：
=
+1=+;
−,
=1
−+−1,≥2
=(−−1)
||−1||2
- 8 -
目前非线性共轭梯度法里比较好的是由 Polak 等在 1969 年提出的，简称 PR 方法。其参
数更新公式是：
4.3.2 主要优点
共轭梯度法保留了最速下降法和牛顿法的优点且避免了它们的缺点，具有收敛速度快、
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
