5.9 随机梯度下降
几乎所有的深度学习算法都用到了一个非常重要的算法：随机梯度下降（stochastic gradi-ent descent，SGD）。随机梯度下降是第4.3节介绍的梯度下降算法的一个扩展。
机器学习中反复出现的一个问题是好的泛化需要大的训练集，但大的训练集的计算代价也更大。
机器学习算法中的代价函数通常可以分解成每个样本的代价函数的总和。例如，训练数据的负条件对数似然可以写成
其中L是每个样本的损失。
对于这些相加的代价函数，梯度下降需要计算
这个运算的计算代价是O(m)。随着训练集规模增长为数十亿的样本，计算一步梯度也会消耗相当长的时间。
随机梯度下降的核心是，梯度是期望。期望可使用小规模的样本近似估计。具体而言，在算法的每一步，我们从训练集中均匀抽出一小批量（minibatch）样本。小批量的数目m'通常是一个相对较小的数，从一到几百。重要的是，当训练集大小m增长时，m'通常是固定的。我们可能在拟合几十亿的样本时，每次更新计算只用到几百个样本。
梯度的估计可以表示成
使用来自小批量B的样本。然后，随机梯度下降算法使用如下的梯度下降估计：
其中，是学习率。
梯度下降往往被认为很慢或不可靠。以前，将梯度下降应用到非凸优化问题被认为很鲁莽或没有原则。现在，我们知道梯度下降用于本书第2部分中的训练时效果不错。优化算法不一定能保证在合理的时间内达到一个局部最小值，但它通常能及时地找到代价函数一个很小的值，并且是有用的。
随机梯度下降在深度学习之外有很多重要的应用。它是在大规模数据上训练大型线性模型的主要方法。对于固定大小的模型，每一步随机梯度下降更新的计算量不取决于训练集的大小m。在实践中，当训练集大小增长时，我们通常会使用一个更大的模型，但这并非是必需的。达到收敛所需的更新次数通常会随训练集规模增大而增加。然而，当m趋向于无穷大时，该模型最终会在随机梯度下降抽样完训练集上的所有样本之前收敛到可能的最优测试误差。继续增加m不会延长达到模型可能的最优测试误差的时间。从这点来看，我们可以认为用SGD训练模型的渐近代价是关于m的函数的O(1)级别。
在深度学习兴起之前，学习非线性模型的主要方法是结合核技巧的线性模型。很多核学习算法需要构建一个m×m的矩阵。构建这个矩阵的计算量是O(m2)。当数据集是几十亿个样本时，这个计算量是不能接受的。在学术界，深度学习从2006年开始受到关注的原因是，在数以万计样本的中等规模数据集上，深度学习在新样本上比当时很多热门算法泛化得更好。不久后，深度学习在工业界受到了更多的关注，因为其提供了一种训练大数据集上的非线性模型的可扩展方式。
我们将会在第8章继续探讨随机梯度下降及其很多改进方法。