Primal Acceleration of Newton's Method
2026-08-21 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors created a new faster method to find the lowest point of certain smooth, bowl-shaped functions. Their approach uses only the main variables and needs to solve just one set of linear equations in each step, making it simpler than existing methods. They proved their method is globally fast, improving function values at a rate proportional to 1 over the step number cubed, and it doesn’t need complicated extra calculations. They also made their method flexible to work with different problem shapes and combined it with other optimization problems.
convex optimizationNewton's methodLipschitz continuous Hessianglobal convergence ratelinear system solveBregman divergencecomposite optimizationsecond-order methodsfunctional residualHessian-free optimization
Authors
Nikita Doikov
Abstract
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.