凸优化（3）——梯度与次梯度：方法，性质与比较

学弱猹

发布于 2021-08-09 17:14:04

1.5K0

发布于 2021-08-09 17:14:04

文章被收录于专栏：学弱猹的精品小屋学弱猹的精品小屋

上一节笔记：凸优化（2）——凸函数，强凸函数及相关拓展

——————————————————————————————————————————————————

大家好！

这一节我们主要会介绍梯度下降算法。当然可能有一些人看过《数值优化》

数值优化（2）——线搜索：步长选取条件的收敛性

的这一节内容，认为这个就是《数值优化》的线搜索方法。但请注意，二者并不是一样的东西。我们到正文会解释二者思想上的不同之处，而一个很重要的特点是在这一节中，我们会给出在“凸”这个视角考虑下的这个问题的一些收敛性结果，进而引出与次梯度有关的等更加有趣而先进的一些优化算法。

那么我们开始吧。

Source

CMU 10-725, Convex Optimization
Boyd, Vandenberghe, Convex Optimization
L. Vandenberghe, Lecture notes for EE 236C, UCLA, Spring 2011-2012
R. T. Rockafellar (1970), Convex Analysis
Carmon et al. (2017), Lower bounds for finding stationary points I

梯度下降法

我们在《数值优化》中接触过线搜索方法，并且我们使用梯度下降法（在《数值优化》中取了最速下降法的名字）举了一个例子。但是在这里我们关注的并不是一个一般的步长和搜索方向的选取（这是线搜索要解决的核心问题），而是单纯的考虑一阶信息对应的方法，也就是梯度信息对应的方法。这样的方法就是一阶方法（first-order methods）。如果是对于大数据相关的问题，一阶方法很多时候会有作用，因为它不需要计算二阶信息，也就不需要消耗对应的时间与空间。

回顾一下《数值优化》的概念，梯度下降法解决的依然是一个无约束优化问题，也就是

\min _x f(x)

这里我们多加一个条件就是

凸且一阶可微。迭代公式可以写成

x^{(k)} = x^{(k - 1)} - t_k \cdot \nabla f(x^{(k - 1)}), k = 1, 2, 3,\cdots

所以步长就是

t_k

，搜索方向就是

-\nabla f(x^{(k - 1)})

，显然它是一个下降方向，因为自变量沿着这个方向走一点，一定会导致函数值下降，当然走太多了就不一定了。

对于这个问题一个比较有意思的解释是，对于任何一个可微的函数，我们都可以通过Taylor展开，得到一个一阶近似

f(y) \simeq f(x) + \nabla f(x)^T ( y- x)

二阶信息不知道，但我们可以想一想，如果点距离

很远，那么我们希望步子迈大一点，如果说很近，那就自然希望步子迈小一点。所以一个比较好的想法就是加一个

\frac 1 {2t} \|y - x \|^2

，这样的话，算是一个二阶近似的近似（禁止套娃），而且也可以使得无论

距离

是远还是近，都可以得到一个不太离谱的罚项。

如果我们把右边的式子看成是

的函数，那么我们自然希望它能够最小化，所以通过对

求梯度，并令梯度为0，就可以得到更新公式

x^+ = x - t \nabla f(x)

所以这算是一个很有意思的理解，甚至有些贪心算法的味道。

在CMU的10-725这一门课中，对于梯度下降算法也采用了一样的想法，即推荐使用线搜索的思路。具体的算法可以使用基于wolfe条件的，也可以使用基于armijo-goldstein条件的，可以使用回溯法（backtracking），也可以使用非常复杂的基于三次函数的找步长的方法。这些都可以在《数值优化》的第2节中找到，链接在上面刚贴过，这里就不多说了。

接下来我们给出它的收敛性分析。还是一样，与《数值优化》不同的是，我们会给出函数性质不同的时候，对应的不同的收敛性分析的结果。

Theorem 1: 设

\nabla f(x)

具有

的光滑量度，也即

\|\nabla f(x) - \nabla f(y) \| \le L \|x - y\|, \forall x, y

，

L > 0

，

t \le \frac 1 L

，那么有

\min_{i = 0, \ldots, k} \| \nabla f(x^{(i)})\| \le \sqrt{\frac{2(f(x^{(0)}) - f(x^*))}{t(k + 1)}}

，其中

f(x^*)

表示最小值。

这里的

是步长，换句话说我们这里的迭代公式是固定步长的。

注意在这个定理下，我们并没有给出迭代值与真实极小值之间差异的一个估计，原因是在于没有凸性，优化算法只能找到驻点或局部极小值。不过实际中，尤其是高维问题中，驻点是鞍点的可能性并不大（想想为什么？），因此这个结论倒也不是说让人完全丧失希望。

这个证明不是很困难。首先我们注意到，因为有光滑性在，我们会有

f(y) \le f(x) + \nabla f(x)^T (y - x) + \frac L 2 \|y - x \|^2, \forall x, y

那么我们考虑代入公式

y = x - t \nabla f(x)

，化简，可以得到

f(x^+) \le f(x) - (1 - \frac{Lt}2)t \|\nabla f(x) \|^2

把

\| \nabla f(x) \|^2

移项可以得到

(1 - \frac{Lt}2)t |\nabla f(x) |^2 \le f(x) - f(x^+)

那么注意到我们有

t \le \frac 1 L

，所以左边其实是可以化简的，变成

\|\nabla f(x)\|^2 \le \frac 2 t ( f(x) - f(x^+))

因为本质上来说左边的系数

(1 - \frac {Lt} 2)t

是一个二次函数，而巧合的是正好可以发现

t = \frac 1 L

是它的一个极大值点，这个放缩的思路在于：既然对于任意的

你的式子都会成立，那么我就要求高一点，让左边取到这个式子可以考虑到的最大值。这样求完之后就可以得到一个

\| \nabla f(x)\|

的一个上界。

这个上界为什么重要呢？因为右边正好是相邻两步迭代函数的差。所以不停的相加，就可以得到

\sum_{i = 0}^k \| \nabla f(x^{(i)}) \|^2 \le \frac 2 t (f(x^{(0)}) - f(x^{(k + 1)})) \le \frac 2 t (f(x^{(0)}) - f(x^*))

最后把左边都放缩成

\min

，再开个根号就可以了。

这个推导不算困难，但是可以看出几点信息，一是固定步长方法可以收敛，但步长绝对不能太大。二是对函数可微性有要求，三是这个收敛速度是

O(\frac 1 {\sqrt k})

的。一般来说理解这个收敛速度是这样的：我们希望做到的是值尽可能的小，比方说我们得到了一个梯度的上界，那么我希望知道，这个上界小于一个任意小的

\epsilon

，需要花多少的功夫。比方说这里收敛速度是

O(\frac 1 {\sqrt k})

，那么就可以稍微估算得到

\frac1 {\sqrt k} \simeq \epsilon

k \simeq \frac 1{\epsilon^2}

因此我们会把它理解为：收敛需要

O(\frac 1 {\epsilon^2})

步，比方说我们希望精度是0.01，那么计算一下就是10000，这个也不算是一个小数字了。并且Source中的Carmon (2017)也证明了，除非是随机算法，否则这个速率就是最好的结果了。

接下来我们看一下，假如说我们有凸的性质，结果会不会有所改观。

Theorem 2: 在Theorem 1的基础上，添加条件为：

凸。那么这个时候有

f(x^{(k)}) - f(x^*) \le \frac {\|x^{(0)} - x^* \|^2}{2tk}

。

因为我们有了凸这个条件，所以就可以给出差值的上界了。

这个证明稍微复杂一点。首先我们其实在一开始给定了一个关系是

f(x^+) \le f(x) - \frac t 2 \|\nabla f(x) \|^2

（当然了这个是从Theorem 1的证明过程里面得到的，具体是哪一条读者可以自己找一找）那么根据这个，可以通过凸函数的一阶条件做进一步的放缩，得到

f(x^+) \le f(x^*) + \nabla f(x)^T (x - x^*) - \frac t 2 \|\nabla f(x) \|^2

（这里的一阶条件其实用的有一点隐晦，注意它是从

往

x^*

方向用的一阶条件）那么这样的话，我们可以思考一下，根据右边不等式这个上界的样子，我们希望推出的，是一个

\|x - x^+\|^2

这样的式子。这个式子的推导自然也依赖于之前的裂项相消的思路。那么我们看一下怎么样裂项相消呢？

我们可以计算一下

\|x - x^* \|^2 - \|x^+ - x^* \|^2

，因为

x^+ = x - t \nabla f(x)

，所以我们会有

\|x - x^* \|^2 - \|x^+ - x^* \|^2 = 2 t (\nabla f(x))^T(x - x^*) - t^2 \|\nabla f(x) \|^2

是不是和上面不等式的后面半部分挺像的？事实上只需要把

除掉，就可以得到我们的化简结果，也就是说

f(x^+) \le f(x^*) + \frac 1 {2t} (\|x - x^* \|^2 - \|x^+ - x^* \|^2)

那么有了这个，其实剩下的推理就简单了，我们可以通过完全一样的思路得到

\sum_{i = 1}^k (f(x^{(i)}) - f(x^*)) \le \frac 1 {2t} \|x^{(0)} - x^*\|^2

最后一步我们也略去不写，相信你会明白怎么得出最终的结论。

那么这个结论实际上就是在说，如果在凸的性质下，如果步长满足

t \le \frac 1 L

，就可以得到一个

O(\frac 1k)

的收敛速度。通过同样的方法，你可以得到，它的意思就是，如果我要得到满意的误差，需要

O(\frac1 \epsilon)

的迭代步数。这个虽然也不算少，但比之前的那个好多了。

最后其实就是强凸函数的情况了，但是强凸函数的情况我们已经在《数值优化》第2节的Theorem 6中给出了。这里多解释一句的是，我们在那里说“要求海塞矩阵正定是在一个局部的邻域内”，但是它的这个邻域其实并不小，是所有的满足

f(x) \le f(x_0)

的点的区域，这个要求其实和要求函数强凸几乎没差了。因此那里的分析步骤其实就是我们需要的强凸情况下的分析步骤，因为对于海塞矩阵的特征值的上界与下界进行限制，就是在对函数的光滑性与凸性做量化。

当然了，强凸的收敛速度就快很多，它的速度是

O(\gamma^k)

，换句话说，如果我们需要满足

\epsilon

这个误差，需要

O(\log(\frac 1 \epsilon))

的一个迭代步数，这相比较

O(\frac 1 \epsilon)

，又是一个大的进步。简而言之，凸对于最速下降法而言，是一个非常重要的性质。并且它是一个线性的收敛速度（这个线性的意思是它在半对数图中画出来是线性的），相比较而言，

O(\frac1 k)

和

O(\frac1 {k^2})

都是次线性的收敛速度。

那么到此为止，对于梯度下降法的分析，就告一段落。

进一段广告！

广告结束！

次梯度

次梯度（subgradient）是梯度的自然延伸，从次梯度方法这个角度出发，可以从另外一条线导出我们之前已经在《数值优化》提到的几个算法，不过在这之前，我们需要补充关于次梯度的概念和相关性质。

次梯度这个概念的起因非常简单：对于一个函数如果不可导，那么如何使用梯度方法？虽然说梯度方法不能够再使用了，但是通过次梯度这个概念，就可以一定程度上弥补这个缺陷，并衍生出一系列类似的方法。

我们首先给出次梯度的定义。

Definition 1: subgradient 对于凸实值函数

f: \mathbb R^n \to \mathbb R

和向量

g \in \mathbb R^n

，如果对于任意的

，都有

f(y) \ge f(x) + g^T(y - x)

，那么称

是一个

在

点处的次梯度。

这个概念有几个关键点容易被忽视。一是函数必须是凸函数，否则是不能定义次梯度的，因为如果不是凸函数，线性函数就不会是函数的一个低估，因此次梯度就无法保证存在。二是次梯度并不唯一，它可以是一个集合。对于复杂的问题，很多时候找到所有的次梯度并不现实，所以会退而求其次，找到某一个次梯度，但这就足够用上次梯度方法了。三则是说，如果

处函数可导，那么次梯度唯一，就是

\nabla f(x)

，这个证明学过数学分析就应该可以独立写出来，所以我们也就不提示大家了。

因为次梯度不唯一，所以还有一个对应的次微分的定义。

Definition 2: subdifferential 定义

\partial f(x)

为所有

点处

的次梯度的集合，称其为次微分。

好的，那我们现在来看个例子，做个计算。

Example 1: 设函数

f: \mathbb R^n \to \mathbb R, f(x) = \|x \|_2

，证明它的次梯度集为

\begin{cases}\frac x {\|x\|_2} & x \ne 0 \\ \{z: \|z\|_2 \le 1 \} & x = 0\end{cases}

我们先看看

x = 0

的情况，根据定义，我们就相当于要求

|y|_2 \ge g^T y = |g|_2 |y|_2 \cos \left<g, y\right>, \forall y

如果给定一个这样的不等式，那么如何判断这个

应该取什么呢？有一个思路是：观察右侧不等式最为苛刻的情况，如果这都可以满足，那么所有的就应该都可以满足。因此我们很容易发现，如果保持

的方向不变，但是长度不断增大，那么自然的，不等式右边的值就会变大。那么如果我们保持长度不变，把

转一转，那么很显然，

与

共线的时候，不等式右边的值是最大的，因此如果我们让它们共线，不等式就变成了

|y |_2 \ge |g|_2 |y|_2, \forall y

这就得到了

x= 0

处的次梯度表达式。虽然这并没有结束，因为同时要证明，如果

\|g\|_2 > 1

，那么就一定不是次梯度，但这个也不难说，因为如果

\|g \|_2 > 1

，那么我们让

转一圈，使得

与

共线，就不可能满足上面那个不等式。

接下来看看

x \ne 0

的情况，那么我们就需要满足

|y|_2 - | x |_2 \ge g^T (y - x) = |g|_2 |y - x|_2 \cos \left<g, y- x\right>, \forall y

这个情况会稍微有些不一样，在变化

的时候，左边和右边都需要考虑。不过事实上也不困难，考虑几何意义，在纸上画一画向量

x, y

，就会发现可以利用上三角不等式，也就是

- \|y - x \|_2 \le \|y \|_2 - \|x \|_2 \le \| y - x \|_2

因此只要考虑

与

y - x

的夹角即可。分别取共线和反向的方向，就可以得到

\|g \| = 1

这个先决条件。

有了这个之后，问题就变成了

应该是取什么方向，这个时候其实就更需要依赖几何的直觉了。不妨假设

\|y\|_2 \ge \|x\|_2

，我们画一张图解释一下

这里的图，蓝线表示向量

y- x

，绿线的

表示取了一段与

的相同长度的一段，那么剩下的那一段，长度就是

\|y\|_2 - \|x\|_2

。

的方向是与

共线的。为什么这样取呢？因为当

\|g\|_2 = 1

成立之后，右边其实就是

y- x

沿着

这个方向的投影，但是左边的话，只要保持

\|y\|_2

不变，就不会改变

\|y\|_2 - \|x\|_2

的值，但

\|y - x\|_2

在什么时候最大呢？是在

x,y

共线的时候，所以换句话说，如果要对任意的情况下，不等式都要成立，对于共线的情况就一定要考虑到，而共线的情况如果要满足，就需要

与

共线。所以可以得到

g = \frac {x}{\|x\|_2}

。而且事实上，可以验证的是，如果我们不取

是这个方向，那么假如说

往逆时针稍微转那么一点点，那么

在旋转的过程中，在接近

方向的时候，就会使得不等式不满足，感兴趣的读者可以继续画图验证，或拿着几何画板自己转转看，相信会有有意思的发现。

所以虽然说这只是一道关于次梯度的例题，但是可以发现这个推导也不是很容易。

再看一个次梯度的例子吧，这个例子后面会用上。

Example 2: 考虑凸集

C \subset \mathbb{R}^n

，并考虑指标函数

I_C: \mathbb R^{n} \to \mathbb R

，证明

\partial I_C(x) = \mathcal {N}_C(x)

，其中

\mathcal{N}_C(x) = \{g \in \mathbb{R}^n: g^T x \ge g^T y, \forall y \in C\}

为正规锥（Normal Cone）

这个证明不是很困难，走个定义就好。注意到我们只需要

满足

I_C(y) \ge I_C(x) + g^T(y - x), \forall y

而如果

y \not \in C

，是不需要讨论的，因为左边是无穷大。但如果

y \in C

，那么这个时候，不等式就是

0 \ge g^T(y - x)

，这就是结论了。

关于正规锥我们补一张CMU课件里面的图

可以看出，这个区域的边界上标了几个点，虚线标志的就是正规锥的位置，注意灰色区域对应的那个点是一个尖点，这个点两边的梯度方向不一样，所以分别取了与两边垂直的两个方向作为区域的边界。读者可以自己画一画，看看为什么正规锥是那样。

最后就是我们可以通过次梯度推导优化的最优性条件。

Proposition 1: 对凸函数而言，只要

0 \in \partial f(x^*)

，那么

x^*

就是极小值点。

这个性质的证明非常简单，因为既然

是一个次梯度，那么在不等式中取

为0，就可以得到

f(y) \ge f(x^*)+0^T(y - x^*) = f(x^*), \forall y

这就证明了结论。这个结论与之前可导情况下，优化的最优性条件是一致的，因为那个时候，次微分只有一个元素

\nabla f(x^*)

，所以就化归成为了

\nabla f(x^*) = 0

。

下面这个性质稍微有意思一点。

Proposition 2: 证明带约束优化的一阶最优性条件，也即

\nabla f(x)^T (y - x) \ge 0, \forall y \in C

。其中

是可行域，为凸集。

这个性质的证明要观察到可以通过指标函数，把带约束优化问题变成无约束优化问题。注意到其实这个带约束问题可以写成

\min_x f(x) + I_C(x)

所以这就可以利用上面的Proposition 1了，也就是计算

0 \in \partial (f(x) + I_C(x))

，注意到这就意味着

0 \in \{\nabla f(x)\} + \mathcal N_C(x)

（次梯度线性性，读者可以自己证明）

-\nabla f(x)^T x \ge -\nabla f(x)^T y , \forall y \in C

\nabla f(x)^T(y - x) \ge 0, \forall y \in C

这就证明了结论。

关于次梯度其实还有一些很重要的实际例子，会帮助我们理解它们的用处。不过我们这一节先讲一些算法上的东西，次梯度本身的例子我们放到下一节说。

再来段广告！

广告结束！

次梯度方法及收敛性

其实在格式上，次梯度方法与梯度法很像，但它的收敛性分析其实比梯度下降方法更加复杂一些。具体来说，它的迭代公式就是

x^{(k)} = x^{(k - 1)} - t_k g^{(k - 1)}, k = 1, 2, 3, \cdots

其中

g^{(k - 1)} \in \partial f(x^{(k - 1)})

，也就是说任何一个次梯度代入这里，都可以“替代”之前梯度法中的那个梯度。

这里要注意两点，一是次梯度方法并不能保证每一步都是下降方向，因此我们会记录每一步的值，并考虑它们中最小的那个，也就是说记录

f(x_{best}^{(k)}) = \min_{i = 0, \ldots, k} f(x^{(i)})

二是次梯度的步长选取上有一些讲究，因为没有下降方向，就自然没有步长选取条件这一说。步长选取一般有两种，一是固定步长

t_k = t

，另外一种是考虑一个下降的步长序列。也即

\sum_{k = 1}^\infty t_k^2 < \infty, \sum_{k = 1}^\infty t_k = \infty

比方说

t_k = \frac 1k

就是一个这样的序列，但是

t_k =\frac 1{k^2}

就不是。级数的性质告诉我们最终这个步长会收敛于0。

好的，那么我们来看一下次梯度方法的收敛性，对于不同的

Theorem 3: 对于固定步长的方法，如果

是Lipschitz连续的，且对应的常数为

（也即

|f(x) - f(y)| \le G \|x - y\|_2, \forall x, y

），那么有

\lim_{k \to \infty} f(x_{best}^{(k)}) \le f^* + \frac{G^2 t}{2}

这个性质最重要的一条信息就是固定步长下，次梯度方法是不收敛的。会有一个误差，这个误差有的地方会说是抽样误差，大家可以搜索一下为什么叫这个名字。

我们证明一下这个结论。首先我们自然要带入我们的迭代公式看一看，注意到

\|x^{(k)} - x^*\|_2^2 = \|x^{(k-1)} - t_k g^{(k-1)} - x^*\|_2^2 = \|x^{(k - 1)} - x^*\|^2 + t_k^2 \|g^{(k - 1)}\|^2 - 2t_k g^{{(k - 1)}^T}(x^{(k - 1)} - x^*)

那么这里其实并没有出现与

f(x)

相关的项，所以自然而然想到使用次梯度的表达式。所以代入，换掉

g^{(k - 1)}

，就可以得到

\|x^{(k)} - x^* \|_2^2 \le \|x^{(k - 1)} - x^*\|^2 + t_k^2 \|g^{(k - 1)}\|^2 - 2t_k(f(x^{(k - 1)}) - f(x^*))

那么很明显可以发现，相当于这就得到了一个与

x^{(k)}

自己相关的表达式。所以不停的迭代这个不等式，可以得到

\|x^{(k)} - x^* \|_2^2 \le \|x^{(0)} - x^* \|_2^2 - 2\sum_{i = 1}^k t_i (f(x^{(i - 1)} ) - f(x^*)) + \sum_{i = 1}^k t_i^2 \|g^{(i - 1)}\|_2^2

那么注意到左边其实是一个非负数，右边的第一项是一个常数，所以我们设它为

R^2

（因为它是一个平方项），并且根据Lipschitz连续，得到

\|g^{(i - 1)}\|^2 \le G

（想想为什么？），所以整体来看就得到了

0 \le R^2 - 2 \sum_{i = 1}^k t_i (f(x^{(i - 1)}) - f(x^*)) + G^2 \sum_{i = 1}^k t_i^2

那么这个时候就简单了，因为把中间的求和式子移项，把它们的所有的

f(x^{(i - 1)})

都变成

f(x_{best}^{(k)})

，就可以得到下面的这个不等式

f(x_{best}^{(k)}) - f(x^*) \le \frac{R^2 + G^2 \sum_{i = 1}^k t_i^2}{2\sum_{i = 1}^k t_i}

那么注意到因为是固定步长的，所以把每一个

t_i

都换成

就可以了（注意是取了极限）

通过这个式子也可以看出固定步长的次梯度方法的收敛速度。因为可以发现我们有

f(x_{best}^{(k)}) - f(x^*) \le \frac{R^2}{2kt} + \frac {G^2 t}{2}

那么自然的，我们会发现，这里的两项中，第二项只有一个未知参数

，因此控制它在一个

\epsilon

的量级下肯定是必要的。那么不妨我们让它

\le \frac \epsilon 2

，那么我们会得到

t = \frac \epsilon {G^2}

那么另外一项不如我们也让它

\le \frac \epsilon 2

，就可以得到

k \ge \frac{R^2 G^2}{\epsilon^2}

因此我们可以得到，如果要收敛，那么就需要

O(\frac1 {\epsilon^2})

的迭代步数。或者换句话说，可以认为它的收敛速度为

O(\frac1 {\sqrt k})

。

那么如果是下降的步长序列呢？我们也有一个结论，但不太一样。

Theorem 4: 如果步长取下降步长序列，也即

\sum_{k = 1}^\infty t_k^2 < \infty, \sum_{k = 1}^\infty t_k = \infty

，那么我们有

\lim_{k \to \infty} f(x_{best}^{(k)}) = f(x^*)

这个结论的证明非常简单，因为上面已经帮我们把任务完成了，注意到

f(x_{best}^{(k)}) - f(x^*) \le \frac{R^2 + G^2 \sum_{i = 1}^k t_i^2}{2\sum_{i = 1}^k t_i}

，代入条件就可以了。通过这个定理也可以看出，如果我们的步长满足一定条件，即使是次梯度方法，也能够收敛。

下面放出了CMU的课程课件中，对于岭回归和LASSO问题的时候的优化算法迭代曲线，可以看出梯度方法到达了数值误差（关于数值误差可以参考《数值优化》第3节：数值优化（3）——线搜索中的步长选取方法，线性共轭梯度法，可以通过搜索关键字“精度”找到对应的部分）之后就收敛了。但是次梯度方法很多时候是做不到的，在接近最小值的时候反而会徘徊，即使是下降步长的序列，也只有相对来说较小的精度。因此还是那句话，万事不可两全。我们到后面会说，次梯度方法很多时候更适合处理大规模的数据，但相比较梯度算法，可能精度上就会没那么好了。

在这一节的最后我们再简单提一下波利亚步长（Polyak Step-size）。

Definition 3: Polyak Step-size 定义步长

t_k = \frac{f(x^{(k - 1)}) - f(x^*)}{\|g^{(k - 1)} \|_2^2}

为波利亚步长。

这个波利亚是不是那个概率论中提出一大堆球模型的人我是不太了解的，但是看它提出的重球法（Heavy-ball Method，这个我们下一节会提到，这一节先留个悬念），我又觉得这个应该就是他233。

波利亚步长的设计思路就是考虑之前证明次梯度方法中的那个不等式

\|x^{(k)} - x^* \|_2^2 \le \|x^{(k - 1)} - x^*\|^2 + t_k^2 \|g^{(k - 1)}\|^2 - 2t_k(f(x^{(k - 1)}) - f(x^*))

最小化最右边的式子就可以得到波利亚步长。波利亚步长也可以使得次梯度方法收敛，但是收敛速度并没有改进。具体的原因我们放到下一节再继续说。

OK，那么关于波利亚步长，就说这么多。

小结

本节的重点就落在了两个字：梯度。我们说明了梯度方法和次梯度方法的各种情况下的收敛速度，方法的收敛性结果的不同，以及方法的应用场景的思考与比较。当然碍于篇幅，更加高级的东西我们这一节就没有多说。但下一节我们会继续关注这些内容，介绍一些实际的运算实例。如果还有空位的话，就再介绍一下机器学习和深度学习里热门的随机梯度下降方法。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-09-09，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

网站

本文分享自学弱猹的精品小屋微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

网站

登录后参与评论

0 条评论

热度