Solver就是用来使loss最小化的优化方法，loss是损失函数。损失函数最小的目标就是求解全局最小值。

假设有数据集(X1, X2, …, Xn)，对应的(y1, y2, …, yn)，其中每个Xi对应m个元素。loss函数定义为

其中，F(X)为模型。假设F(X)为线性函数：

, x0 = 1

目标：min Φ(θ)，loss函数最小。估计最优系数(θ0, θ1, θ2, …, θm)。

预备知识：梯度下降法(最速下降法)

顾名思义，梯度下降法的计算过程就是沿梯度下降的方向求解极小值。

具体过程如下(如图1所示)：

1. 首先对θ赋值，这个值可以是随机的，也可以让θ是一个全零的向量(初值的选择非常影响梯度下降算法的好与坏)。
2. 改变θ的值，使得Φ(θ)按梯度下降的方向进行减少。

图1 梯度下降描述(来自于斯坦福大学，《机器学习》公开课[2])

????过程2)可以表示为：

????????

????????其中α为步长。

由于我们每进行一次参数更新需要计算整体训练数据的梯度，批量梯度下降会变得很慢，并且会遇到内存吃不下数据就挂了。同时批量梯度下降也无法支持模型的在线更新，例如，新的样本不停的到来。

1. SGD (随机梯度下降算法，Stochastic gradient descent)

在梯度下降中，对于θ的更新，所有的样本都有贡献，也就是参与调整θ，其计算得到的是一个标准梯度。如果数据量非常大，那么运算速度很慢。而随机梯度下降算法的随机也就是说我用样本中的一个例子来近似我所有的样本，来调整θ。这样速度更快，但是更容易陷入局部极小。随机梯度下降算法可以表示为：

????

/*****************[1] *****************/

Caffe中的SGD在通过负梯度和上一次的权重更新值Vt的线性组合来更新θ，迭代公式如下：

????

????

其中，α是负梯度的学习率(base_lr)，μ是上一次梯度值的权重（momentum），用来加权之前梯度方向对现在梯度下降方向的影响。这两个参数需要通过tuning来得到最好的结果，一般是根据经验设定的。如果你不知道如何设定这些参数，可以参考相关的论文。

在深度学习中使用SGD，比较好的初始化参数的策略是把学习率设为0.01左右（base_lr: 0.01)，在训练的过程中，如果loss开始出现稳定水平时，对学习率乘以一个常数因子（gamma），这样的过程重复多次。

对于momentum，一般取值在0.5--0.99之间。通常设为0.9，momentum可以让使用SGD的深度学习方法更加稳定以及快速。

关于更多的momentum，请参看Hinton的《A Practical Guide to Training Restricted Boltzmann Machines》。

实例：

?

lr_policy设置为step，则学习率的变化规则为 base_lr * gamma ^ (floor(iter / stepsize))

即前1000次迭代，学习率为0.01; 第1001-2000次迭代，学习率为0.001; 第2001-3000次迭代，学习率为0.00001，第3001-3500次迭代，学习率为10-5

上面的设置只能作为一种指导，它们不能保证在任何情况下都能得到最佳的结果，有时候这种方法甚至不work。如果学习的时候出现diverge（比如，你一开始就发现非常大或者NaN或者inf的loss值或者输出），此时你需要降低base_lr的值（比如，0.001），然后重新训练，这样的过程重复几次直到你找到可以work的base_lr。

/*****************[1] *****************/

2. AdaGrad(自适应梯度，Adaptive Gradient)

自适应梯度与SGD类似，AdaGrad的更新速率是可变的。更新速率一定，不一定适合所有的更新阶段。所以AdaGrad调整的是Gradient，对于所有的参数，随着更新的总距离增多，学习速度随之变缓。可以表示为：

????

????其中(θi)t是t步的参数，ε很小，保证非0。

缺点：学习率单调递减，训练后期学习率非常小；需要手动设置全局学习率；更新 θt时，左右两边单位不统一。

参考文献：Duchi, E. Hazan, and Y. Singer.?Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

/*****************[1] *****************/

示例：

/*****************[1] *****************/

3. AdaDelta

AdaDelta基本思想是用一阶的方法，近似模拟二阶牛顿法，是对AdaGrad的缺点进行改进。可表示为：

???? ？

缺点：类似于AdaGrad，其学习率是单调递减的，训练后期学习率非常小。

/*****************[1] *****************/

示例：

/*****************[1] *****************/

4. RMSprop

RMSprop和Adadelta是在差不多的时间各自独立产生的工作，目的都是为了缓解Adagrad的学习速率减少的问题。实际上RMSprop和我们在Adadelta中推到的第一个更新向量是相同的：

????

????

其中，ρ建议取0.9，α建议取0.001。

/*****************[1] *****************/

示例：

/*****************[1] *****************/

5. NAG

这个算法严格的说来是凸优化中的算法，具有O(1/t^2)的收敛率，收敛速度比较快。因为 DNN是一个non-convex的model，所以NAG方法并不能达到这个收敛速度。caffe文档中指出，这个方法对于某些deeplearning 的 architecture是非常有效的。与SGD类似，具体更新过程如下：

????

????

通过调节α和μ可以有效的改变迭代速度以及迭代的方向。可以看出θi的更新是和上次增量以及梯度线性相关的。在Caffe的文档中给出了一个基本的调参规则[3]：

a. 初始的learning rate建议设置为0.01。

b. 在迭代过程中当loss到达了一个明显的"plateau"的时候，则以10倍的速度drop learning rate，相当于稍微减少步长，

c. μ是一个调解参数，一般设置为0.9，这个参数起到一个平滑的作用，可以让SGD算法更加稳定和快速

d. μ和α是一个反相关的，增加μ，则降低α，反之亦然。

/*****************[1] *****************/

示例：

/*****************[1] *****************/

6. Adam(个人认为一般都合适的caffe的solver方法)

Adaptive Moment Estimation(Adam) 也是一种不同参数自适应不同学习速率方法，与Adadelta与RMSprop区别在于，它计算历史梯度衰减方式不同，不使用历史平方衰减，其衰减方式类似动量，如下[4]：

????

????

Wt与Vt分别是梯度的带权平均和带权有偏方差，初始为0向量，Adam的作者发现他们倾向于0向量(接近于0向量)，特别是在衰减因子(衰减率)ρ1，ρ2接近于1时。为了改进这个问题，对Wt与Vt进行偏差修正(bias-corrected)：

????

????

最终，Adam的更新方程为：

????

[1] http://www.cnblogs.com/denny402/

[2] http://open.163.com/movie/2008/1/M/C/M6SGF6VB4_M6SGHFBMC.html

[3] http://blog.sina.com.cn/s/blog_eb3aea990102v41r.html

[4] http://blog.csdn.net/heyongluoyao8/article/details/52478715?locationNum=7

Caffe中Solver方法(HGL)