Line Search for Convex Minimization

L Orseau, M Hutter
[Google DeepMind]

凸优化线搜索

要点:

  • 动机：为了解决一维凸函数的准确最小化问题，特别是对于一些计算昂贵的通用凸函数，在梯度下降或Frank-Wolfe等算法中需要找到合适的步长。
  • 方法：提出两个准确的一维凸函数搜索算法，分别为∆-Bisection和∆-Secant。∆-Bisection利用凸性来提高收敛速度，使用梯度信息和凸性进行搜索。∆-Secant只使用函数查询，并通过优化搜索区间来提高收敛速度。在没有梯度信息或梯度计算成本较高时，∆-Secant比较适用。
  • 优势：所提出的算法在一维凸函数的最小化问题中，比传统的搜索算法(如bisection search和golden-section search)更快、更有效。论文还设计了基于∆-Secant的准确线搜索算法，对于多变量凸函数的最小化有着更好的收敛保证，比传统的backtracking line search更鲁棒且不需要精确调参。


提出两个准确的一维凸函数搜索算法和相应的准确线搜索算法，以提高搜索效率并获得更好的收敛保证。

https://arxiv.org/abs/2307.16560 


图片

内容中包含的图片若涉及版权问题，请及时与我们联系删除