优化算法总结

认为优化算法可以分为三部分：

1. 批量部分
2. 更新部分
3. 调整学习率部分

1 批量部分

GD: 最初的算法为梯度下降（GD），对所有样本损失的平均作反向更新

$\mathbf g_t=\dfrac1{|I|}\sum\limits_{i\in I}\nabla\mathcal l_i(x_{t-1})$

2 更新部分

主要调整步进的方式，方法之间的关系与更迭的逻辑如图，具体算法见下：

Momentum：

$\mathbf v_t=\beta\mathbf v_{t-1}+\mathbf g_t$
$\mathbf w_t = \mathbf w_{t-1}-\eta\mathbf v_t$

AdaGrad:

$\mathbf s_t=\mathbf s_{t-1}+\mathbf g_t^2$
$\mathbf w_t=\mathbf w_{t-1}-\dfrac\eta{\sqrt{\mathbf s_t+\epsilon}}\cdot \mathbf g_t$

RMSProp:

$\mathbf s_t=\gamma\mathbf s_{t-1}+(1-\gamma)\mathbf g_t^2$
$\mathbf w_t=\mathbf w_{t-1}-\dfrac\eta{\sqrt{\mathbf s_t+\epsilon}}\cdot \mathbf g_t$

Adadelta:

$\mathbf s_t=\gamma\mathbf s_{t-1}+(1-\gamma)\mathbf g_t^2$
$\mathbf w_t=\mathbf w_{t-1}-\mathbf g’t$
$\mathbf g’t=\dfrac{\sqrt{\Delta\mathbf x{t-1+}\epsilon}}{\sqrt{\mathbf s_t+\epsilon}}\cdot \mathbf g_t$
$\Delta \mathbf x{t}=\lambda\Delta\mathbf x_{t-1}+(1-\lambda)\mathbf g’^{2}_{t}$

Adam:

估算动量和二阶矩：
$\mathbf v_t=\beta_1\mathbf v_{t-1}+(1-\beta_1)\mathbf g_t$
$\mathbf s_t=\beta_2\mathbf s_{t-1}+(1-\beta_2)\mathbf g_t^2$

无偏化处理:
$\hat{\mathbf{v}}_t = \dfrac{\mathbf v_t}{1-\beta_1^t}$
$\hat{\mathbf{s}}_t = \dfrac{\mathbf s_t}{1-\beta_2^t}$
更新：
$\mathbf g’_t=\dfrac{\eta\mathbf {\hat{\mathbf v}_t}}{\sqrt{\hat{\mathbf s}t}+\epsilon}$
$\mathbf x_t = \mathbf x{t-1}-\mathbf g’_t$

3 学习率部分

最简单的是固定学习率

• 随迭代轮数减少学习率

  • 单因子调度器：$\eta_{t+1}=\eta_t\cdot\alpha$

    为了防止衰减过度，一般使用：$\eta_{t+1}=\max(\eta_{\min},\eta_t\cdot \alpha)$

  • 多因子调度器：$s={5,10,20},t\in s时，\eta_{t+1}=\eta_t\cdot\alpha$

  • 余弦调度器：$\eta_t=\eta_T+\dfrac{\eta_0-\eta_T}2(1+\cos(\pi t/T))$，$t>T$后不更新

• 增加预热期

  • 线性增加

Optimization algorithms can be divided into three parts:

1. Batch processing part
2. Update part
3. Learning rate adjustment part

1 Batch Processing Part

GD: The original algorithm is gradient descent (GD), which performs backward updates using the average loss of all samples.

$\mathbf g_t=\dfrac1{|I|}\sum\limits_{i\in I}\nabla\mathcal l_i(x_{t-1})$

2 Update Part

This part mainly adjusts the step size. The relationships and evolution logic between methods are shown in the figure below; specific algorithms are listed as follows:

Momentum:

$\mathbf v_t=\beta\mathbf v_{t-1}+\mathbf g_t$
$\mathbf w_t = \mathbf w_{t-1}-\eta\mathbf v_t$

AdaGrad:

$\mathbf s_t=\mathbf s_{t-1}+\mathbf g_t^2$
$\mathbf w_t=\mathbf w_{t-1}-\dfrac\eta{\sqrt{\mathbf s_t+\epsilon}}\cdot \mathbf g_t$

RMSProp:

$\mathbf s_t=\gamma\mathbf s_{t-1}+(1-\gamma)\mathbf g_t^2$
$\mathbf w_t=\mathbf w_{t-1}-\dfrac\eta{\sqrt{\mathbf s_t+\epsilon}}\cdot \mathbf g_t$

Adadelta:

$\mathbf s_t=\gamma\mathbf s_{t-1}+(1-\gamma)\mathbf g_t^2$
$\mathbf w_t=\mathbf w_{t-1}-\mathbf g’t$
$\mathbf g’t=\dfrac{\sqrt{\Delta\mathbf x{t-1+}\epsilon}}{\sqrt{\mathbf s_t+\epsilon}}\cdot \mathbf g_t$
$\Delta \mathbf x{t}=\lambda\Delta\mathbf x_{t-1}+(1-\lambda)\mathbf g’^{2}_{t}$

Adam:

Estimate momentum and the second moment:
$\mathbf v_t=\beta_1\mathbf v_{t-1}+(1-\beta_1)\mathbf g_t$
$\mathbf s_t=\beta_2\mathbf s_{t-1}+(1-\beta_2)\mathbf g_t^2$

Bias correction:
$\hat{\mathbf{v}}_t = \dfrac{\mathbf v_t}{1-\beta_1^t}$
$\hat{\mathbf{s}}_t = \dfrac{\mathbf s_t}{1-\beta_2^t}$
Update:
$\mathbf g’_t=\dfrac{\eta\mathbf {\hat{\mathbf v}_t}}{\sqrt{\hat{\mathbf s}t}+\epsilon}$
$\mathbf x_t = \mathbf x{t-1}-\mathbf g’_t$

3 Learning Rate Part

The simplest approach is to use a fixed learning rate.

• Reduce the learning rate as the number of iterations increases:
  • Single-factor scheduler: $\eta_{t+1}=\eta_t\cdot\alpha$
    To prevent excessive decay, we usually use: $\eta_{t+1}=\max(\eta_{\min},\eta_t\cdot \alpha)$
  • Multi-factor scheduler: Let $s={5,10,20}$, and when $t\in s$, $\eta_{t+1}=\eta_t\cdot\alpha$
  • Cosine scheduler: $\eta_t=\eta_T+\dfrac{\eta_0-\eta_T}2(1+\cos(\pi t/T))$, and no updates occur after $t>T$.
• Add a warm-up period:
  • Linear increase