本文主要整理下Batch、Online场景下，各种常用的最优化算法。内容上大部分是参考其他博客，并无太多原创成分，目的是梳理知识点，加深理解。
因此会尽量在必要的地方添加来源信息，如有遗漏或者错误之处，请不吝指出！
谈及机器学习问题的参数最优化求解算法，两大应用场景（训练方式）——Batch、Online占据了相当重要的地位。借助本博文，作者出于知识整理、逻辑疏剪的目的，简单叙述下Batch和Online场景下，多种常用最优化算法的异同之处。
一般机器学习参数优化问题，都使用Batch方式进行训练。此时在全量数据上进行训练的成本，尚在可接受范围之内，因此讨论更多的，是如何更高效、更准确地得到「全局最优解」。
我们从随机梯度下降（SGD）开始。
博文1有提到，SGD以及一系列基于SGD演变而来的算法，都可以使用一个统一的框架来描述。各个算法的不同，也不过是对框架中某个步骤的改动而已。
即：
给定一个优化目标参数$w$，以及目标函数$f(w)$，初始学习率$\alpha$，在t+1时刻，基于SGD的最优化算法以如下步骤进行迭代：
- 计算梯度值$g_t=\nabla f(w_t)$
- 计算一阶动量$m_t=\phi(g_1,g_2,…,g_{t}), V_t=\varphi(g_1,g_2,…,g_{t})$
- 计算下降梯度$\eta_{t}=\alpha * \frac{m_t}{\sqrt{V_t}} $
- 更新权重$w_{t+1} = w_{t} - \eta_t$
后续提到的算法（如SGD-M、AdaGrad、Adam等，无非就是在修改上述4个步骤中的一或者多个，框架依然保持一致。
1. SGD
SGD算法直接使用梯度作为一阶动量，同时未引入二阶动量参与学习率的调整，一般直接使用一个随当前时刻$t$严格递减的函数调整学习率。具体来说，是更改步骤2的计算方法，如下：
这样的话，第三步下降梯度计算可得：$\eta_t=\alpha \frac{g_t}{\sqrt{t}}$
SGD算法比较简明，有如下几个特点：
- 无须计算高阶动量
- 不用记忆任何数据的历史结果，内存消耗低
但由于SGD的下降梯度方向，完全由上一个时刻的梯度决定，导致此算法容易在局部最优的鞍点处持续震荡，无法跳出，同时由于其学习率随着时刻严格递减，一定程度上加剧了「鞍点处震荡」的可能性。
2. SGD-Momentum
针对SGD由于下降梯度计算依据的单一性所导致的问题，SGD-Momentum（SGD-M）算法在计算下降梯度时，同时加权地结合了当前时刻梯度以及历史上累积梯度(动量)，在持续快速变化的参数上，加速其更新过程，以此「抑制」SGD算法所遇到的「容易在鞍点处震荡」的情况发生。具体来说，SGD-M算法是更改了上述框架中的步骤2中一阶动量的计算方法，如下：
上式中$\beta$一般经验值取0.9。这个参数意味着某个时刻的下降梯度，主要由其历史的指数移动平均动量决定（经验参数$\beta=0.9$），同时也小程度（$1-\beta$）地参考当前时刻梯度值，以此，SGD-M算法能够在持续变化较快的参数上，加速其更新过程，从而在一定程度上「抑制」了SGD算法「鞍点处震荡」的问题。
3. N-SGD
同样是为了解决SGD中遇到的「容易在鞍点处震荡」问题，Nesterov Accelerated SGD（N-SGD)采用了与SGD-M不同的角度切入，直接修改框架中步骤1中梯度的计算。具体来说，是梯度的计算，从只考虑上一个时刻目标参数的梯度，修改为基于「根据已有累积动量更新后的目标参数」。具体如下：
感官上来讲，N-SGD算法，是先根据已有累积动量更新一次目标参数，然后在此基础之上，结合Momentum的计算方法，同时考虑累积动量和当前梯度，得出最终的下降梯度。以此，N-SGD算法相对于正常的SGD或者SGD-M，在计算下降梯度时，预先地往前看一步，极大地加速了优化问题的收敛过程。
4. AdaGrad
1.1-1.3中涉及的三个算法，都未引入二阶动量，它们只是使用了不同的一阶动量生成方法，其学习率的变化，并不会依据任何与某时刻的参数变化情况而定，一般是采用与当前时刻呈严格递减的函数作为学习率确定方法。
上述算法无法根据各个参数情况的不同，做适应性的调整，即：不论参数变化多寡，都是采用统一的学习率，不利于某些展现规模较低特征（反而可能更有用）的更新优化。
AdaGrad方法针对此情况，修改了算法框架中的步骤2，引入二阶动量的计算，一般采用$V_t=\sum^{t}_{r=1}{g_r^{2}}$的经验式，以此，对一些经常展现、更新的参数（也就是累积二阶动量比较大），学习率变得更小，更新更加缓慢、谨慎，而对一些变动较少的参数（累积动量较小），算法为其分配了更大的学习率，期望能从少量样本中学到更多信息。
具体来说，
可以看到，学习率从$\alpha/\sqrt{t}$变成了$\alpha/\sqrt{\sum_{r=1}^{t}g_r^2}$，在稀疏数据上，此算法有比较好的表现，但对于比较稠密的数据，大部分参数都会更新比较频繁，上述学习率随着迭代次数的增加，愈发趋近于0，从而导致算法提前结束或者只能得到局部最优。因此，上述方法在迭代轮数足够长的情况下，很容易导致算法在一个局部最优处震荡，无法提供足够的变动，让参数跳出，得到全局最优的可能较低。
5. AdaDelta
针对AdaGrad上述问题，AdaDelta将全局的二阶累积动量，修改为固定窗口的受限二阶累积动量，以此抑制「学习率因为迭代次数的累加，而趋近于0」的问题。具体来说，
这样，累积的二阶动量，可以通过参数$\beta$的调整，仅仅基于最新几次（约等于$1/(1-\beta)$个时刻）迭代得到，从而避免AdaGrad中的问题。
6. Adam
既然有了AdaDelta动态的根据二阶累积动量，为不同情况的特征（参数）调整不同的学习率，也有SGD-M根据一阶累积动量，调整梯度的方向，加速算法收敛，那Adam算法便是同时结合了这两种算法，采各家之所长，「既能加速收敛，亦能灵活地根据参数不同情况，得到更优的结果」。具体来说，Adam算法修改了上述算法框架中的步骤2：
兼具加速收敛以及更优结果的长处之外，Adam算法也有一些隐忧2。
首先，Adam算法可能没办法收敛。这个问题，是由于采用了与AdaDelta相同的二阶累积梯度作为学习率的策略，我们没办法保证$V_{t} = \beta_{2} * V_{t-1} + (1-\beta_{2})*g_{t}^{2}$所计算出来的$V_{t}$一定是随着t严格单调递增的，所以学习率也没有办法保证是严格递减的。因此在持续迭代的过程中，存在着一定可能性会出现算法无法正常收敛的情况。
针对这个问题，文章3提出了一个remedy。将上述二阶累积动量的更新方式，修改为$V_{t} = max(\beta_{2}V_{t-1} + (1-\beta_{2})g_{t}^{2}, V_{t-1})$，以此保证$V_{t}$是随着t单调递减的，保证算法一定能够收敛。
其次，Adam算法得到的结果，不一定是最优结果。这个情况更多可能出现在深度学习模型的优化场景下，在此类模型中，参数维度极高，相对于正常较低维度的参数空间，非凸目标函数更大可能会出现很多局部最优点，坑坑洼洼，由于采用了与SGD-M一致的累积一阶动量移动平均作为梯度计算策略，Adam算法在计算梯度方向时，会参考历史的累积动量，在某些高峰处，很容易直接越过；而在某些高原平面，容易陷入无法跳出，结束训练。
7. N-Adam
既然Adam同时采AdaDelta和SGD-M之所长，那么N-SGD所使用的加速收敛方法，也可以合入Adam算法，这就是Nesterov Accelerated Adam（N-Adam）算法。具体来说，在Adam算法的基础之上，N-Adam如果N-SGD之于SGD的修改一样，对算法框架中的步骤1做了调整：
至此，我们使用一个统一的优化算法框架，整理了Batch场景下，SGD类的几个主要优化算法以及它们各自的优缺点。
接下来，我们转向Online场景，看看在大规模数据下，为了增加模型（参数）的稀疏性，各种层出不穷的算法所做出的努力。