Stochastic Gradient Descent ( 随机梯度下降 )

Stochastic Gradient Descent (SGD) ( 随机梯度下降（ SGD ） ) 是一种简单但非常有效的方法，用于在诸如（线性）支持向量机和 逻辑回归 之类的凸损失函数下的线性分类器的辨别学习。即使 SGD 已经在机器学习社区中长期存在，但最近在大规模学习的背景下已经受到了相当多的关注。
SGD 已成功应用于文本分类和自然语言处理中经常遇到的大规模和稀疏机器学习问题。

SGD 已成功应用于文本分类和自然语言处理中经常遇到的 large-scale and sparse ( 大规模和稀疏 ) 机器学习问题。鉴于数据稀疏，本模块中的分类器容易扩展到具有 10^5 个以上训练样本和超过10^5个特征的问题。

随机梯度下降的优点是：

· 效率。

· 易于实施（很多机会进行代码调优）。

随机梯度下降的缺点包括：

· SGD 需要一些 hyperparameters  ( 超参数 ) ，如 regularization parameter ( 正则化参数 ) 和迭代次数。

· SGD 对特征缩放敏感。

大家都知道，训练深度网络一般用的是 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 能更有效的利用信息，特别是信息比较冗余的时候。

考虑下面一个特殊情况，假设你要 ，但是 , , 这样的话其实你有很多项是冗余的，这样的话你 取得的最小值点 , 其实和你 确定的最小值点是一样的。 如果采取 GD 去迭代，你每一次要算 个梯度，但是如果用 SGD 其实就是每一次选一个计算梯度，因为 ，SGD 算一个梯度的下降方向，就等于 GD 算十个得到的下降方向，所以无形之间，帮我们排除了很多冗余信息。

在实际中，可能没有这么巧合的情况，但是如果是在数据集特别特别大的情况下，虽然可能没有 ，但是很有可能出现一些函数比较接近，也就是 ,这样的话， SGD无形之间排除冗余信息的能力就又触发了。

Prat II: 实验上 ( Practical Motivation )

结论是：相对于非随机算法， SGD 在前期迭代效果卓越。

我直接截论文上面的图，大家观赏一下

L-BFGS是一种需要算所有梯度，还要拟合Hessian 的一个优化算法.。不过既然是要算 full gradient, 大家直接理解成一种像 GD 一样的非随机的算法吧。 x 轴可以看成计算的梯度的数量，y轴可以看成是和真实最小值的误差。（个人理解哈，可能有偏差，大家会个意呗，想精确了解的，自己去看看原论文呗~~）

比较上图可得，随机算法 SGD 前期每个 iteration 找到的迭代点，可以显著的接近最小值点。

这里又有一个特别好玩的小例子来解释为什么 SGD 前期表现好，后期就水了现象。

这是我最想翻译的部分！！其他可以跳过，这里要认真听了哈~~。

假设我们需要优化的函数全部是二次函数，形式如下

其中 是常数，并且满足

我们求导，令导数等于零得到

其实这就是一堆sample, 在平方距离公式下，离他们最近的点就是他们的均值。

结合我们的假设公式（2.2）我们得到，最小值点在0处，也就是

所以函数的最小值点在0处。我们现在看看 SGD 的表现，假设我们最开始的初始点在最左边，然后无论你选到那个二次函数的分支，沿着梯度，都能向靠近最小值点的方向移动。所以SGD 前期效率很高。

如果想随机梯度下降收敛的比较好，我知道的方法有，一是采取递减的 stepsize，原理是什么我还没搞清楚，二就是 Variance reduction 的一些方法吧，比如采用更多的样本算梯度，或者用SAGA, SVRG这种方法吧。个人猜测，这些做法是不是为了解决忽近忽远的问题，其实我不太清楚，当个讨论题，希望有大牛能帮我们解答一下。

Prat III: 理论上 （Theoretical Motivation）

结论是：如果样本数量大，那么 SGD的Computational Complexity 依然有优势。

我们知道， GD 在强凸的情况下收敛速度是 Linear Convergence, 最差的情况下，至少需要迭代 次，才能达到 的精度，加上 GD 每一次需要计算 n 个梯度，所以总的 Computational Complexity 是 。

至于 SGD， 结论是 为了达到 , 在最差的情况下，我们需要迭代次数是 ，但是因为 SGD 每一次就算一个梯度，所以它的 Computational Complexity 也是 。这些复杂度的证明我看看以后有时间写一下好了，当个小练习，但是不是今天的重点，故略去。

放在表格里面就是这样子的了

对比与 GD 的 ，SGD 的 受所需的精度 的影响较大, 但是如果是在 Large Large Data 的设定下，n 会特别特别大， 这样 SGD 的Computational Complexity 依然是可以小于 GD 的Computational Complexity，换就换就是，如果n特别大，那么 SGD 在Computational Complexity 上依然有优势

总结：

好了总结一下， SGD 相比与 GD 优势如下：

Prat I: 相对于非随机算法，SGD 能更有效的利用信息，特别是信息比较冗余的时候。

Prat II: 相对于非随机算法， SGD 在前期迭代效果卓越。

Prat III: 如果样本数量大，那么 SGD的Computational Complexity 依然有优势。