梯度下降可能有两种效率低下的方式。有趣的是，他们每个人都有自己的修复方法，这几乎是相反的解决方案。这两个问题是：

(1) 需要太多的梯度下降更新。

(2) 每个梯度下降步骤都太昂贵了。

关于（1），将梯度下降与考虑二阶导数信息的方法进行比较，梯度下降在改善每次迭代的损失方面往往效率很低。一种非常标准的方法，牛顿法，通常需要更少的迭代来收敛，即对于逻辑回归，牛顿法的 10 次迭代通常比梯度下降 5,000 次迭代所提供的解决方案具有更低的损失。对于线性回归，这更加极端；有一个封闭形式的解决方案！然而，随着预测变量的数量变得非常大（即 500+），牛顿法/直接求解线性回归可能会变得过于昂贵每次迭代由于需要大量的矩阵运算，而梯度下降每次迭代的成本将大大降低。

关于（2），有可能拥有如此大的数据集，以至于梯度下降的每次迭代都太昂贵而无法计算。计算梯度将需要操作（ = 样本大小， = 协变量数）。虽然的值根本不是问题，但肯定会出现类似、的问题。在这种情况下，基于较小的数据子集来近似导数的方法更具吸引力，例如随机梯度下降。$O(nk)$$n$$k$$n = 10^{6}$$k < 100$$n = 10^{12}$$k = 10^3$

我说这些修复几乎是相反的，因为像牛顿法这样的方法每次更新成本更高但效率更高（就损失的变化而言），而随机梯度下降实际上效率较低但每次更新的计算成本要低得多。

首先让我建议对您的符号进行改进。特别是，让我们用而不是来表示损失函数。使用字母只是我个人的偏好，因为它提醒我我们正在处理L oss。更实质性的变化是清楚地表明损失是权重而不是数据的函数。重要的是，梯度是相对于而不是的。所以 其中是你的维度数据。$L(w)$$f(x)$$L$$w$$x$$w$$x$

$$\nabla L(w) = \left(\frac{\partial L}{\partial w_1}, \dots, \frac{\partial L}{\partial w_D} \right),$$ $D$

尽管我们应该将损失视为权重的函数，但任何合理的损失函数仍将取决于整个数据集（如果不是，则无法从数据中学到任何东西！ ）。例如，在线性回归中，我们通常使用平方和损失函数 因此，评估一组特定权重将需要对数据集个点求和。如果，那么梯度下降优化中的每个增量步骤都需要大约一百万次操作，这非常昂贵。$w$$x$

$$L(w) = \sum_{i=1}^N (y_i - w^Tx_i)^2.$$ $\nabla L(w)$$w$$N$$x$$N = 10^6$

如果您为梯度下降低效的说法提供背景信息，将会有所帮助。相对于什么效率低下？

我猜这里缺少的上下文是与机器学习中的随机或批量梯度下降的比较。以下是在这种情况下如何回答这个问题。您正在优化模型的参数，甚至是超参数。因此，您有成本函数，其中 - 您的数据， - 参数向量，以及 - 损失函数。为了最小化这个成本，你在参数上使用梯度下降： $\sum_{i=1}^n L(x_i|\Theta)$$x_i$$\Theta$$L()$ $\theta_j$

$$\frac{\partial}{\partial \theta_j}\sum_{i=1}^nL(\Theta|x_i)$$

因此，您看到您需要获得所有数据的总和。这是不幸的，因为这意味着你在梯度下降的每一步都在循环遍历数据。这就是批量和随机梯度下降的出现方式：如果我们从数据集中进行采样，并计算样本的梯度，而不是整个集呢？ 这里，是样本中的观测数。因此，如果您的样本是总样本的 1/100，那么您的计算速度将提高 100 倍！的速率降低$x_{i=1,\dots,n}$

$$\frac{\partial}{\partial \theta_j}\sum_{k=1}^{n_s}L(\Theta|x_k)$$ $n_s$$s$$\sqrt n$而计算量在处增加，所以这个技巧可能会奏效。$n$

或者，而不是等到计算出全部总和，您可以将其分成批次，并为每个批次做一个步骤。这样，在计算整个数据集的总和时，您将完成 M 步。这些将是嘈杂的步骤，但随着时间的推移噪音会被抵消。$\sum_{i=1}^n$$\sum_{s=1}^M\sum_{i_s=1}^{n_s}$

简短回答：计算梯度需要对所有数据点求和。如果我们有大量数据，则需要很长时间。

我这里有详细的回答。

与标准梯度下降相比，随机梯度下降如何节省时间？

---

另一方面，请始终记住，除了迭代方法（梯度体面）之外，还有直接方法。如果我们想解决最小二乘问题，直接法可能非常有效。例如，QR 分解。如果我们没有太多的特征，它是非常快的。

当您验证它时，您可能会感到惊讶：500 万个数据点具有 2 个特征，求解线性回归/最小二乘需要几秒钟！

x=matrix(runif(1e7),ncol=2)
y=runif(5e6)
start_time <- Sys.time()
lm(y~x)
end_time <- Sys.time()
end_time - start_time
# Time difference of 4.299081 secs