论文标题
用于凸优化及其滑动的近乎最佳的超快速二阶方法
Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
论文作者
论文摘要
在本文中，我们提出了一种新的Hyperfast二阶方法，其收敛速率$ o（n^{ - 5}）$ to convex函数的对数因子与第三个导数。此方法基于两个想法。第一个来自Yu的超快速二阶方案。 Nesterov（核心讨论文件2020/07，2020）。它允许仅使用二阶Oracle解决子问题来实现三阶方案。此方法与速率$ o（n^{ - 4}）$收敛。第二个想法来自Kamzolov等人的工作。 （ARXIV：2002.01004）。这是不确定的近三阶方法。在这项工作中，我们改善了其收敛性，并将其与仅使用二阶Oracle解决子问题的方案合并。结果，我们将收敛速率$ o（n^{ - 5}）$提高到对数因子。这种收敛速度几乎是最佳的，并且到目前为止是最著名的。此外，我们研究了有两个函数总和并改善Kamzolov等人的滑动框架的情况。 （ARXIV：2002.01004）对于二阶方法。
In this paper, we present a new Hyperfast Second-Order Method with convergence rate $O(N^{-5})$ up to a logarithmic factor for the convex function with Lipshitz the third derivative. This method based on two ideas. The first comes from the superfast second-order scheme of Yu. Nesterov (CORE Discussion Paper 2020/07, 2020). It allows implementing the third-order scheme by solving subproblem using only the second-order oracle. This method converges with rate $O(N^{-4})$. The second idea comes from the work of Kamzolov et al. (arXiv:2002.01004). It is the inexact near-optimal third-order method. In this work, we improve its convergence and merge it with the scheme of solving subproblem using only the second-order oracle. As a result, we get convergence rate $O(N^{-5})$ up to a logarithmic factor. This convergence rate is near-optimal and the best known up to this moment. Further, we investigate the situation when there is a sum of two functions and improve the sliding framework from Kamzolov et al. (arXiv:2002.01004) for the second-order methods.
