Paper Overview
- Field: Machine Learning
- Author: Nikita Doikov
- Published: 2026-08-21
- arXiv: 2608.21359
- Direct primal acceleration: acceleration is achieved directly on Newton's method, without dual variables or extragradient corrections
- One linear solve per iteration: unlike cubic regularization or related approaches, no auxiliary nonlinear subproblems must be solved
- Global O(1/k^3) rate in functional residual with simple predetermined parameters
- Hessian-free implementation is possible using inexact linear system solvers while retaining the fast global rate
- Generalizations to arbitrary geometry via Bregman divergences and to composite optimization
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. The construction is further extended to arbitrary geometries (via Bregman divergences) and to composite optimization problems.
Key Contributions
*Auto-collected on 2026-08-25*