如何定义梯度下降的终止条件?

机器算法验证 算法 优化 梯度下降
2022-02-05 02:36:04

实际上,我想问你如何定义梯度下降的终止条件。

我可以根据迭代次数停止它吗,即考虑参数值,比如 100 次迭代?

或者我应该等待两个参数值 'new' 和 'old' 的差异非常小到让我们说的顺序?这肯定需要很多时间。106

什么是最好的方法?在我的情况下,即使是一次迭代也需要大量时间。在这种情况下,如果我等待第二种情况,我猜它甚至可能需要数周时间。

那么我应该使用哪种方法。如何应对这种情况?

1个回答

好问题。我在文献中看到了很多停止规则,每个规则都有优点和缺点,具体取决于上下文。例如,R 中的optim函数至少有三个不同的停止规则:

  • maxit,即预定的最大迭代次数。我在文献中看到的另一个类似选择是超时前的最大秒数。如果您只需要一个近似的解决方案,这可能是一个非常合理的方案。事实上,有些模型(尤其是线性模型)的提前停止类似于在参数值上放置高斯先验。常客会说你有一个“L2 规范”而不是先验,但他们也会认为这是一件合理的事情。我只是略读了这篇论文,但它讨论了提前停止和正则化之间的关系,可能会帮助您获得更多信息。但简短的版本是,是的,提前停止可能是一件非常受人尊敬的事情,这取决于你做什么

  • abstol,即当函数“足够接近”为零时停止。这可能与您无关(听起来您并不期待零),所以我将跳过它。

  • reltol,这就像你的第二个建议——当改进低于阈值时停止。我实际上不知道这方面有多少理论,但是与使用少量最大迭代次数相比,您可能会倾向于通过这种方式获得更低的最小值。如果这对您很重要,那么运行代码进行更多迭代可能是值得的。

另一类停止规则与优化验证数据集(或交叉验证)而不是训练数据上的成本函数有关。根据您要使用模型的目的,您可能希望在训练数据达到局部最小值之前停止,因为这可能涉及过度拟合。我很确定 Trevor Hastie 写过关于这样做的好方法,但我不记得引用了。

在合理的时间内找到较低最小值的其他可能选项包括:

  • 随机梯度下降,它只需要一次估计一小部分数据的梯度(例如,“纯”SGD 的一个数据点,或小批量)。

  • 更高级的优化函数(例如牛顿型方法或共轭梯度),它们使用有关目标函数曲率的信息来帮助您指向更好的方向并在下坡时采取更好的步长。

  • 更新规则中的“动量”术语,以便优化器在下坡方面做得更好,而不是在目标函数中限制峡谷壁。

这些方法都在我在网上找到的这些讲义中讨论过。

希望这可以帮助!

编辑哦,您还可以尝试获得更好的起始值(例如,通过解决问题的更简单版本),以便从“热启动”获得接近最佳值的迭代次数更少。