Inexact Newton-CG algorithms with complexity guarantees
Inexact Newton-CG algorithms with complexity guarantees
复制标题
DOI：
10.1093/imanum/drac043
复制
发表时间：
2021-09
影响因子：
2.1
通讯作者：
Z. Yao;Peng Xu;Fred Roosta;Stephen J. Wright;Michael W. Mahoney
中科院分区：
文献类型：
--
作者：
Z. Yao;Peng Xu;Fred Roosta;Stephen J. Wright;Michael W. Mahoney
我们考虑最近开发的Newton-CG算法的变体用于非凸问题（Royer，C。W. & Wright，S. J.（2018）光滑非凸优化的二阶线搜索算法的复杂性分析。SIAM J. Optim.，28，1448-1477），其中梯度和Hessian信息的不精确估计用于各个步骤。在一定的条件下的不精确措施，我们得到迭代复杂性的界限，以达到$\N $-近似二阶最优匹配最佳已知的下限。我们对梯度的不精确条件是自适应的，允许在具有大梯度的区域中的粗略精度。我们描述了我们的方法的两个变体，其中一个是自适应地选择步长沿着计算的搜索方向，另一个是预定义的步长。为了获得二阶最优性，我们的算法将在某些步骤上使用负曲率方向。这些方向可以使用随机Lanczos算法以高概率获得。从这个意义上说，我们所有的结果在算法的运行中具有很高的概率。我们在几个机器学习模型上根据经验评估了我们提出的算法的性能。我们的方法是第一次尝试将不精确的Hessian和/或梯度信息引入Royer & Wright的Newton-CG算法（2018，用于光滑非凸优化的二阶线搜索算法的复杂性分析。SIAM J. Optim.，28，1448-1477）。
We consider variants of a recently developed Newton-CG algorithm for nonconvex problems (Royer, C. W. & Wright, S. J. (2018) Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477) in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving $\epsilon $-approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step size along the computed search direction is chosen adaptively, and another in which the step size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high probability, using the randomized Lanczos algorithm. In this sense, all of our results hold with high probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models. Our approach is a first attempt to introduce inexact Hessian and/or gradient information into the Newton-CG algorithm of Royer & Wright (2018, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477).