报码:从浅层模型到深度模型：概览机器学习优化算法(2)_本港台直播_J2开奖直播

从概念上讲，最小化光滑凸目标的最简单的方法是梯度下降法，具体分析参见 [ 62 ]。在这种方法中，从初始化估计值 w0 开始，通过下述公式迭代地更新权重估计值。

其中 αk > 0 是一个步长参数。步长序列 {αk} 的选择直接决定此算法的性能。在优化研究领域，人们普遍认为，在每次迭代中采用线性搜索来确定 {αk }，可以为解决各种类型的问题找到一个性能优越的算法。然而，对于机器学习应用程序来说，这种运算成本高昂，因为每次函数 F 的计算都需要传递整个数据集，如果 n 过大，很可能带来高昂的（训练）成本。

好在当每个αk 都设置为一个正的常数α且它是一个足够小的固定值时，从理论上分析，该算法的收敛性仍可以得到保证。（固定的步长常数在机器学习领域叫做学习率。但即使不是常数，也有人把αK 或整个序列 {αK } 叫做学习率）。该算法的收敛速度取决于函数 f 是强凸函数还是弱凸函数。

用于解决 L1 范数正则化的logistic回归问题的梯度下降和加速梯度下降拓展算法分别被称作 ISTA 和 FISTA。我们观察到，在这种情况下，即使λ> 0，目标函数也不会是强凸函数。只有目标函数为凸时 [5]，ISTA 和 FISTA 具有与其对应的平滑函数相同的次线性收敛速度。

梯度下降在 ML 训练过程中的一个重要特性就是计算出每次迭代中求解函数 F 的梯度的运算成本。在 ML 的训练过程中，单个梯度计算的成本通常是 O（ND），这个确实可以看到，例如，在正则化项为的情况中，函数 F 关于每一个特定的 w 的梯度是

2.1.2 随机梯度法

随机梯度法由于其用于最小化随机目标函数而在运筹学领域广为人知，同时也是 ML 社区中的一种特征优化算法。该算法最初由 Robbins 和 Monro [ 67 ] 在解决随机方程组问题时提出，值得注意的是，它可以用于最小化具有良好收敛性的随机目标，而且每次迭代的计算复杂度仅为 O（d）而不是 O（nd）（梯度下降中的计算复杂度）。

在每一次迭代中，随机梯度法都会计算梯度 F（Wk）的无偏估计 GK。该估计可以以及低的代价计算得到；例如，对于公式（12），某次迭代的随机梯度可被求解为

其中 Sk 被称作小批量，它的所有元素都是从总数据集 {1,...,n} 中按均匀分布选出来的。接下来的运算类似于梯度下降：

毫无疑问，该算法的关键在于选择步长序列 {αk}。不同于梯度下降，固定的步长（即学习率）不能保证算法会收敛到强凸函数 F 的最小值，而只保证收敛到最小值的邻域。

SGD 的收敛速度比梯度下降慢。尤其当函数 F 是强凸函数时，该算法只保证当 k ≥ O(1/ε) 时可以得到预期精度的解（即满足 E[F(wk)]-F(w) ≤ ε的解），而当函数 F 仅仅是凸函数时，只有在 k ≥ O(1/ε^2) [11] 时才能保证得出上述解。

另一方面，正如前文提及的，如果 Sk 的大小由一个常数限定（独立于 n 或 k 的常数），那么 SGD 的每次的迭代成本都比梯度下降法小 0（n）倍。

然而，在实际运用中，标准的 SGD 并不一定是解决机器学习中优化问题的最有效方法。事实上，机器学习和优化算法领域在开发改进或替代 SGD 方面进行了大量的积极研究。在随后的两部分中，我们将讨论两类方法：方差缩减法和二阶方法。但是在这两类方法以外，还有多种方法。例如，加有动量的 SGD 就是一个实践中被发现的性能好于好于标准 SGD 的拓展版 SGD。见下图算法 1

报码:从浅层模型到深度模型：概览机器学习优化算法