为什么我们更宠爱“随机”梯度下降？（SGD）
导读
特别声明：本文仅有的一点贡献就是用自己的理解翻译了 Leon Bottou 等人的论文 <Optimization Methods for Large-Scale Machine Learning>，初窥门径，才疏学浅，疏漏之处，望不吝指教。
引子
大家都知道，训练深度网络一般用的是 SGD （Stochastic Gradient Descent | 随机梯度下降）而不是 GD (Gradient Descent | 梯度下降)，但是有没有考虑过 SGD 为什么比 GD 更受大家宠爱，SGD 是如何在用较低的 Computational Complexity （一般可以大概理解成，达成目标需要计算 Gradient 的次数）的同时还能保证比较好的训练效果。
本文主要给出几个特殊的例子，给大家一个从直觉性，实验上和理论上认知，为什么有时候，相对于GD 我们更宠爱 SGD?
我们主要从以下三个方面，一起看一看 SGD 相对于 GD 的优势。
Prat I: 直觉上 ( Intuitive Motivation)
Prat II: 实验上 ( Practical Motivation )
Prat III: 理论上 （Theoretical Motivation）
背景知识
我们一般想要优化的函数形式如下
我们知道梯度下降每一次迭代都需要出所有的梯度，即每一次算n个梯度，进行下面的迭代
而随机梯度下降，每一次选一个 
计算梯度，然后迭代
Part I: 直觉上 ( Intuitive Motivation)
结论是：相对于非随机算法，SGD 能更有效的利用信息，特别是信息比较冗余的时候。
Prat II: 实验上 ( Practical Motivation )
结论是：相对于非随机算法， SGD 在前期迭代效果卓越。
我直接截论文上面的图，大家观赏一下
L-BFGS是一种需要算所有梯度，还要拟合Hessian 的一个优化算法.。不过既然是要算 full gradient, 大家直接理解成一种像 GD 一样的非随机的算法吧。 x 轴可以看成计算的梯度的数量，y轴可以看成是和真实最小值的误差。（个人理解哈，可能有偏差，大家会个意呗，想精确了解的，自己去看看原论文呗~~）
比较上图可得，随机算法 SGD 前期每个 iteration 找到的迭代点，可以显著的接近最小值点。
这里又有一个特别好玩的小例子来解释为什么 SGD 前期表现好，后期就水了现象。
这是我最想翻译的部分！！其他可以跳过，这里要认真听了哈~~。
假设我们需要优化的函数全部是二次函数，形式如下
其中
是常数，并且满足
我们求导，令导数等于零得到
其实这就是一堆sample, 在平方距离公式下，离他们最近的点就是他们的均值。
结合我们的假设公式（2.2）我们得到，最小值点在0处，也就是
所以函数的最小值点在0处。我们现在看看 SGD 的表现，假设我们最开始的初始点在最左边，然后无论你选到那个二次函数的分支，沿着梯度，都能向靠近最小值点的方向移动。所以SGD 前期效率很高。
我们假设选中最左边那个
，举个例子。
而到了后期，我们的 
足够靠近我们的最小值点 
，那么单纯靠选择一个二次函数的导数方向移动，便不能达到很好的效果，时而远离最小值点 “0”，时而接近最小值点，我们的前进方向开始犹豫徘徊，这时候便需要计算更多的梯度信息来进行决策了。你看下图，选 
会背离，选 
会接近，就如同诗经《蒹葭》里面描述你追求你心爱的姑娘一样，溯洄从之，宛在水中央。 溯游从之，宛在水中坻。 朦朦胧胧不知方向，忽近忽远~~。这个时候你需要更多的信息了。
多好的例子啊！！！奇美无比~~~。
我突然意识到，随机梯度下降怎么和与女生相处那么相似。刚开始，离的远的时候，不经意间便能产生好感，慢慢靠近。等靠的近了，好感想转换成爱情的时候，便开始茫然失措，不知方向，忽远忽近~~。
忽近忽远后怎么办？
所以对于随机梯度下降，我其实不太清楚如何解决忽近忽远，但是如果想随机梯度下降收敛的比较好，我知道的方法有，一是采取递减的 stepsize，原理是什么我还没搞清楚，二就是 Variance reduction 的一些方法吧，比如采用更多的样本算梯度，或者用SAGA, SVRG这种方法吧。个人猜测，这些做法是不是为了解决忽近忽远的问题，其实我不太清楚，当个讨论题，希望有大牛能帮我们解答一下。
Prat III: 理论上 （Theoretical Motivation）
结论是：如果样本数量大，那么 SGD的Computational Complexity 依然有优势。
总结
好了总结一下， SGD 相比与 GD 优势如下：
Prat I: 相对于非随机算法，SGD 能更有效的利用信息，特别是信息比较冗余的时候。
Prat II: 相对于非随机算法， SGD 在前期迭代效果卓越。
Prat III: 如果样本数量大，那么 SGD的Computational Complexity 依然有优势。
原文发布时间为：2018-09-19
本文作者：zeap
本文来自云栖社区合作伙伴“ ”，了解相关信息可以关注“ ”。
