优化算法

对目标函数求梯度 $\nabla_{\theta} J(\theta)$

批量梯度下降

利用所有训练数据，计算目标函数梯度，$\eta$是学习率(learning rate)

$$\theta = \theta - \eta \cdot \nabla_{\theta} J(\theta)$$

缺点：一次参数更新需要计算整体数据的梯度，内存消耗大，不支持模型在线更新

随机梯度下降

训练中，利用一个样本$x^{(i)}$ 和标签 $y^{(i)}$进行一次参数更新

$$\theta = \theta - \eta \cdot \nabla J(\theta;x^{(i)};y^{(i)})$$

优点：

• 速度快，支持在线学习

缺点：

• 高方差，目标函数值剧烈波动
• 随机波动，容易陷入局部极小值

mini-batch 随机下降

结合前两种，在训练中，利用一个 batch 样本$x^{(i)}$ 和标签 $y^{(i)}$进行一次参数更新

$$\theta = \theta - \eta \cdot \nabla J(\theta;x^{(i:i+n)};y^{(i:i+n)})$$

优点：

• 减小参数更新的方程，收敛更平稳
• 可以根据内存来控制输入

Momentum

帮助SGD在相关方向上加速并抑制震荡，当前向量 $v_{t}$ 的更新考虑了上一个时刻向量 $v_{t-1}$ 的作用

$$\left\{ \begin{aligned} v_t & = &\underbrace{\gamma v_{t-1}}_{momenturm \,term} &+& \eta \cdot \nabla_{\theta} J(\theta)\\ \theta & = &\theta &-& v_t \\ \end{aligned} \right.$$

Nesterov accelerated gradient(NAG)

给momentum term引入先验

$$\left\{ \begin{aligned} v_t & = \gamma v_{t-1} + \eta \cdot \nabla_{\theta} J(\theta - \gamma v_{t-1})\\ \theta & = \theta - v_t \\ \end{aligned} \right.$$

AdaGrad

之前的方法对所有参数$\theta$都用了相同的学习率$\eta$，AdaGrad在时刻$t$对每个参数$\theta_i$采用了不同的学习速率$\eta$
$\theta_i$在$t$时刻的梯度：

$$g_{t,i} = \nabla_\theta J(\theta_i)$$

SGD对在$t$时刻的参数$\theta_i$更新，

$$\theta_{t+1, i} = \theta_{t,i} - \eta \cdot g_{t,i}$$

AdaGrad在$t$时刻的参数$\theta_i$更新，

$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_{t,i} + \epsilon}} \cdot g_{t,i}$$

其中，$G_{t} \in \mathbb{R}^{d \times d}$是一个对角矩阵，对角元素$i$是每个参数$\theta_i$到t时刻为止，所有时刻梯度的平方之和，$\epsilon$为避免分母为0。
进一步，写成element-wise matrix-vector multiplication形式，

$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_{t} + \epsilon}} \odot g_{t}$$

优点

• 不用人工调整学习率，默认0.01

缺点

• 在分母中累积梯度的平方，在训练过程中导致学习率一直在减小
• 需要手动设置一个全局初始学习率
• 更新$\theta_t$时，左右两边的单位不一致

Adadelta

为缓解AdaGrad学习率单调递减问题做出的扩展。不对过去所以时刻梯度平方累积，将累积时刻限制在窗口大小为$w$的区间
递归使得定义为过去所有时刻梯度平方的decaying average(?)。时刻$t$的running average $E[g^2]_t$仅仅依赖于之前average和当前的梯度
$\gamma$是一个衰减系数，随着时间指数衰减，因此与当前时刻比较近的$g_t$对梯度计算更起作用

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

将对角矩阵$G_t$替换为过去$t$时刻梯度平方的dacaying average $E[g^2]_t$

$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{E[g^2]_t + \epsilon}} \odot g_{t}$$

RMSprop

和Adadelta原理相似？？？

Adam

Adaptvie Moment Estimation (Adam) 自适应学习速率计算方法。保存过去梯度平方和+momentum。

$$m_t=\beta_1 m_{t-1} + (1 - \beta_1) g_t\\ v_t = \beta_2 v_{t - 1} + (1 - \beta_2) g_t^2$$

其中，$m_t$和$v_t$分别是梯度的一阶矩（均值）和二阶矩（偏方差）的估计
为消除估计值的偏差，计算bias-corrected

$$\widehat{m}_t = \frac{m_t}{1-\beta^t_1}\\ \widehat{v}_t = \frac{v_t}{1 - \beta^t_2}$$

更新规则，

$$\theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\widehat{v}_t + \epsilon}} \widehat{m}_t$$

默认设置，$\beta_1 = 0.9,\beta_2=0.999,\epsilon=10^{-8}$

---

【各优化算法对比-投影面】

---