各类优化方法总结（从SGD到FTRL）

本文主要是介绍各类优化方法总结（从SGD到FTRL），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

各类优化方法总结

为了方便描述，假设第 $t$ 轮要更新的某参数是 $w_t$ ， $loss$ 函数关于 $w_t$ 的偏导数表示为 $g_t$ ，即：

g t = \partial L \partial w t

$g_t=\frac{\partial L}{\partial w_t}$

1. SGD

w t = w t - 1 - η \cdot g t

$w_t=w_{t-1}-\eta \cdot g_t$
可以对一个样本都计算一次梯度并更新一次参数，也可以先对一整个

batch b a t c h $batch$ 一起计算梯度，再更新参数（称为batch-SGD）。

优点

简单

缺点

所有的参数使用同样的学习率 $\eta$ ，不够灵活
容易陷入局部最优
需要人工设定 $\eta$

2. Momentum

m t = μ \cdot m t - 1 + g t w t = w t - 1 - η \cdot m t

$m_t=\mu \cdot m_{t-1} + g_t\\ w_t = w_{t-1}-\eta \cdot m_t$
实际上就是用加权累积的梯度代替本轮梯度，每次的更新方向并不是纯粹的梯度，而是要加上上一次迭代的一部分。可以将第

t t $t$ 轮的梯度看成下面这个式子，显然越早期的梯度贡献越小。

m_{t} = \sum_{i = 1}^{t} μ^{t - i} g_{i}

$m_t = \sum_{i=1}^t \mu^{t-i}g_i$
此外，将

Δwt Δ w t $\Delta w_t$ 展开得到

Δwt=−η⋅mt=−η⋅μ⋅mt−η⋅gt Δ w t = − η ⋅ m t = − η ⋅ μ ⋅ m t − η ⋅ g t $\Delta w_t=-\eta \cdot m_t=-\eta \cdot \mu \cdot m_t - \eta \cdot g_t$ ，可以看到momentum不会直接改变当前梯度

gt g t $g_t$ 。

优点
momentum在前后梯度一致时有利于加速收敛，不一致时能做方向纠正，同时减少陷入局部最优。

在前后两次梯度方向比较接近时（一般是训练初期），前后两次在相近的方向上叠加，能够加速训练。
在前后两次梯度方向相差很远时（训练后期在局部最小附近来回震荡），虽然 $g_t$ 可能很小，但是有历史梯度的累积在， $m_t$ 不至于太小，有利于跳出局部最优。

缺点

仍然需要人工设定 $\eta$

3. Nesterov

g t = ▿ f (w t - 1 - η \cdot μ \cdot m t - 1)

$g_t=\triangledown f(w_{t-1}-\eta\cdot\mu\cdot m_{t-1})$

m t = μ \cdot m t - 1 + g t w t = w t - 1 - η \cdot m t

$m_t=\mu \cdot m_{t-1} + g_t\\ w_t = w_{t-1}-\eta \cdot m_t$

可以看到，Nesterov只是在Momentum的基础上，修改了当前梯度 $g_t$ ，让历史累积的梯度 $m_{t-1}$ 也影响到当前的梯度 $g_t$ 。

缺点

仍然需要人工设定 $\eta$

4. Adagrad

n t = n t - 1 + g 2 t w t = w t - 1 - η n t + ϵ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt \cdot g t

$n_t=n_{t-1}+g_t^2\\ w_t = w_{t-1}-\frac{\eta}{\sqrt{n_t+\epsilon}} \cdot g_t$

$n_t$ 其实是 $\sum_i^tg_i^2$ ，对于稀疏梯度，该平方和一般会比较小，使得参数的学习率偏大，对于非稀疏梯度，该平方和一般比较大，使得参数学习率偏小。因此Adagrad适合用来处理稀疏梯度。

优点

每个参数都有自己的学习率。
训练初期 $g_t$ 平方和比较小，学习率较大，能够加速训练
训练后期 $g_t$ 平方和比较大，学习率较小，能够约束梯度
适合处理稀疏梯度

缺点

仍然需要人工设定 $\eta$
训练后期平方和太大，使得梯度 $\rightarrow 0$ ，容易导致训练提前结束

5. Adadelta

E [g 2] t = v \cdot E [g 2] t - 1 + (1 - v) \cdot \cdot g 2 t

$E[g^2]_t = v\cdot E[g^2]_{t-1}+(1-v)\cdot \cdot g_t^2$

w t = w t - 1 - \sum t - 1 r = 1 ( w r - w r - 1 ) ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt E [ g 2 ] t + ϵ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt

$w_t=w_{t-1}-\frac{\sqrt{\sum_{r=1}^{t-1}(w_r-w_{r-1})}}{\sqrt{E[g^2]_t+\epsilon}}$

为了减轻Adagrad梯度衰减过快的问题，Adadelta用历史梯度平方的集权均值代替平方和。

优点

具有Adagrad的优点
不需要人工设定 $\eta$
缓解了Adagrad梯度衰减过快的问题

6. Adam

m t = μ \cdot m t - 1 + (1 - μ) \cdot g t n t = v \cdot n t - 1 + (1 - v) \cdot g 2 t

$m_t=\mu\cdot m_{t-1} +(1-\mu)\cdot g_t\\n_t=v\cdot n_{t-1} +(1-v)\cdot g_t^2$

m ̂ t = m t 1 - μ n ̂ t = n t 1 - v

$\hat{m}_t=\frac{m_t}{1-\mu}\\\hat{n}_t=\frac{n_t}{1-v}$

w t = w t - 1 - m ̂ t n ̂ t + ϵ ‾ ‾ ‾ ‾ ‾ ‾ \sqrt

$w_t=w_{t-1}-\frac{\hat{m}_t}{\sqrt{\hat{n}_t+\epsilon}}$

$m_t$ 和 $n_t$ 可以分别看作对历史梯度的一阶和二阶矩估计，即对期望 $E[g]_t$ 和 $E[g^2]_t$ 的估计， $\hat{m}_t$ 和 $\hat{n}_t$ 的处理是校正为无偏估计。

优点

实际上只需要保存梯度的均值，所以基本不需要额外的内存
不需要人工设定全局学习率 $\eta$
有观点认为，RNN使用Adam速度快，效果好

7. FTRL

w t + 1 = arg min w (g 1 : t \cdot w + 1 2 \sum s = 1 t σ s | | w - w s | | 22 + λ 1 | | w | | 1)

$w_{t+1}=\arg \min_w \left ( g_{1:t}\cdot w + \frac{1}{2}\sum_{s=1}^t \sigma_s ||w-w_s||_2^2 + \lambda_1||w||_1 \right )$
主要用于CTR预测的在线训练，成千上万维度导致大量稀疏特征。一般希望模型参数更加稀疏，但是简单的L1正则无法真正做到稀疏，一些梯度截断方法（TG）的提出就是为了解决这个问题，在这其中FTRL是兼备精度和稀疏性的在线学习方法。FTRL的基本思想是将接近于0的梯度直接置零，计算时直接跳过以减少计算量。

这里给出工程上的伪代码，里面的四个参数是可调的，具体原理尚且没时间看懂，以后有时间的话研究一下Google那篇论文。
这里写图片描述