algorithm - 批处理和随机梯度下降之间的算法复杂度差异是什么

Question

批量梯度下降是：θj:=θj+α∑(yi-h(xi))xji 对于每个j.

随机梯度下降是：

loop
{  
   for i=1 to m,
   {
       θj:=θj+α(yi-h(xi))xji   for every j.
   }
}

我很好奇两种算法之间的复杂性差异。我认为复杂性是一样的！两者都是 O(m*n)，但是批量梯度是 m*n，随机是 n*m，只是顺序不同，对吗？

score 2 · Accepted Answer

A) 这不是你会做 SGD 的方式。你会随机选择“i”，或者在每一轮中随机播放数据。

B）只有当你决定只对数据执行固定数量的 epoch 时，你才是正确的。

实际上，您可能希望继续运行该算法，直到您收敛到一个解决方案。SGD 和 GD 的收敛速度不同，并不是“运行时大 O(f(x))”那么简单。每种方法需要不同的时间来达到不同的目标。这些进一步变化取决于您的损失函数和其他因素。

在实践中不使用 GD，因为如果您打算每个 epoch 只执行一次更新，还有更好的选择。

C）“m*n，随机数是 n*m，只是顺序不同，对吗？” 如果您的大 O 语句是正确的，那将是正确的。

D）你忘记在你的大 O 中包含问题的维度。

score 0 · Accepted Answer

这两种方法的渐近复杂度在某种意义上是相同的。如果您在外部循环的多次迭代中都运行这两种方法，您会渐近地完成相同数量的工作。不同之处在于方法的实际行为方式。

通常，随机梯度下降被用作处理非常大的训练集的一种方式。假设您的训练集中有十亿个项目。批量梯度下降每次更新模型参数（theta）时都需要遍历所有十亿个项目。随机梯度下降在为每个处理的训练集项目拟合模型参数（尽管增量较小）方面不断取得进展。

如果您的训练数据集非常大，并且您的排序没有任何偏差，您可以（如您所示）简单地按顺序重复循环遍历数据集。事实上，连续运行数据集没有使用不同的顺序，这在实践中应该不是问题。

2 回答 2