论文标题
四分之一的规律性
Quartic Regularity
论文作者
论文摘要
在本文中，我们提出了新的线性收敛二阶方法，以最大程度地减少凸四分之一的多项式。该框架用于设计优化方案，该方案可以解决满足新规律性条件的一般凸问题。它假定了目标函数第四个衍生物的积极确定性和界限。对于此类问题，牛顿方法的适当的四分之一正规化具有全球线性收敛速率。我们讨论了该结果的几个重要后果。特别是，它可用于在高阶近端方案的框架中构造新的二阶方法。这些方法具有收敛速率$ \ tilde o（k^{ - p}）$，其中$ k $是迭代计数器，$ p $等于3、4或5，tilde表示在辅助问题的复杂性界限中存在对数因素，这是在每个迭代率上解决的。
In this paper, we propose new linearly convergent second-order methods for minimizing convex quartic polynomials. This framework is applied for designing optimization schemes, which can solve general convex problems satisfying a new condition of quartic regularity. It assumes positive definiteness and boundedness of the fourth derivative of the objective function. For such problems, an appropriate quartic regularization of Damped Newton Method has global linear rate of convergence. We discuss several important consequences of this result. In particular, it can be used for constructing new second-order methods in the framework of high-order proximal-point schemes. These methods have convergence rate $\tilde O(k^{-p})$, where $k$ is the iteration counter, $p$ is equal to 3, 4, or 5, and tilde indicates the presence of logarithmic factors in the complexity bounds for the auxiliary problems, which are solved at each iteration of the schemes.
