有多少百分比的机器学习算法本质上是迭代的；即我可以按顺序运行它们

来自深度学习书籍 ch5, SGD

机器学习中一个反复出现的问题是大型训练集对于良好的泛化是必要的，但大型训练集的计算成本也更高。

在深度学习出现之前，学习非线性模型的主要方法是将核技巧与线性模型结合使用。许多核学习算法需要构造一个 m×m 矩阵。构建此矩阵的计算成本为 O(m^2)，这对于具有数十亿示例的数据集显然是不可取的。

一般来说，梯度下降通常被认为是缓慢或不可靠的。过去，将梯度下降应用于非凸优化问题被认为是鲁莽或无原则的，优化算法可能无法保证在合理的时间内达到甚至局部最小值，但它经常会发现一个非常低的成本函数的值足够快以至于有用

基于梯度下降的方法，基本前提是您根据随机的一小部分训练数据（batch）估计梯度并相应地更新权重，算法将在两个步骤之间迭代地保持交替，直到满足某个目标（在参数空间中找到一个好的局部最小值），该过程称为随机梯度下降（SGD 的见解是梯度是一个期望值。该期望值可以使用一小组样本近似估计）。
在极端情况下，梯度是基于一个示例进行估计的，（在线学习）
请参阅Practical Recommendations for Gradient-Based Training of Deep Architectures

这些模型的运行时间或准确性是否存在一些折衷

对于固定的模型大小，每次 SGD 更新的成本不取决于训练集大小 m。在实践中，随着训练集大小的增加，我们经常使用更大的模型，但我们并非被迫这样做。达到收敛所需的更新次数通常随着训练集的大小而增加。然而，随着 m 接近无穷大，模型最终会在 SGD 对训练集中的每个示例进行采样之前收敛到其最佳可能的测试误差。进一步增加 m 不会延长达到模型最佳可能测试错误所需的训练时间。从这个角度来看，可以说用 SGD 训练模型的渐近成本是 O(1) 作为 m 的函数。