优化算法的目的是为了优化损失函数，损失函数衡量的是模型与数据的偏离程度，主要思想是计算损失函数关于参数的导数（多个参数时计算偏导数），然后沿__导数的负方向__迭代更新参数，一步步最小化损失函数。这类方法就叫做梯度下降法。
一阶优化算法
一阶优化算法只计算一阶偏导，写成矩阵就叫 Jacobian 矩阵。
1.随机梯度下降法SGD
Stochastic gradient descent
这里的随机梯度下降法特指 minibatch SGD。这里随机的意思就是每次随机从训练数据中选择一批数据计算梯度来更新参数。具体流程如下：
Require: 学习率 $\epsilon$
Require: 初始参数 $\theta$
while 未满足停止条件 do
从训练集中采样$m$个样本${x^{(1)}, …,x^{(m)}}$的小批量，其中$x^{(i)}$对应目标为$y^{(i)}$。
计算梯度：$g=\frac{1}{m} \nabla_\theta \sum_iL(f(x^{(i)}, \theta), y^{(i)})$ 其中$\sum_iL(f(x^{(i)}, \theta), y^{(i)})$是当前批样本的损失（误差）
应用更新：$\theta=\theta-\epsilon g$
end while
典型的流程如下（计算当前参数下的梯度，沿负梯度方向更新参数）：
但随机梯度下降法有个缺点，由于梯度越大更新步长越大，导致在峡谷类型的函数上收敛非常慢，会一直在比较陡的方向来回振荡。如图：
2.使用动量的随机梯度下降 Momentum
随机梯度下降法固然有用，但有时候导致收敛速度比较慢，想想一下在一个底比较平的碗里，由于碗底的梯度此时已很小，所以每次参数更新的幅度也特别小，导致算法需要很久才能到达极小值处。不过在碗壁处由于梯度大，所以更新幅度也大。所以可以很自然的想，可以保留在碗壁处的运动趋势，这样在碗底就有更快的速度即更大的参数更新幅度。这里就很容易联想到动量，动量是物体质量和速度的乘积，是物体在运动方向上保持运动的趋势（牛顿第一定律，惯性定律）。
由于有速度的物体都有动量，所以这里我们认为每次更新的参数的位置都有速度，当前时刻的速度会影响之后时刻的速度，当然假设物体是单位质量，运动时间是单位时间，而SGD则可以看做在任何位置都没有速度或者速度只使用一次便消失，各时刻互不影响。我们先看看物理问题中动量的运用。
假设从山坡上滚下来一个球（光滑无摩擦），受重力的影响，会一直加速直到到达水平面，每一时刻它都有山坡切线方向的速度，也就是有动量，这里我们计算在某一位置$S_{t-1}$经过单位时间后可以到达的位置$S_t$，如图所示：
由于模型并不严谨，所以计算不会太考虑细节。$S_t$的计算方式如下：
所以：
如果把上面的 $S$ 看做 $\theta$ ，把 $F$ 看做 $-g$ 即负梯度，就有：
这就是动量算法的基本思路，也可以从简单的角度理解，每次更新时都考虑历史更新值，历史更新值一直在累加，所以如果遇到每次更新值方向一致（近似）的情况，那即是当前梯度很小，由于历史累加也会在当前时间有较大的更新幅度，也就是说在碗底运动时使用了碗壁处积攒的动能，收敛速度更快，而且如果遇到峡谷类型的损失函数，也会一定程度上遏制在梯度大的方向上来回摆动，比如当前计算了梯度向左，而上一步计算的梯度是向右，两个梯度向加就可以减小当前更新的幅度，保持稳定，如图所示：
在具体实现阶段，需要考虑历史累积梯度和当前梯度的权重，整体流程如下：
Require: 学习率 $\epsilon$， 动量参数 $\alpha$
Require: 初始参数 $\theta$ ，初始速度 $v$
while 未满足停止条件 do
从训练集中采样$m$个样本${x^{(1)}, …,x^{(m)}}$的小批量，其中$x^{(i)}$对应目标为$y^{(i)}$。
计算梯度：$g=\frac{1}{m} \nabla_\theta \sum_iL(f(x^{(i)}, \theta), y^{(i)})$
计算速度：$v=\alpha v -\epsilon g$
应用更新：$\theta=\theta+v$
end while
具体流程参考下图：
由于动量算法考虑了之前的速度，所以它有可能冲过局部极小值，但是也有可能冲过全局最优值，在损失函数曲面情况较复杂的情况下，可能会多次冲过极小值又折返回来，使收敛不稳定，也会浪费时间。
3.自适应学习率算法Adagrad
前面的 SGD 和 Momentum 算法都是手动设置学习率 $\epsilon$ ,但是学习率往往难以设置却对训练过程影响很大，动量算法在一定程度上影响了学习率（$ \theta =\theta +v $ 而不是 $\theta=\theta-\epsilon g$ ） 但是却引入了新的动量参数。以上这些算法在所有参数上都使用了同一个学习率，但直观上来说，每个参数的学习率应该是独立的，应该在训练阶段自适应的调整每个参数的学习率。Adagrad就是一种实现方法，基本思想是，如果每个权重方向历史梯度很大，那么就该在这个方向减小学习率，以免越过极小点，同样，如果某个权重方向历史梯度较小，那么就可以在该方向使用大的学习率，加快收敛。Adagrad 使用所有历史梯度的平方和的平方根，所以在设定初始学习率的情况下，梯度较大的参数方向的学习率减小的很快，反之梯度较小的参数方向的学习率减小的比较慢，具体算法如下：
Require: 全局学习率 $\epsilon$
Require: 初始参数 $\theta$
Require: 小常数 $\delta$ ，为了数值稳定使用，大约设为$10^{-7}$
初始化梯度累积变量 $r=0$
while 未满足停止条件 do
从训练集中采样$m$个样本${x^{(1)}, …,x^{(m)}}$的小批量，其中$x^{(i)}$对应目标为$y^{(i)}$。
计算梯度：$g=\frac{1}{m} \nabla_\theta \sum_iL(f(x^{(i)}, \theta), y^{(i)})$
累积平方梯度：$r=r+g\bigodot g$ （对应元素相乘）
计算更新：$\Delta \theta = \frac{\epsilon}{\delta+\sqrt{r}} \bigodot g$ ，只看其中一个参数更新就是：$\Delta \theta^i=\frac{\epsilon}{\delta+\sqrt{\sum^t_{t=0}(g^i_t)^2}}g^i$
应用更新：$\theta=\theta+\Delta \theta$
end while
Adagrad算法还可以从二阶梯度分析，待续，主要参考李宏毅的Gradient Descent
虽然Adagrad效果不错，但是从一开始就累积梯度平方会导致有效学习率过早和过量的减小。
4.自适应学习率算法RMSProp
RMSProp是Adagrad的修改版，由于Adagrad使用了历史所有的梯度，所以很容易被历史梯度影响难以做出快速调整，这点与Momentum比较像，但是Momentum有动量参数参数来控制历史梯度的权重而Adagrad没有这个机制，增加了这个机制就是RMSProp了，控制历史梯度的权重可以更快的对梯度变化做出调整。
具体算法如下：
Require: 全局学习率 $\epsilon$ ，衰减速率 $\rho$
Require: 初始参数 $\theta$
Require: 小常数 $\delta$ ，为了数值稳定使用，通常设为$10^{-6}$
初始化梯度累积变量 $r=0$
while 未满足停止条件 do
从训练集中采样$m$个样本${x^{(1)}, …,x^{(m)}}$的小批量，其中$x^{(i)}$对应目标为$y^{(i)}$。
计算梯度：$g=\frac{1}{m} \nabla_\theta \sum_iL(f(x^{(i)}, \theta), y^{(i)})$
累积平方梯度：$r=\rho r+(1-\rho)g\bigodot g$ （对应元素相乘）
计算更新：$\Delta \theta = \frac{\epsilon}{\delta+\sqrt{r}} \bigodot g$ ，只看其中一个参数更新就是：$\Delta \theta^i=\frac{\epsilon}{\delta+\sqrt{\sum^t_{t=0}(g^i_t)^2}}g^i$
应用更新：$\theta=\theta+\Delta \theta$
end while
5.自适应学习率算法Adam
Adam 结合了RMSProp和Momentum
具体算法如下：
Require: 全局学习率 $\epsilon$ （建议默认为0.001)
Require: 矩估计的指数衰减速率，$\rho_1$ 和 $\rho_2$ 在区间 [0,1) 内（建议默认分别为0.9和0.999）
Require: 初始参数 $\theta$
Require: 小常数 $\delta$ ，为了数值稳定使用，通常设为$10^{-6}$
初始化一阶和二阶矩变量 $s=0$ ， $r=0$
初始化时间步 $t=0$
while 未满足停止条件 do
从训练集中采样$m$个样本${x^{(1)}, …,x^{(m)}}$的小批量，其中$x^{(i)}$对应目标为$y^{(i)}$。
计算梯度：$g=\frac{1}{m} \nabla_\theta \sum_iL(f(x^{(i)}, \theta), y^{(i)})$
$t = t+1$
更新有偏一阶矩估计(速度)：$s=\rho_1s+(1-\rho_1)g$
更新有偏二阶矩估计(累积平方梯度)：$r=\rho_2 r+(1-\rho_2)g\bigodot g$ （对应元素相乘）
修正一阶矩的偏差：$\hat{s}=\frac{s}{1-\rho_1^t}$
修正二阶矩的偏差：$\hat{r}=\frac{r}{1-\rho_2^t}$
计算更新：$\Delta \theta =- \epsilon \frac{\hat{s}}{\delta+\sqrt{\hat{r}}} $ （逐元素应用操作）
应用更新：$\theta=\theta+\Delta \theta$
end while
Adam论文中给出的与其他优化算法的比较：
6.各算法比较
二阶优化算法
二阶优化算法只计算二阶偏导，写成矩阵就叫 Hessian 矩阵。
最简单的二阶优化算法 牛顿法 ，寻找函数的临界点，临界点有可能是极大极小点，也可能是鞍点，但是鞍点是不可取的，只有是极小点也就是Hessian矩阵正定时牛顿法才是适用的，不然牛顿法很可能找到鞍点而停止。
由于牛顿法这种寻找梯度为零（临界点）的点的性质，导致无法成功运用在神经网络的训练中。因为高维空间中有更多的鞍点。而低维空间的局部极小值更普遍。直观上来理解：假设某个点每个二阶偏导都大于零说明这个点是极小点，假设由抛硬币决定二阶导数的正负，那在二维空间中某个点是极小点的概率就是$1/21/2=1/4$ 那在高维如五维空间中这个点是极小点的条件就是各个偏导都大于零，概率是$1/21/21/21/2*1/2=1/32$ 而只有其中一个偏导大于零的情况就比较常见。
高维空间中鞍点的激增或许就解释了在神经网络训练中为什么二阶方法无法成功取代梯度下降法。（《深度学习》8.2）
