梯度下降（Gradient Descent）的收敛性分析

©作者 | 黄秋实

单位 | 香港中文大学（深圳）

研究方向 | 智能电网

梯度下降是一种简单且常用的优化方法，它可以被用来求解很多可导的凸优化问题（如逻辑回归，线性回归等）。同时，梯度下降在非凸优化问题的求解中也占有一席之地。我们常听到神经网络（neural network），也常常使用梯度下降及其变种（如随机梯度下降，Adam 等）来最小化经验误差（empirical loss）。

不妨设可导的目标函数（objective function）为f(w)，其中 w 为优化变量。对于优化问题（1）：

我们可以使用如下算法进行求解：

• 随机初始化优化变量  
• 重复如下步骤直至收敛： ，其中 为优化步长

算法收敛后得到的 即为原优化问题的一个解。显然，对于凸优化问题，梯度下降可以让带领我们找到全局的最优解（global minima）；但是对于非凸优化问题，梯度下降有很大的可能只能让我们得到一个局部最优（local minima）或者鞍点（saddle point）。

1. 在什么条件下，梯度下降可以保证 更新后的目标函数值 更小？

2. 优化步长 应该如何设定？可以随意选择吗？

3. 梯度下降的优化算法为什么可以收敛？收敛的速度又是多快呢？

为了回答以上问题，我们需要先回顾一些数学知识。

多元泰勒展开（multivariate Taylor expansion）

对于一个二阶可导的函数 ，它的泰勒展开可以表示为：

其中， 和 为函数定义域中任意两点， 是 和 众多凸组合（convex combination）中的一个（ ）。

Lipschitz 连续性

给定两个度量空间 和 ， 是集合 X 上的测度， 是集合 Y 上的测度。一个从集合 X 到集合 Y 函数 满足 Lipschitz 连续，则存在一个常数 对于集合 X 中任意两点 和 有：

因此对于函数 ，若其满足 Lipschitz 连续，则对于任意两点 w 和 v，都满足：

一个函数 f(x) 满足 Lipschitz 连续，可以理解为该函数的变化速率受到了限制。这个变化速率的上界就被称为 Lipschitz 常数。函数梯度的 Lipschitz 连续性在实际情况中相对容易得到满足，因为真实世界中的数据的变化幅度并不大。这也是很多其他数据处理方法物理释义，例如应用数据低秩性与稀疏性的 Robust PCA 等用压缩感知方法。对于常用的机器学习模型，例如逻辑回归，SVM等方法，大多可以证明其损失函数的梯度在一定条件下满足 Lipschitz 连续性。但是对于深度学习模型，我们无法证明。

有了如上两个至关重要的数学知识，我们就可以开始回答最开始的问题了。我们首先去回答：在什么条件下，梯度下降可以保证 更新后的目标函数值 更小？

下降引理 （Descent Lemma）

对于一个二阶可导的函数 ，它的导数 满足 Lipschitz 连续，则它的 Hessian 矩阵满足：

我们可以从这个角度来理解式（5）：首先，我们知道导数 变化最快的方向就是它的 Hessian 矩阵 绝对值最大特征值所对应的特征向量。由于 Hessian 矩阵 是对称矩阵（symmetric matrix），于是根据 Rayleigh quotient，我们就可以得到，对于任意 v 都满足：

因此，对于导数 满足 Lipschitz 连续的函数 ，它任意点 w 的 Hessian 矩阵 都满足 ，即式（5）。

当我们对这样满足二阶可导，且导数 满足 Lipschitz 连续的函数 进行泰勒展开时，我们可以得到

式（7）就是很多梯度相关的优化算法收敛性证明中常用的下降引理。

应用下降引理，我们就可以直接回答当前的问题了。我们将梯度下降的更新公式 代入式（7）中，我们就可以得到：

从式（8）中，我们可以看到，由于 ，所以当 时（即 ），我们就可以保证梯度下降算法的更新过程中，目标函数值的大小始终保持单调递减（非严格）的状态。并且当优化步长选取 时， 目标函数值缩减的速度最快（读者可以自行验证）。因此，我们可以看到选择最优的优化步长其实就是在估计目标函数的 Lipschitz 常数。

梯度下降的收敛性与收敛速度

在上面的论述中，我们已经回答了梯度下降算法为什么可以优化目标函数，让每一步优化得到的结果的目标函数的函数值更小。同时我们也给出了如何选择优化步长的指标。现在我们就来回答，为什么梯度下降的优化算法可以收敛？它的收敛速度又是多少？

梯度下降算法收敛性的证明依赖于如下三个条件：

• 目标函数的梯度 满足 Lipschitz 连续 
• 目标函数 ，即目标函数有一个下界 
• 优化步长  

我们来简单分析一下这三个条件：条件（1）和条件（3）使得下降引理成立，保证了梯度下降算法在优化目标函数过程中的正确性。同时，条件（3）也使得梯度下降算法处于收敛速度最快的状态，这有助于我们对算法收敛速度进行计算。条件（2）是一个不可或缺的条件，它保证了原始的优化问题存在可行解。例如，当 时，我们可以看到这个优化问题并不存在可行解；而当 时，这个优化问题就存在唯一可行解 。

我们注意到我们平时常用的损失函数，例如交叉熵，均方误差等，在一定的范围内（部分损失函数会依赖于一个好的初始值的选择）都可以满足以上三个条件。

首先我们证明梯度下降的收敛性。对于梯度下降算法的收敛条件，我们可以遵循如下定义：

其中 为任意常数， 是对应的收敛指标。根据优化定理，我们将优化步长 代入式（8），进而可以得到：

因此，当我们将前 K 步的 进行加和时，我们可以（神奇的）得到：

但是式（11）左侧的部分仍和 t 相关，我们可以通过放缩来去除它们与 t 之间的相关性。我们将每一个 放缩成为 进而得到：

于是，我们就得到了，从 到 的一共 步， 个梯度中，至少存在一个最小的梯度满足

由式（13），我们知道：虽然我们无法保证梯度下降的更新过程中每一步的 都随着算法迭代次数的增加而减小；但是对于收敛指标为 的情况下，算法可以保证在 步之内收敛。同时，对于任意给定的收敛指标 ，我们可以保证算法在 步之内收敛。

文章部分内容参考 [1] ，Lipschitz 连续性部分参考 [2] 。

参考文献

[1] CPSC 540 - Machine Learning (January-April, 2018) https://www.cs.ubc.ca/~schmidtm/Courses/540-W18/

[2] Lipschitz_continuity https://en.wikipedia.org/wiki/Lipschitz_continuity

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·