Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization
Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization
复制标题
DOI：
10.1137/17m1134329
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
C. Royer;Stephen J. Wright
中科院分区：
文献类型：
--
作者：
C. Royer;Stephen J. Wright
最近人们对寻找光滑函数的无约束局部最小值很感兴趣，部分原因是机器学习和鲁棒统计中这类问题的普遍存在。特别关注具有良好复杂性保证的算法。从这一角度分析了利用正则化和信任域的二阶牛顿型方法。最近更多的建议，主要基于一阶方法，也被证明可以享受最优的迭代复杂度，同时在计算成本上提供额外的保证。在本文中，我们提出了一种具有良好复杂性特性的算法，该算法与最近提出的其他方法在两个重要方面有所不同。首先，它只基于直线搜索：每一步都需要计算一个搜索方向，然后沿着该方向进行回溯直线搜索。其次，它的分析相当直接，主要依靠标准技术来证明回溯对目标的充分减少。在本文的后半部分，我们考虑了搜索方向的不精确计算，使用线性代数中的迭代方法：共轭梯度和Lanczos方法。对于这些更实用的方法，我们得到了修正的收敛性和复杂度结果。
There has been much recent interest in finding unconstrained local minima of smooth functions, due in part of the prevalence of such problems in machine learning and robust statistics. A particular focus is algorithms with good complexity guarantees. Second-order Newton-type methods that make use of regularization and trust regions have been analyzed from such a perspective. More recent proposals, based chiefly on first-order methodology, have also been shown to enjoy optimal iteration complexity rates, while providing additional guarantees on computational cost. In this paper, we present an algorithm with favorable complexity properties that differs in two significant ways from other recently proposed methods. First, it is based on line searches only: Each step involves computation of a search direction, followed by a backtracking line search along that direction. Second, its analysis is rather straightforward, relying for the most part on the standard technique for demonstrating sufficient decrease in the objective from backtracking. In the latter part of the paper, we consider inexact computation of the search directions, using iterative methods in linear algebra: the conjugate gradient and Lanczos methods. We derive modified convergence and complexity results for these more practical methods.