🙍🏼 🦗 👇🏾 数学优化问题中的梯度方法概述 🙃 👨🏿‍🔬 ❄️

前言

本文将重点介绍基于函数梯度的使用来解决数学优化问题的方法。主要目标是在本文中收集与该方法及其各种修改相关的所有最重要的想法。

UPD 他们在评论中写道，在某些浏览器上和移动应用程序中，公式未显示。不幸的是，我不知道如何处理。我只能说我使用了Habrava编辑器的“内联”和“显示”宏。如果您突然知道如何解决此问题，请在评论中写下。

作者注

在撰写本文时，我捍卫了一篇论文，该论文的任务要求我对数学优化的基本理论方法有深入的了解。但是，我的眼睛（和其他所有人一样）仍然被可怕的长公式模糊不清，因此我花了很多时间来找出可以描述渐变方法不同变化的关键思想。我的个人目标是写一篇文章，其中包含对这个主题或多或少进行详细了解所需的最少信息。但是要做好准备，反正不能没有公式。

问题陈述

在描述方法之前，您必须首先描述问题，即：

数 学

$\数学{K}$ 和功能

：

$f：\ mathcal {K} \ rightarrow \ mathbb {R}$ 需要找到一点

$x ^ * \ in \ mathcal {K}$ 这样

（ ） （ ）

$f（x）\ geq f（x ^ *）$ 对于所有

$x \ in \ mathcal {K}$ “，通常这样写

（ ）

$f（x）\ rightarrow \ min_ {x \ in \ mathcal {K}}$

理论上 ，通常假设

$f$ 是微分和凸函数，并且

数 学

$\数学{K}$ -凸集（甚至更好）

$\ mathcal {K} = \ mathbb {R} ^ n$ ），这使我们能够为成功应用梯度下降提供一些保证。在实践中，即使任务不具有以上任何属性，也可以成功应用梯度下降（本文后面的示例）。

一点数学

假设现在我们只需要找到一维函数的最小值

（ ）

$f（x）\ rightarrow \ min_ {x \ in \ mathbb {R}}$

早在17世纪，皮埃尔·费马（Pierre Fermat）提出了一个准则，可以解决简单的优化问题，即

$x ^ *$ -最低点

$f ^ *$ 然后

（ ）

$f'（x ^ *）= 0$

在哪里

$f'$ -衍生

$f$ 。该准则基于线性近似。

（ ） 约 （ ） （ ） （ ）

$f（x）\约f（x ^ *）+ f'（x ^ *）（x-x ^ *）$

更紧密

$x$ 到

$x ^ *$ ，此近似值越准确。右侧是一个表达式，当

（ ）

$f'（x ^ *）\ neq 0$ 也许更多

（ ）

$f（x ^ *）$ 少是该标准的主要本质。在多维情况下，类似于线性近似

（ ） 约 （ ） （ ） （ ）

$f（x）\约f（x ^ *）+ \ nabla f（x ^ *）^ T（x-x ^ *）$ （以下

$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ -标准标量积，其书写形式是由于标量积与行向量乘以列向量的矩阵乘积相同）而获得了标准

（ ） 。

$\ nabla f（x ^ *）= 0。$

价值

（ ）

$\ nabla f（x ^ *）$ -功能梯度

$f$ 在这一点上

$x ^ *$ 。同样，梯度等于零意味着所有偏导数等于零，因此，在多维情况下，可以通过分别为每个变量依次应用一维准则来简单地获得该准则。

值得注意的是，这些条件是必要的，但还不够，最简单的示例是0

（ ）

$f（x）= x ^ 2$ 和

（ ）

$f（x）= x ^ 3$

在凸函数的情况下，该标准就足够了，这主要是因为它有可能获得许多凸函数的结果。

二次函数

$\ mathbb {R} ^ n$ 是形式的功能

（ ） （ ， ， ， ） ，

$f（x）= f（x_1，x_2，\ ldots，x_n）= \ frac {1} {2} \ sum_ {i，j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c$

为了节省空间（并且减少使用索引的麻烦），此函数通常以矩阵形式编写：

（ ） ，

$f（x）= \ frac {1} {2} x ^ TAx-b ^ Tx + c，$

在哪里

（ ， ， ）

$x =（x_1，\ ldots，x_n）^ T$ ，

（ ， ， ）

$b =（b_1，\ ldots，b_n）^ T$ ，

是交点处的矩阵

我

$我$ 字符串和

$j$ 列是值

（ ）

$\ frac {1} {2}（a_ {ij} + a_ {ji}）$ （

结果证明是对称的-这很重要）。下一个当提到二次函数时，我将具有上述函数。

我为什么要谈论这个？事实是二次函数在优化中很重要，原因有两个：

它们在实践中也会发生，例如，在构建线性最小二乘回归时
二次函数的梯度是线性函数，尤其是对于上面的函数
$部分部分（，，，）（），$
$\ frac {\部分} {\部分x_i} f（x_1，x_2，\ ldots，x_n）= a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2}（a_ {ij } + a_ {ji}）x_j -b_i，$

或以矩阵形式
$\ nabla f（x）= Ax-b，$

因此系统 $\ nabla f（x）= 0$ -线性系统。没有比线性更简单的系统。我试图达到的想法是二次函数的优化-最简单的优化问题 。另一方面，事实是 $\ nabla f（x ^ *）= 0$ -必要的最低条件使通过优化问题解决线性系统成为可能。稍后，我将尝试说服您，这是有道理的。

有用的渐变属性

好吧，我们似乎已经发现，如果一个函数是可微的（它对所有变量都有导数），那么在最小点处梯度应该等于零。但是，当梯度非零时，它会携带任何有用的信息吗？

让我们尝试解决一个更简单的问题：

$x$ 寻找点

$\ bar {x}$ 这样

$f（\ bar {x}）<f（x）$ 。让我们在

$x$ 再次使用线性逼近

$f（\ bar {x}）\约f（x）+ \ nabla f（x）^ T（\ bar {x} -x）$ 。如果你拿

$\ bar {x} = x- \ alpha \ nabla f（x）$ ，

$\ alpha> 0$ 然后我们得到

$f（\ bar {x}）\约f（x）-\ alpha \ | \ nabla f（x）\ | ^ 2 <f（x）。$

同样，如果

$\ alpha <0$ 然后

$f（\ bar {x}）$ 会更多

$f（x）$ （以下

$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2}〜$ ）再一次，由于我们使用了近似值，因此这些考虑仅对小样本才成立

$\ alpha$ 。总结一下，如果

$\ nabla f（x）\ neq 0$ ，则梯度表示函数的最大局部增加的方向 。

这是二维函数的两个示例。在梯度下降的演示中经常可以看到这类照片。彩色线是所谓的水平线 ，这是功能针对其的固定值的一组点，在我的情况下，这些是圆和椭圆。我用较低的值标记了水平的蓝线，用较高的值标记了红色。

请注意，对于由以下形式的方程式定义的表面

$f（x）= c$ ，

$\ nabla f（x）$ 将法线（普通人-垂直线）设置为此表面。还要注意，尽管梯度在函数中显示为最大增加的方向，但是不能保证在与梯度相反的方向上可以找到最小值（例如，左图）。

梯度下降

基本梯度下降法仅剩一小步：我们从这一点中学到了

$x$ 得到点

$\ bar {x}$ 功能值较低

$f$ 。是什么阻止我们重复几次？实际上，这就是梯度下降：我们建立序列

$x_ {k + 1} = x_k- \ alpha_k \ nabla f（x_k）。$

价值

$\ alpha_k$ 称为步长（机器学习中的学习速度）。关于选择的几句话

$\ alpha_k$ ：如果

$\ alpha_k$ -非常小，序列变化缓慢，这使得算法效率不高；如果

$\ alpha_k$ 如果非常大，则线性近似会变差，甚至可能不正确。在实践中，步长通常是根据经验选择的；理论上，通常假设使用Lipschitz梯度，即

$\ | \ nabla f（x）-\ nabla f（y）\ | \ leq L \ | x-y \ |$

对于所有

$x，y$ 然后

$\ alpha_k <\ frac {2} {L}$ 保证减少

$f（x_k）$ 。

二次函数分析

如果

是对称的可逆矩阵，

$Ax ^ * = b$ 然后对于二次函数

$f（x）= \ frac {1} {2} x ^ TAx-b ^ Tx + c$ 点

$x ^ *$ 是最低点（ UPD 。只要该最低点完全存在-

$f$ 没有接近

$-\臭名昭著的$ 仅当

正定），对于梯度下降方法，我们可以获得

$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f（x_k）-x ^ * = x_k- \ alpha_k（Ax_k-b）-x ^ * =$

$（x_k-x ^ *）-\ alpha_kA（x_k-x ^ *）=（I- \ alpha_k A）（x_k-x ^ *），$

在哪里

$我$ 是单位矩阵，即

$Ix = x$ 对于所有

$x$ 。如果

$\ alpha_k \ equiv \ alpha$ 事实证明

$\ | x_ {k} -x ^ * \ | = \ |（I- \ alpha A）^ k（x_0-x ^ *）\ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |。$

左边的表达式是与步骤中获得的近似值的距离

$k$ 梯度下降到最小点，在右边-形式的表达

$\ lambda ^ k \ beta$ 如果收敛到零

$| \ lambda | <1$ （我写的条件

$\ alpha$ 在上一段中，这正是保证）。该基本估计可确保梯度下降收敛。

渐变下降修改

现在，我想谈一谈梯度下降的常用修改，主要是所谓的

惯性或加速梯度法

此类的所有方法表示如下

$x_ {k + 1} = x_k- \ alpha_k \ nabla f（x_k）+ \ beta_k（x_k-x_ {k-1}）。$

最后一项表征了相同的“惯性”，每一步的算法都试图逆梯度运动，但与此同时，它部分地由于惯性沿与上一次迭代相同的方向运动。此类方法具有两个重要属性：

实际上，它们并没有使计算计划中通常的梯度下降复杂化。
精心选择 $\ alpha_k，\ beta_k$ 即使采用最佳选择的步骤，此类方法也比普通梯度下降快一个数量级。

最早的此类方法之一出现在20世纪中叶，称为重球法 ，它传达了该方法的惯性性质：在此方法中

$\ alpha_k，\ beta_k$ 独立于

$k$ 并根据目标函数精心选择。值得注意的是

$\ alpha_k$ 可能除了

$\ beta_k$ - 通常只比一个少一点 。

重球法是最简单的惯性方法，但不是最开始的方法。我认为在这种情况下，第一种方法对于理解这些方法的本质非常重要。

切比雪夫方法

是的，是的，这种类型的第一种方法是Chebyshev发明的，用于求解线性方程组。在梯度下降的分析中，可以得到以下等式

$x_ {k + 1} -x ^ * =（I- \ alpha_k A）（x_k-x ^ *）= \ ldots =$

$（I- \ alpha_kA）（I- \ alpha_ {k-1} A）\ ldots（I- \ alpha_1A）（x_0-x ^ *）= P_k（A）（x_0-x ^ *），$

在哪里

$P_k$ 是某种程度的多项式

$k$ 。为什么不尝试接机

$\ alpha_k$ 这样

$P_k（A）（x_0-x ^ *）$ 较小吗？ Chebyshev多项式是一类与零偏差最小的通用多项式。切比雪夫的方法主要在于选择下降参数，以便

$P_k$ 是契比雪夫（Chebyshev）的多项式。确实存在一个小问题：对于正常的梯度下降，这根本不可能。但是，对于惯性方法，这是可能的。这主要是由于Chebyshev多项式满足二阶递归关系

$T_ {n + 1}（x）= 2xT_n（x）-T_ {n-1}（x），$

因此，不能为梯度下降而构建它们，因为梯度下降只能从一个先前的值中计算出一个新值，而对于惯性来说，由于使用了两个先前的值而成为可能。原来，计算的复杂性

$\ alpha_k，\ beta_k$ 不依赖

$k$ 也不是空间的大小

$n$ 。

共轭梯度法

另一个非常有趣且重要的事实（是汉密尔顿-凯利定理的结果）： 对于任何方阵

大小

$n \倍n$ 有一个多项式

$P$ 不再学位

$n$ 为此

$P（A）= 0$ 。为什么这很有趣？都是一样的平等

$x_ {k + 1} -x ^ * = P_k（A）（x_0-x ^ *）。$

如果我们可以选择梯度下降中的步长，以便精确地获得该归零多项式，则梯度下降将收敛一个不大于维数的固定迭代次数

。正如我们已经发现的，对于梯度下降我们无法做到这一点。幸运的是，对于惯性方法，我们可以做到。该方法的描述和论证是非常技术性的，我将限于本质： 在每次迭代中，选择的参数将给出最佳多项式，可以在考虑梯度测量当前步骤之前进行的所有测量的情况下构建参数 。同时

梯度下降的一次迭代（不考虑参数计算）包含一个矩阵乘以一个向量和2-3个向量加法
参数的计算还需要通过矢量进行1-2矩阵相乘，通过矢量进行2-3标量矢量相乘以及对矢量进行多次加法。

计算计划中最困难的事情是将矩阵与向量相乘，这通常是及时完成的

$\数学{O}（n ^ 2）$ 但是，对于特殊的实现，可以在

$\数学{O}（m）$ 在哪里

$m$ -中的非零元素数

。给定共轭梯度法的收敛性，不超过

$n$ 迭代获得算法的整体复杂度

$\数学{O}（nm）$ ，在所有情况下都不会更糟

$\数学{O}（n ^ 3）$ 用于高斯或乔尔斯基方法，但如果

$m << n ^ 2$ 那不是那么罕见。

共轭梯度法也可以很好地工作

$f$ 不是二次函数，但是它不会以有限的步数收敛，并且通常需要进行一些小的附加修改

涅斯特罗夫方法

对于数学优化和机器学习社区，“ Nesterov”这个名字早已是家喻户晓的名字。在上个世纪80年代，Yu.E。 Nesterov提出了一个有趣的惯性方法版本，其形式为

$x_ {k + 1} = x_k- \ alpha_k \ nabla f（x_k + \ beta_k（x_k-x_ {k-1}））+ \ beta_k（x_k-x_ {k-1}），$

它并不意味着任何复杂的计算

$\ alpha_k，\ beta_k$ 与共轭梯度法一样，该方法的行为通常与重球法相似，但无论从理论上还是在实践上，其收敛通常更为可靠。

随机梯度下降

与通常的梯度下降唯一的形式差异是使用函数而不是梯度

$g（x，\ theta）$ 这样

$E_ \ theta g（x，\ theta）= \ nabla f（x）$ （

$E_ \ theta$ -随机期望

$\ theta$ ），因此随机梯度下降的形式为

$x_ {k + 1} = x_k- \ alpha_kg（x_k，\ theta_k）。$

$\ theta_k$ -这是我们不会影响的一些随机参数，但平均而言，我们同时会违反渐变。例如，考虑功能

$f（x）= \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2，~~ \ nabla f（x）= \ frac {1} {m} \ sum_ {j = 1} ^ m（x-y_j）$

和

$g（x，i）= x-y_i。$

如果

$我$ 取值

$1，\ ldots，m$ 同样可能只是平均

$g$ 是渐变

$f$ 。该示例还指示以下内容：计算梯度的复杂度

$m$ 比计算复杂度高倍

$g$ 。这允许随机梯度下降在同一时间完成

$m$ 多次迭代。尽管事实上，随机梯度下降的收敛速度通常比平时慢，但由于迭代次数增加了很多，因此可以提高每单位时间的收敛速度。据我所知，目前随机梯度下降是训练大多数神经网络的基本方法，已在所有主要的ML库中实现：张量流，割炬，咖啡，CNTK等。

值得注意的是，惯性方法的思想用于随机梯度下降，并且在实践中通常会有所增加，理论上，通常假定渐近收敛速度不会改变，原因是随机梯度下降的主要误差是由于色散引起的。

$g$ 。

次梯度下降

这种变化使您可以使用不可微分的函数，我将对其进行详细描述。我们将不得不再次回忆一下线性近似-事实是，通过梯度存在一个简单的凸性特征，一个微分函数

$f$ 当且仅当

$f（y）\ geq f（x）+ \ nabla f（x）^ T（y-x）$ 对于所有

$x，y$ 。事实证明，凸函数不必是可微的，但是对于任何一点

$x$ 当然有这样的载体

$g$ 那

$f（y）\ geq f（x）+ g ^ T（y-x）$ 对于所有

$y$ 。这样的载体

$g$ 通常称为次梯度

$f$ 在这一点上

$x$ ，所有点的所有梯度的集合

$x$ 称为亚微分

$x$ 并表示

$\部分f（x）$ （尽管有名称-与偏导数无关）。在一维情况下

$g$ 是一个数字，以上属性仅表示该图

$f$ 位于通过线上方

$（x，f（x））$ 并有一个斜坡

$g$ （请参见下面的图片）。我注意到一点可以有多个次梯度，甚至是无限个。

通常很难为一个点计算至少一个子梯度；子梯度下降本质上是使用子梯度而不是梯度。事实证明，这足够了；理论上，收敛速度会降低，但是，例如，在神经网络中，不可微函数

$ReLU（x）= \最大值（0，x）$ 他们之所以喜欢使用它，只是因为它的训练速度更快（顺便说一句，这是一个非凸，不可微函数的示例，其中成功应用了（子）梯度下降。）

$Relu$ 包含凸但多层的神经网络

$Relu$ ，非凸且不可微）。例如，对于一个功能

$f（x）= | x |$ 亚微分的计算非常简单

$\部分f（x）= \开始{cases} 1，＆x> 0，\\ -1，＆x <0，\\ [-1，1]，＆x = 0。 \ end {cases}$

可能要知道的最后一件事是， 次梯度下降不会以恒定的步长收敛 。对于以上功能，这是最容易看到的。

$f（x）= | x |$ 。即使在某一时刻不存在导数也会破坏收敛：

假设我们从这一点开始 $x_0$ 。
次梯度下降步骤：
$x_ {k + 1} = \开始{cases} x_ {k} -1，＆x> 0，\\ x_k + 1，＆x <0，\\ ??? ＆x = 0。 \ end {cases}$
如果 $x_0> 0$ 那么前几步我们将减去一个，如果 $x_0 <0$ 然后添加。一种或另一种方式，我们有时会发现自己处于区间 $[0，1）$ 从那里我们 $[-1，0）$ ，然后我们将在这些间隔的两个点之间跳转。

理论上，对于次梯度下降，建议采取一系列步骤

$\ alpha_k = \ frac {1} {（k + 1）^ c}。$

哪里

$c$ 通常

$1$ 或

$\ frac {1} {2}$ 。在实践中，我经常看到成功的步骤

$\ alpha_k = e ^ {-ck}$ ，尽管从总体上讲，对于此类步骤将不会收敛。

近端方法

不幸的是，在优化的背景下，我对“近端”一词的翻译不甚了解，这就是为什么我只称这种方法。近端方法作为投影梯度方法的概括而出现。这个想法很简单：如果有一个功能

$f$ 表示为总和

$f（x）= \ varphi（x）+ h（x）$ 在哪里

$\ varphi$ 是微分凸函数，并且

$h（x）$ -凸面，为此需要特殊的近端操作员

$prox_h（x）$ （在本文中，我将仅局限于示例，我将不作一般性描述），然后针对

$\ varphi$ 保持和梯度下降

$f$ 如果在每次迭代之后将此近端运算符应用于当前点

$x_k$ ，换句话说，近端方法的一般形式如下：

$x_ {k + 1} =代理_ {\ alpha_kh}（x_k- \ alpha_k \ nabla \ varphi（x_k））$

我认为到目前为止，为什么这是必要的还完全无法理解，尤其是考虑到我没有解释近端操作员是什么。这是两个示例：

$h（x）$ -凸集的指标函数 $\数学{K}$ 那就是
$h（x）= \开始{cases} 0，＆x \ in \ mathcal {K}，\\ + \ infty，＆x \ notin \ mathcal {K}$

在这种情况下 $pro_ _ {\ alpha_kh}（x）$ 是布景的投影 $\数学{K}$ ，即“最接近 $x$ 设定点 $\数学{K}$ ”。因此，我们仅将梯度下降限制为集合 $\数学{K}$ ，这使我们能够解决限制问题。不幸的是，在一般情况下计算投影可能会更加困难，因此，如果约束很简单（例如，所谓的框约束），则通常使用此方法：对于每个坐标
$l_i \ leq x_i \ leq r_i$
$h（x）= \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i |$ -- $\ ell_1$ -正规化。他们喜欢将此术语添加到机器学习的优化问题中，以避免重新训练。这种正则化也倾向于使最不重要的成分无效。对于此类函数，近端运算符具有以下形式（以下描述了单个坐标的表达式）：
$[prox _ {\ alpha h}（x）] _ i = \开始{cases} x_i- \ alpha，＆x_i> \ alpha，\\ x_i + \ alpha，＆x_i <-\ alpha，\\ 0，＆x_i \以[-\ alpha，\ alpha]，\ end {cases}$

这很容易计算。

结论

这样就结束了我所知道的渐变方法的主要变化。也许最后我会注意到，所有这些修改（也许除了共轭梯度法之外）都可以轻松地相互影响。我故意不在此列表中包括Newton方法和准Newton方法（BFGS和其他方法）：尽管它们使用梯度，但它们是更复杂的方法，并且需要特定的附加计算，这些计算通常比计算梯度更昂贵。但是，如果需要此文本，我将很乐意对它们进行类似的审查。

数学优化问题中的梯度方法概述

前言

作者注