泰勒公式视角下的梯度下降法和牛顿法

泰勒公式视角下的梯度下降法[1]

梯度下降法的目标是使得$f(x_t+\Delta x )<f(x_t)$,由泰勒公式可知,$f(x)$在$x_t$点的一阶泰勒展开为:

又$x_{t+1}$可等价写作$x_t + \Delta x$,则上式可化为:

所以要想使得$f(x_t+\Delta x)$<$f(x_t)$,$f’(x_t)\cdot\Delta x$必须小于0,此时$f’(x_t)$为定值,$\Delta x$为可变部分,于是可以令$\Delta x = -\eta \cdot f’(x_t)$,其中$\eta>0$,则

由此可以推得当$\Delta x = -\eta \cdot f’(x_t)$时,$f(x_t+\Delta x )<f(x_t)$恒成立。

泰勒公式视角下的牛顿法[2]

对于无约束的凸优化问题

其中$\boldsymbol{x}^*$为目标函数的最小值点,也是极小值点,牛顿法利用极小值点的必要条件

从点$\boldsymbol{x}^t$开始,求$ f(\boldsymbol{x})$在$\boldsymbol{x}^t$点的二阶泰勒展开式的极小值点(仅当$\boldsymbol{x}^{t}$点的Hessian矩阵为正定矩阵时),作为下一次(第$t+1$次)的迭代值$\boldsymbol{x}^{t+1}$,直到某次迭代值$\boldsymbol{x}^{t+1}$使得$\parallel\nabla f(\boldsymbol{x}^{t+1})\parallel<\epsilon$时停止迭代,其中$\epsilon$为自定义的精度要求,具体迭代步骤如下,由多元函数的泰勒展开式[3]可得$f(\boldsymbol{x})$在$\boldsymbol{x}^{t}$点的二阶泰勒展开式为:

其中$g_t$为$f(\boldsymbol{x})$在$\boldsymbol{x}^{t}$点的梯度值,$H_t$为$f(\boldsymbol{x})$在$\boldsymbol{x}^{t}$点的Hessian矩阵。对上式求导并令其等于$\boldsymbol{0}$可得:

解得$\boldsymbol{x}=\boldsymbol{x}^t-H_t^{-1}g_t$,令其为下一次的迭代值,即$\boldsymbol{x}^{t+1}=\boldsymbol{x}^t-H_t^{-1}g_t$。
【注】:

  • 牛顿法也是经典的求根算法,在求根时是一阶算法,在求最优化问题时是二阶算法,具体参见[4]
  • 关于牛顿法和梯度下降法的效率对比:从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径[5]

    红色为牛顿法的迭代路径,绿色为梯度下降法的迭代路径

参考文献:

[1] 梯度下降法 —— 经典的优化方法
[2] 李航.《统计学习方法》
[3] 多元函数的泰勒(Taylor)展开式
[4] 牛顿法到底是一阶优化算法还是二阶优化算法?
[5] 常见的几种最优化方法