An overview of gradient descent optimization method

梯度下降算法是一种非常流行的优化算法，它是优化神经网络的最常用的算法之一。当前的具有最优性能的深度学习工具包基本上都包含了不同的实现梯度下降的算法，但是，这些算法在使用的时候基本上都是当作一个黑箱子在使用，用户不知道其具体的实现细节，因为，具体地描述这些算法的优点或缺点是比较困难的。

这篇博客旨在给读者提供一个各个梯度下降算法之所以有用的直觉，从而帮助用户针对具体的问题选择合适的梯度下降算法。我们首先介绍几种梯度下降算法的变种，然后总结一下使用该算法训练中会出现的一些挑战，之后具体地介绍常见的优化算法以及它们解决上述挑战的动机和相应的更新规则。我们简单地给出了梯度下降算法的平行化和分布式化的一些设置。最终，考虑一些有助于优化梯度下降算法的特别的策略。

梯度下降主要用来最小化目标函数$J(\theta)$ ，其中参数是$\theta \in R^d$，它通过将参数$\theta$往目标函数相对于参数$\theta$的梯度相反的方向进行更新来一步步地减小目标函数值。其中学习率$\eta$决定了每次更新的步长。换句话说，假设目标函数是一座山，参数每次都从山的最陡峭的那一面往下面滚，直到到达谷底，即是局部最小点。

梯度下降的变种

一共有三种不同的梯度下降形式，其区别在于每次使用多少数据来计算目标函数的梯度。通过使用不同数量的数据，我们在参数更新的准确度与其所消耗的时间之间达到一个平衡。

Batch gradient descent

BGD ，每次都使用所有的训练数据计算目标函数相对于待求参数的梯度。
$$\theta = \theta - \eta.grad(J(\theta))$$
因为每次更新都要利用所有训练数据计算梯度，BGD 会非常慢，而且内存可能也不够一次性导入这么多数据。BGD 也不支持在线的更新方式。

1
2
3

for i in range(nb_epochs):
	params_grad = evaluate_gradient(loss_function,data, params)
	params = params - learn_rate*params_grad

其中迭代次数 nb_epochs 是预先定义的，每次迭代过程中，首先计算梯度向量 params_grad，它是所有训练数据的损失函数相对于参数的梯度。现有的深度学习工具包都实现了非常有效的自动求梯度(automatic differentiation)的方法，当然，如果你想自己手写求梯度的代码，梯度检验(gradient checking)是非常有必要的。之后我们将参数向着梯度的方向进行更新，学习率(learn_rate) 决定了每一次更新的步长。对于凸的损失函数，BGD能确保收敛到全局最优解，对于非凸函数，BGD能收敛到局部最优解。

Stochastic gradient descent

SGD 每次使用单个样本进行参数更新，假设第$i$ 个训练样本的属性为$x_{i}$，标号为$y_i$,那么使用第$i$个样本的更新公式为：
$$\theta = \theta - \eta*grad(J(\theta,x_i,y_i))$$
BGD 每次迭代都是用相同的样本计算梯度，因此其包含很多冗余的计算.SGD 通过每次只使用一个样本更新来解决这种冗余问题，因此，SGD通常速度非常快，而且其适用于在线学习。
值得注意的是，SGD更新得到的参数值波动非常大，也即更新得到参数的方差非常大。

对于非凸函数，虽然BGD能够收敛到局部最优解，但是这个局部最优解可能并不是最好的，SGD能够使得参数跳出这个局部最优点，从而获得更好的解。
当然，如果我们逐步地减小学习率，对于非凸函数，SGD最终也会像BGD那样收敛到一个局部最优解。对于凸函数，SGD也能收敛到全局最优解。

下面的代码简单地展示了SGD的学习过程，注意，每次迭代前都要重现排列一下数据

for i in range(nb_epochs):
	np.random.shuffle(data)
	for example in data:
		params_grad  = evaluate_gradient(loss_function,example,params)
		params = params - learn_rate * params_grad

Mini-batch gradient descent

MBGD 是介于BGD和SGD之间的一种方法，它每次选择$n$样本更新参数：

MBGD可以:
1) 减小参数更新的方差，从而使得参数更新能够稳定地收敛。
2) 能够使用高度优化的矩阵操作，从而能够使得更新mini-batch 非常有效。
一般的mini-batch 大小在50 到256之间，但是这个值因具体应用而不同。
MBGD 是神经网络训练中最常用的一种算法，SGD一般也可以指代MBGD。

for i in range(nb_epoches):
	np.random.shuffle(data)
	for batch in get_batches(data,batch_size  = 50):
		params_grad = evaluate_gradient(loss_function,batch,params)
		params = params - learn_rate * params_grad

Challenges

上述提到的几种梯度下降算法并不能保证好的收敛效率，它们提出了以下的几个挑战：
1）选择一个合适的学习率非常重要，如果学习率设置地非常小的话，收敛率非常慢。但是，学习率过大的话，算法不容易收敛，导致目标函数在局部最小点周围跳转而不收敛到最小点。
2）也可以在迭代的过程中动态地改变学习率，但是需要预先定义一些规则。但是这种规则不能适用于不同的数据
3) 另一个主要的挑战是，当目标函数是高度非凸的时候，比如神经网络，我们希望避免参数陷在次优点，而且，在这种情况下，参数极易陷入到鞍点，而不是局部最优点。

Gradient descent optimization algorithms

接下来我们介绍几种深度学习中经常用到的算法来应对上述挑战，我们不会讨论对高维数据不可行的算法，比如二阶算法，如牛顿法。

Momentum

一般的SGD算法在遇到山谷时会发生剧烈震荡，也即在达到局部最优点的过程中非常缓慢，Momentum能够加速收敛到局部最优点，而且能够避免过多的震荡。在每次更新中，它将当前的梯度加上上一次更新的梯度的加权和作为参数更新的步长，具体如下式所示：

在实际操作中，常常将$\gamma$设为0.9. 可以想象将一个小球滚下山坡，小球会沿着最陡的方向越跑越快，在Momentum中的参数更新中，梯度最大的方向每次都被保留下来传入到下一次参数的更新中，经过多次迭代，最陡峭的方向累积的梯度和越来越大，也即参数向这个方向更新的步长越来越大，因此，能够加速收敛和避免震荡。

Nesterov accelerated gradient

但是，一个只会一直沿着最陡方向下降的小球是不够智能的，我们希望这个小球能够预知当前选择的方向会不会一直下降，因为可能虽然小球当前所运动地方是下降的，但是未来会上升。
相比于 Momentum,Nesterov accelerated gradient （NAG）根据当前的参数值估计下一步参数的梯度，将参数沿着下一步梯度的方向移动

Adagrad

Adagrad 也是一种基于梯度的优化算法，它能够自适应地调整学习率，对于不频繁更新的特征使用较大的学习率，而对于频繁更新的参数使用较小的学习率。所以，Adagrad比较适用于稀疏数据。
在上面的算法中，我们使用向量化的方式来更新参数$\theta$,因为Adagrad 对每个不同的参数 $\theta_i$
在不同的时刻使用不同的学习率，
因此，我们首先对每个单独的参数 $\theta_i$
介绍更新规则，之后再给出向量化的更新公式。假设 $g_{t,i}$
表示目标函数 $J(\theta)$ 在时刻t关于参数 $\theta_i$的梯度：

那么SGD算法的更新公式为：

在Adagrad算法中，$\theta_i$在当前时刻的学习率由上一时刻的梯度计算得到：

$G_t \in R^{d\times d}$是对角矩阵，其对角线上的元素$G_{t,ii}$等于$\theta_i$在时刻t之前所有时刻梯度的平方和，$\epsilon$是光滑项以防止分母为零，通常设置为1e-8.比较有趣的是，如果上式中没有平方根，算法的效果会很差。
通过使用矩阵-向量 element-wise product, 上式可以直接向量化为：

Adagrad 一个最大的优点就是不用手动调节学习率，通常将$\eta$设置为0.01,然后就可以自动调节。
Adagrad一个最大的缺点就是在上式的分母中，梯度的平方和是一直累加的，可能会累加到无限大，然后每次迭代更新会非常缓慢，最终会停止迭代，可能还没有收敛到局部最优点，下面的算法主要是为了解决这个问题。

Adadelta

Adadelta 算法是Adagrad算法的扩展，主要是为了解决一直下降的学习率问题。与Adagrad一直累计过去的所有的梯度平方和不同的是，Adadelta设定了一个累积和窗口大小为$\omega$

Adadelta并没有存储过去$\omega$个时刻的梯度的平方，在时刻t的累计梯度平方和被定义为t-1时刻的累积梯度平方和和当前梯度平方的加权和。

$\gamma$通常也设定为0.9，与Momentum中的$\gamma$相同。

简单整理一下：
对于一般的SGD
每次迭代的梯度:
每次更新公式:
Adagrad 与 Adadelta仅仅是学习率与SGD不同：
对于Adagrad:

替换上式中的$G_t$得：

上式中分母可以看作是梯度的Root Mean Square Error，所以可以将其替换为:

Adadelta的作者发现上述参数$\theta$的更新公式左右两边单位不统一，$\triangle\theta_t$是参数的更新大小，$g_t$是目标函数关于参数的梯度，它们能相等么？为了实现单位的统一，Adadelta中又定义了新的更新方式，首先定义:

为关于参数更新大小的迭代均值，因此有：

因为在第t步迭代中，$E[\triangle\theta^2]_t$是未知的，因此，使用t-1时刻的$E[\triangle\theta^2]_{t-1}$来近似。最终得到Adadelta的更新公式为：

RMSprop

RMSprop是Geoff Hinton在他的coursera 课程上提出来的一种自适应学习率算法，它是与Adadelta各自独立被提出来的。它与Adadelta的目的一样，都是为了解决Adagrad算法中学习率衰减非常快的问题，它实际上与Adadelta算法中的第一种形式相同:

只不过在RMSprop中$\gamma$被固定地设为0.9,$\eta$通常被设为0.001

Adam

Adaptive Moment Estimation (Adam) 算法结合了Momentum，Adadelta 以及 RMSprop的优点，Adam是上述几种算法的集合。
首先Adam像Momentum那样计算当前梯度更新也利用了过去时刻的梯度：

其次，Adam也像Adadelta那样利用了过去时刻梯度的平方：

因为每次更新$m_t,v_t$都有偏差，通过下式克服偏差：

最终给出了Adam算法的更新公式，类似于Adadelta和RMSprop: