跳转至

牛顿法的原始加速

文章背景与核心概要

本文介绍了一种针对具有 Lipschitz 连续 Hessian 矩阵的凸函数最小化问题的全新直接加速牛顿法。该算法完全在原始域（primal domain）内运行，且每次迭代仅需进行一次线性求解，无需辅助的非线性子问题、参数搜索或对偶修正。

该方法在函数残差方面实现了 \(O(1/k^3)\) 的全局收敛速度。据作者所知，这是首个在保持单次线性求解效率的同时达到该收敛速率的二阶方法。此外，该算法支持通过不精确线性求解器实现无 Hessian（Hessian-free）计算，并可通过 Bregman 散度和复合优化问题扩展至任意几何结构。

文章详情

  • 标题： Primal Acceleration of Newton's Method
  • 作者： Nikita Doikov
  • 提交日期： 2026年8月21日
  • 主要学科： 优化与控制 (math.OC)
  • 次要学科： 人工智能 (cs.AI)，机器学习 (cs.LG)
  • arXiv ID： arXiv:2608.21359 [math.OC]
  • DOI： 10.48550/arXiv.2608.21359

摘要

我们开发了一种新的直接加速牛顿法，用于最小化具有 Lipschitz 连续 Hessian 的凸函数。该算法仅使用原始变量，且每次迭代仅执行一次线性求解。通过简单的预定参数选择，它在函数残差方面实现了 \(O(1/k^3)\) 的全局收敛速度。据我们所知，这是针对此类问题首个在每次迭代仅依赖一次线性系统求解（无需解决辅助非线性正则化子问题，如三次正则化，无需执行非线性参数搜索，也无需使用对偶外梯度修正）的情况下达到该速率的二阶方法。我们的方法可以通过不精确线性系统求解器以无 Hessian 的方式实现，同时保持快速的全局收敛速度。我们进一步通过 Bregman 散度将我们的构造扩展到了任意几何结构，并推广到了复合优化问题。

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.

链接与资源