1 梯度下降算法理论分析

1.1 相关介绍

1.1.1 批量梯度下降

使用整个数据集的优化算法被称为批量（batch）或确定性（deterministic）梯度算法，因为它们会在一个大批量中同时处理所有样本。通常，术语“批量梯度下降”指使用全部训练集，而术语“批量”单独出现时指一组样本。

1.1.2 随机梯度下降

每次只使用单个样本的优化算法被称为随机（stochastic）或者在线（online）算法。术语“在线”通常是指从连续产生样本的数据流中抽取样本的情况，而不是从一个固定大小的训练集中遍历多次采样的情况。

1.1.2 小批量随机梯度下降

大多数深度学习的算法介于以上两者之间，使用一个以上而又不是全部的训练样本。传统上，这些会被称为小批量随机（minibatch stochastic）方法，现在通常将它们简单地称为随机（stochastic）方法。

1.2 迭代步的推导

考虑如下优化问题，其中x是模型的参数，

对f(x)在w=w(k)$w=w^{(k)}$处做二阶泰勒展开，并假设∇2f(w(k))≈1α(k)I${\mathrm{\nabla }}^{2}f(w^{(k)})\approx \frac{1}{{\alpha }^{(k)}}I$，

令∂F(w)∂w=0$\frac{\mathrm{\partial }F(w)}{\mathrm{\partial }w}=0$，即

可得

所以

这就是梯度下降算法的迭代步，其中α(k)${\alpha }^{(k)}$是第k步的步长。
同理，如果不假设∇2f(w(k))≈1α(k)I${\mathrm{\nabla }}^{2}f(w^{(k)})\approx \frac{1}{{\alpha }^{(k)}}I$，则推导出牛顿法的迭代步如下：

2 梯度算法实现

2.1 基本算法

2.1.1 随机梯度下降

更新规则如下：

2.1.2 动量

初始化v=0$v=0$，更新规则如下：

动量方法（Polyak, 1964）引入了变量v充当速度角色，速度v积累了梯度元素∇θ(1m∑mi=1L(f(x(i);θ),y(i)))${\mathrm{\nabla }}_{\theta }(\frac{1}{m}\sum _{i=1}^{m}L(f(x^{(i)};\theta ),y^{(i)}))$，α$\alpha$越大，之前梯度对现在方向的影响也越大。动量的主要目的是主要解决两个问题：

• Hessian矩阵的病态条件（更新一步之后loss并没有减小）
• 随机梯度的方差（随机梯度和全梯度之间有偏差）

2.1.3 Nesterov动量

受Nesterov加速梯度算法（Nesterov, 1983, 2004）启发，Sutskever et al.(2013)提出了动量算法的一个变种。这种情况的更新规则如下：

Nesterov动量和标准动量之间的区别体现在梯度计算上。Nesterov动量中，梯度计算在施加当前速度之后。因此，Nesterov动量可以解释为往标准动量方法中添加了一个校正因子。

2.2 自适应学习率算法

最近提出一些增量（或者基于小批量）的算法来自适应模型参数的学习率。它们的思想都是，为每个参数设置不同的学习率，在整个学习过程中自适应这些学习率。

2.2.1 AdaGrad

Adagrad算法（Duchi et al., 2011）独立地适应所有模型参数的学习率。效果是在参数空间中更为平缓的倾斜方向会取得更大的进步。在凸优化背景下表现很好。更新规则如下：

1. 计算梯度：g←1m∑mi=1L(f(x(i);θ+αv)$g\leftarrow \frac{1}{m}\sum _{i=1}^{m}L(f(x^{(i)};\theta +\alpha v)$
2. 累积平方梯度：r←r+g⊙g$r\leftarrow r+g\odot g$
3. 更新：θ←θ−ϵδ+r√⊙g$\theta \leftarrow \theta -\frac{ϵ}{\delta +\sqrt{r}}\odot g$

2.2.2 RMSProp

RMSProp算法（Hinton,2012）修改AdaGrad以在非凸设定下效果更好。AdaGrad根据平方梯度的整个历史收缩学习率，经验上已经发现，对于训练深度神经网络而言，从训练开始时积累梯度平方会导致有效学习率过早或过量的减少。RMSProp使用指数衰减平均以丢弃遥远过去的历史，使其能够在最后找到凸碗状结构后快速收敛，它就像一个初始化于该碗状结构的AdaGrad算法实例。更新规则如下：

1. 计算梯度：g←1m∑mi=1L(f(x(i);θ+αv)$g\leftarrow \frac{1}{m}\sum _{i=1}^{m}L(f(x^{(i)};\theta +\alpha v)$
2. 累积平方梯度：r←ρr+(1−ρ)g⊙g$r\leftarrow \rho r+(1-\rho )g\odot g$
3. 更新：θ←θ−ϵδ+r√⊙g$\theta \leftarrow \theta -\frac{ϵ}{\delta +\sqrt{r}}\odot g$

2.2.3 AdaDelta

Adadelta算法（Zeiler, 2012）也像RMSProp一样，使用了小批量随机梯度按元素平方的指数加权移动平均变量r$r$，两位作者在互不知道的情况下都想到了这样的方法。AdaDelta跟RMSProp不同的地方在于，使用累积更新量代替学习率，因此它的主要优势在于不需要选取学习率。更新规则如下：

1. 计算梯度：g←1m∑mi=1L(f(x(i);θ+αv)$g\leftarrow \frac{1}{m}\sum _{i=1}^{m}L(f(x^{(i)};\theta +\alpha v)$
2. 累积平方梯度：r←ρr+(1−ρ)g⊙g$r\leftarrow \rho r+(1-\rho )g\odot g$
3. 计算更新：Δx←−d√r√⊙g$\mathrm{\Delta }x\leftarrow -\frac{\sqrt{d}}{\sqrt{r}}\odot g$
4. 累积更新量：d←ρd+(1−ρ)Δx$d\leftarrow \rho d+(1-\rho )\mathrm{\Delta }x$
5. 应用更新：θ←θ+Δx$\theta \leftarrow \theta +\mathrm{\Delta }x$

2.2.4 Adam

Adam（Kingma and Ba, 2014）这个名字派生自短语“adaptive moments”，可以看作RMSProp和Moments的结合。更新规则如下：

1. 计算梯度：g←1m∑mi=1L(f(x(i);θ+αv)$g\leftarrow \frac{1}{m}\sum _{i=1}^{m}L(f(x^{(i)};\theta +\alpha v)$
2. 更新有偏一阶矩估计：s←ρ1s+(1−ρ1)g$s\leftarrow {\rho }_{1}s+(1-{\rho }_1)g$
3. 更新有偏二阶矩估计：r←ρ2r+(1−ρ2)g⊙g$r\leftarrow {\rho }_{2}r+(1-{\rho }_2)g\odot g$
4. 修正一阶矩的偏差：ŝ ←s1−ρt1$\hat{s}\leftarrow \frac{s}{1-{\rho }_1^t}$
5. 修正二阶矩的偏差：r̂ ←r1−ρt2$\hat{r}\leftarrow \frac{r}{1-{\rho }_2^t}$
6. 更新：θ←θ−ϵŝ δ+r̂ √$\theta \leftarrow \theta -ϵ\frac{\hat{s}}{\delta +\sqrt{\hat{r}}}$

2.3 随机梯度算法

2.3.1 SAG

SAG方法（Le Roux et al., 2012）更新规则如下：

其中，sk$s_k$是从1,2,...,n$1,2,...,n$均匀采样的值。
该方法的缺点是需要为每个样本存储最新的梯度；更新的梯度是全梯度的有偏估计，证明见下一节。

2.3.2 SAGA

SAGA方法（Defazio et al., 2014）是SAG方法的无偏版本，更新规则如下：

其中，sk$s_k$是从1,2,...,n$1,2,...,n$均匀采样的值。
在这个方法中，

所以更新量是∇f(w(k))$\mathrm{\nabla }f(w^{(k)})$的无偏估计。

2.3.3 SVRG

SVRG方法（Johnson et al., 2013）不需要为每个样本存储一个最新梯度。