梯度下降法推导与改进

符号说明

$\text{x},{\text{x}}_0,{\text{x}}_t,△\text{x}$都是nx1的列向量。
${\text{x}}_{t,i}$代表向量${\text{x}}_t$的第i个元素，是个常量。
$f(\text{x})$为$\text{x}$的函数，是一个常量。

---

基本思想

梯度下降法的基本思想非常简单，想象一下自己在一个盆地中，现在需要进入到盆地最底部，那么最简单的方式就是一直往下走，直到不能再向下走为止，此时就到达了盆地最底部。那么对于一个复杂的函数而言，找到一个合适的公式去描述这一简单的思想，就可以求出函数的极小值位置了。

---

算法推导

高维函数带有佩亚诺余项的一阶泰勒展开式如下
$$f(\text{x})=f({\text{x}}_0)+▽{f({\text{x}}_0)}^T(\text{x}-{\text{x}}_0)+o(||\text{x}-{\text{x}}_0||)$$
令$\text{x}={\text{x}}_0+△\text{x}$
$$f({\text{x}}_0+△\text{x})-f({\text{x}}_0)=▽{f({\text{x}}_0)}^T△\text{x}+o(||△\text{x}||)$$
假设${\text{x}}_0$处是极小值位置
那么下式成立
$$\underset{||△\text{x}||\to 0}{\lim }f({\text{x}}_0+△\text{x})-f({\text{x}}_0)>0\text{\hspace{1em}(1.1)}$$
$⟺$
$$\underset{||△x||\to 0}{\lim }\frac{▽{f({\text{x}}_0)}^T△\text{x}}{||△\text{x}||}+\underset{△\text{x}\to 0}{\lim }\frac{o(||△\text{x}||)}{||△\text{x}||}>0\text{\hspace{1em}(1.2)}$$
$⟺$
$$\underset{||△x||\to 0}{\lim }\frac{▽{f({\text{x}}_0)}^T△\text{x}}{||△\text{x}||}>0\text{\hspace{1em}(1.3)}$$
$⟺$
$$\underset{||△x||\to 0}{\lim }▽{f({\text{x}}_0)}^T△\text{x}>0\text{\hspace{1em}(1.4)}$$
可以得到如果两个向量$▽f({\text{x}}_0)$与$△\text{x}$同向那么满足推导(4)，同样也满足公式(1)
$$\underset{||△\text{x}||\to 0}{\lim }△\text{x}=\alpha ▽f({\text{x}}_0),\alpha >0$$
令$△\text{x}={\text{x}}_t-{\text{x}}_{t+1}$，若要使$▽f({\text{x}}_t)$与其同向，只需要一个可收敛的递推式（可收敛很重要）
$${\text{x}}_t-{\text{x}}_{t+1}=\alpha ▽f({\text{x}}_t),\alpha >0$$
得到最终的梯度下降递推式如下
$${\text{x}}_{t+1}={\text{x}}_t-\alpha ▽f({\text{x}}_t),\alpha >0,t=1,2,3,\cdots \text{\hspace{1em}(1.5)}$$
推导过程中假设条件为极小值，那么对于求极大值的情况常常在函数前面加一个负号，转换成求极小值的情况。
在应用中也会发现，有些存在极值的函数利用梯度下降无法求出极值，一般是$\alpha$取值或者函数本身的问题导致递推式无法收敛。从推导过程中可以看出，如果这个递推式不收敛，那么就不会满足推导(4)从而无法利用这个方法求极值。

---

算法改进

Polysk’s Classical Momentum算法
简称为CM算法，可以加速梯度下降法，递推公式如下
$${\text{x}}_{t+1}={\text{x}}_t+{\text{v}}_{t+1}\text{\hspace{1em}(2.1)}$$
$${\text{v}}_{t+1}=u{\text{v}}_t-\alpha {▽}_{{\text{x}}_t}f,u\in [0,1)\text{\hspace{1em}(2.2)}$$
利用公式(2.2)对公式(2,1)展开，
$${\text{v}}_{t+1}={\text{u}}^{t+1}{\text{v}}_0-\alpha {\text{u}}^t{▽}_{{\text{x}}_0}f-\alpha {\text{u}}^{t-1}{▽}_{{\text{x}}_1}f\cdots -\alpha {▽}_{{\text{x}}_t}f\text{\hspace{1em}(2.3)}$$
$${\text{x}}_{t+1}={\text{x}}_t+{\text{v}}_{t+1}\text{\hspace{1em}(2.4)}$$
一般而言，${\text{u}}^{t+1}{\text{v}}_0$（一般为0向量）对${\text{v}}_{t+1}$的方向影响几乎可以忽略，若该递推式是收敛的，那么该公式满足递推(1.4)，那么该递推式可以求出极值点，而且${\text{v}}_{t+1}$变化量明显大于$-\alpha {▽}_{{\text{x}}_t}f$所以当选取的初始迭代点${\text{x}}_0$距离极值点较远时能够较快地达到收敛位置。但是缺点是会在即将到达收敛的时候在极值点附近来回震荡，所以也有可能导致更多的迭代步骤。

左侧为梯度下降法的迭代示例，右侧为CM算法迭代步骤。与之前的分析一致。

Nesterov’s Accelerated Gradient算法
简称为NAG算法，也可以对对梯度下降法进行加速，其递推式如下
$${\text{x}}_{t+1}={\text{x}}_t+{\text{v}}_{t+1}\text{\hspace{1em}(2.5)}$$
$${\text{v}}_{t+1}=u{\text{v}}_t-\alpha {▽}_{{\text{x}}_t+{\text{v}}_t}f,u\in [0,1)\text{\hspace{1em}(2.6)}$$
与CM算法相比，求梯度的位置不一样，CM算法是对当前的位置${\text{x}}_t$的求梯度，NAG算法是对即将到达的下一个位置${\text{x}}_t+{\text{v}}_t$求梯度，仅仅这一点的改变就可能会使其迭代步骤低于CM算法。

Adgard算法

迭代公式如下
$${\text{x}}_{t+1,i}={\text{x}}_{t,i}-\frac{\alpha }{\sqrt{G_{t,i}+ϵ}}{▽}_{{\text{x}}_{t,i}}f\text{\hspace{1em}(2.7)}$$
$$G_{t,i}=\sum _{i=0}^{i=t}{▽}_{{\text{x}}_{t,i}^2}f\text{\hspace{1em}(2.8)}$$
随着迭代步骤t的增加，与梯度下降法中的$\alpha$相比，Adgard算法中的系数$\frac{\alpha }{\sqrt{G_{t,i}+ϵ}}$越来越小，这种求解方式有效地减少了在极值点附近的震荡次数，但是如果选取的初始点距离极值点附近比较远，迭代次数将大幅上升。

RMSprop算法

该算法主要针对Adgard算法在极值点附近震荡过多，而提出的，迭代公式如下
$${\text{x}}_{t+1,i}={\text{x}}_{t,i}-\frac{\alpha }{\sqrt{g_{t,i}+ϵ}}{▽}_{{\text{x}}_{t,i}}f\text{\hspace{1em}(2.9)}$$
$$g_{t,i}=\gamma G_{t-1,i}+(1-\gamma )G_{t,i}\text{\hspace{1em}(2.10)}$$
$$G_{t,i}=\sum _{i=0}^{i=t}{▽}_{{\text{x}}_{t,i}^2}f\text{\hspace{1em}(2.11)}$$
添加公式(2.10)，可以缓解在极值点附近的震荡次数。

Adam算法

前面我们提到CM算法与NAG算法减少迭代次数，但是在极值点附近常常出现过多的震荡，RMSprop算法与Adam算法可以有效降低这种震荡，但是开始的迭代次数比较多。所以有人就思考将两者结合起来，总体思想就是将CM算法作为分子，Adgard算法作为分母，期望达到在离极值点较远的时候分子不断增加从而减少初始迭代步骤，在离极值点较近的时候分母不断增加从而减少震荡的目的，由于公式过于臃肿，而且参数过多，导致本人不愿意敲打该公式，所以将原论文(Adam: A Method for Stochastic Optimization)中的伪代码粘贴到下面以表敬意。