L-BFGS 在非凸设置中的收敛

机器算法验证 优化
2022-03-29 04:02:08

即使学习率真的很小,通常 L-BFGS 可能不会在非凸设置中收敛,这是真的吗?

例如这里的 L-BFGS 发散,但它的局部收敛有理论上的保证。这怎么解释?

1个回答

是的,即使学习率非常小,L-BFGS-B 算法也不会收敛于真正的全局最小值。

使用准牛顿法意味着你试图找到最优的θ使用类似于以下的迭代方案:θk+1=θkαSkgk在哪里θ是您优化的参数,k索引您所在的迭代,α是你的学习率,S是与系统相关的“Hessian-like”矩阵A你试图解决和g是梯度,通常Sk=0=I. (请注意,如果S=A1你得到了简单的牛顿法,如果S=I你会得到标准的最速下降算法。)

现在你看到学习率α仅以算法更新其当前解决方案的方式进入该方案。有一个非常小的α只会确保您更突出地使用局部梯度信息,以牺牲 Hessian 信息。为了与您引用的论文相提并论,这就是 L-BFGS-B 在优化L2在梯度下降总是收敛时进行的正则化回归。非常低α保证你最终会收敛到局部最小值,但代价是学习率低。

说了这么多,非凸性意味着(但不等于)存在多个局部最小值。上面的方案保证你会为每个给定的找到其中一个θ0. 虽然收敛到一个特定的最小值并不能保证你会收敛到全局最小值,只是在存在许多本地最小值的情况下,你会选择一个更接近你的θ0. 请注意,L-BFGS-B 在用于至少局部可微的凸目标/损失函数时效果最佳。这就是为什么在稳健回归的情况下它们会失败(相当悲惨);Hessian 信息完全混乱,算法卡住了。这在作者不错的情节中得到了进一步强调2(c)你会看到梯度下降在一段时间后就像疯了一样反弹,因为即使是一阶梯度信息也不是很丰富。正如评论中所指出的,还有其他替代 BFGS 的更新方案(例如SR-1)可以在标准 BFGS 更新失败的情况下处理非凸性。