问题引出

  李航大神在《统计学习方法》中指出使用一种机器学习方法的三要素由模型、策略和算法组成（这时读者可以想象一下最基本的LR和SVM方法中的三要素都是些什么）。而三要素中的"算法"指的就是求解最优化问题中的优化算法。有关优化问题，在面试中经常问到的就是梯度下降法、牛顿法与拟牛顿法的相关知识。

正文

  设如式$(1)$(1)所示的无约束优化问题：
$\mathop {\min }\limits_{x \in {R^n}} f\left( x \right) \tag{1}$x∈Rnmin​f(x)(1)
  $f(x)$f(x)在$x_k$xk​点的一阶导数如式$(2)$(2)所示，二阶导数的Hessian矩阵如式$(3)$(3)所示：

$g_k=f'({x_k}) = \left( {{{\partial f\left( {{x_k}} \right)} \over {\partial {x_1}}},{{\partial f\left( {{x_k}} \right)} \over {\partial {x_2}}}, \ldots ,{{\partial f\left( {{x_k}} \right)} \over {\partial {x_n}}}} \right) \tag{2}$gk​=f′(xk​)=(∂x1​∂f(xk​)​,∂x2​∂f(xk​)​,…,∂xn​∂f(xk​)​)(2)

$H_k^{-1}=f^{\prime\prime}{\left( x_k \right)^{ - 1}}=\begin{pmatrix} \frac {\partial ^2 f(x_k)} {\partial ^2 x_1^2} & \cdots& \frac {\partial ^2 f(x_k)} {\partial x_1 \partial x_n} \\ \vdots&\frac {\partial ^2 f(x_k)} {\partial x_i \partial x_j} & \vdots \\ \frac {\partial ^2 f(x_k)} {\partial x_n \partial x_1} & \cdots& \frac {\partial ^2 f(x_k)} {\partial ^2 x_n^2} \\ \end{pmatrix} \tag{3}$Hk−1​=f′′(xk​)−1=⎝⎜⎜⎜⎛​∂2x12​∂2f(xk​)​⋮∂xn​∂x1​∂2f(xk​)​​⋯∂xi​∂xj​∂2f(xk​)​⋯​∂x1​∂xn​∂2f(xk​)​⋮∂2xn2​∂2f(xk​)​​⎠⎟⎟⎟⎞​(3)

1. 梯度下降法(Gradient Descend,GD):

  梯度下降法是最为常用的一种简单优化方法。当目标函数是凸函数时，梯度下降法的解是全局解。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快的下降方向，所以也被称为是”最速下降法“。
  梯度下降法的求解公式如式$(4)$(4)所示：
$x_{k+1}=x_{k}+\lambda p_k \tag{4}$xk+1​=xk​+λpk​(4)
式中$\lambda$λ为超参数步长，$p_k=-g_k$pk​=−gk​为梯度的负方向，$g_k$gk​如式$(2)$(2)所示。
  根据样本的利用情况，梯度下降法又分为批量梯度下降法(Batch Gradient Descend,BGD)，随机梯度下降法(Stochastic Gradient Descent,SGD)和小批量梯度下降法(mini-Batch Gradient Descend,mini-BGD)。在以后得专题中再介绍三者的区别。

2. 牛顿法:

  牛顿法我记得在研究生数值分析那门课里讲到过。首先得明确，牛顿法是为了求解函数值为零的时候变量的取值而设计的算法。而在优化问题中，其是通过求解目标函数一阶导数为零的参数值从而间接使用牛顿法。
  牛顿法的求解公式如式$(5)$(5)所示：
$x_{k+1}=x_{k}-\lambda g_kH_k^{-1} \tag{5}$xk+1​=xk​−λgk​Hk−1​(5)
式中$\lambda$λ为超参数步长，$g_k$gk​如式$(2)$(2)所示，$H_k^{-1}$Hk−1​如式$(3)$(3)所示。

3. 拟牛顿法:

  牛顿法每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。拟牛顿法的提出就是为了改善原始牛顿法每次都需要求解复杂的Hessian矩阵的逆矩阵的缺陷。它使用一个正定矩阵来近似Hessian矩阵的逆，从而简化了运算的时间复杂度。
$x_{k+1}=x_{k}-\lambda g_kG_k \tag{6}$xk+1​=xk​−λgk​Gk​(6)
式中$\lambda$λ为超参数步长，$G_k$Gk​为$H_k^{-1}$Hk−1​的近似替代矩阵。
  常用的拟牛顿方法主要有DFP、BFGS和Broyden等几类算法，具体的步骤可以参照李航老师的《统计学习方法》，这里不再赘述。

总结

  文献中总说牛顿法比梯度下降法收敛速度快，是因为牛顿法是利用二阶导数更新迭代，而梯度下降法只利用了一阶导数来更新。但是为什么利用二阶导数更新就会比一阶快呢？不能人云亦云，还是需要冷静的思考一下本质上的原因。笔者认为原因主要有两点:(1)牛顿法设计的初衷就是直接令目标函数的一阶导数为零来求得极值，只是在求一阶导数为零的过程中，会存在误差，故采用迭代的方法来逼近。而梯度下降法只是采用当前的梯度值来更新参数从而求得极值。从算法原理上牛顿法就比梯度下降法更直接。(2)牛顿法中利用了目标函数的二阶导数信息，这就不光能保证目标值下降的快，还能保证目标值下降速度也变化的快，这就是引入二阶导数信息的好处。
  在深度学习中，梯度下降法应用较多，牛顿法一般不用在深度学习中。而在深度学习中还有momentum、rmsprop、adam、adagrad等优化方法，这些将留在后面专题中介绍。
  通过本文的介绍，可以看出梯度下降法是利用的是目标函数的一阶导数信息来更新参数而牛顿法是利用其二阶导数信息，理解梯度下降法和牛顿法的联系与区别也会帮助我们看清GBDT与XgBoost。

参考文献

[1] https://www.cnblogs.com/shixiangwan/p/7532830.html
[2]《统计学习方法》 李航