提出一种无需求解复杂子问题的加速牛顿法，每步仅需一次线性求解。
Primal Acceleration of Newton's Method
- 仅使用原始变量，每轮迭代一次线性求解即可
- 全局收敛率达 $O(1/k^3)$，为该类问题最优速率
- 可无海森矩阵实现，适合大规模优化场景
我们提出一种新的直接加速牛顿法，用于最小化Hessian Lipschitz连续的凸函数。该算法仅使用原始变量，每轮迭代仅需一次线性求解。通过一个简单的预设参数选择，其函数残差达到全局收敛率 $O(1/k^3)$。据我们所知，这是首个在该问题类别中达到此速率且每轮仅需一次线性系统求解的方法（无需求解辅助非线性正则化子问题，如三次正则化，也无需非线性参数搜索或对偶外梯度修正）。该方法可采用近似线性求解器实现，同时保持快速全局收敛率。我们进一步将该构造推广至任意几何（通过Bregman散度）和复合优化问题。
原文摘要 · Abstract (English)
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of $O(1/k^3)$ in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。