论文标题
鞍点模型的立方正规化牛顿方法：全球和局部收敛分析
Cubic Regularized Newton Method for Saddle Point Models: a Global and Local Convergence Analysis
论文作者
论文摘要
在本文中，我们提出了一种立方正规化牛顿（CRN）方法，用于解决凸连接鞍点问题（SPP）。在每次迭代中，构建和解决了一个立方体的鞍点子问题，为迭代提供了搜索方向。通过正确选择的步骤，如果鞍点函数是梯度Lipschitz，并且强烈的convex-trong-trong-concove，则该方法将显示与全局线性和局部超级线性收敛速率收敛到鞍点。如果该函数仅是凸连接的，则我们提出了一种同型延续（或路径遵循）方法。在Lipschitz-type误差绑定条件下，我们提出了$ \ MATHCAL {O} \ left的迭代复杂性界限（\ ln \ left（\ ln \ left（1/ε\ right）\ right）$ $ right）$，以达到$ε$ - $ - $ε$ - 实现同型持续方法，并且迭代复杂性界限变为$ \ MATHCAL {O} \ left（\ left（1/ε\ right）^{\ frac {1-θ} {θ^2}}} \ right）$ right条件下涉及涉及参数$θ$（$ 0<θ<θ<1 $）的条件。
In this paper, we propose a cubic regularized Newton (CRN) method for solving convex-concave saddle point problems (SPP). At each iteration, a cubic regularized saddle point subproblem is constructed and solved, which provides a search direction for the iterate. With properly chosen stepsizes, the method is shown to converge to the saddle point with global linear and local superlinear convergence rates, if the saddle point function is gradient Lipschitz and strongly-convex-strongly-concave. In the case that the function is merely convex-concave, we propose a homotopy continuation (or path-following) method. Under a Lipschitz-type error bound condition, we present an iteration complexity bound of $\mathcal{O}\left(\ln \left(1/ε\right)\right)$ to reach an $ε$-solution through a homotopy continuation approach, and the iteration complexity bound becomes $\mathcal{O}\left(\left(1/ε\right)^{\frac{1-θ}{θ^2}}\right)$ under a Hölderian-type error bound condition involving a parameter $θ$ ($0<θ<1$).
