Primal Acceleration of Newton's Method

Nikita Doikov

math.OCAug 21, 2026

Primal Acceleration of Newton's Method

Authors: Nikita Doikov

Organizations: School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.

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.

Figures & tables

First-order methods: $\bm{H}_{k}=\bm{0}$ in ( 3 )
Method	Parameters		Convergence Rate, $F_{k}$
Gradient Descent	$\alpha_{k}=\frac{1}{L_{1}}$	$\beta_{k}=0$	$O\bigl(\frac{L_{1}R^{2}}{k}\bigr)$
Fast Gradient Method [ 28 ]	$\alpha_{k}=\frac{1}{L_{1}}\cdot\frac{k+1}{k+2}$	$\beta_{k}=\frac{k}{k+3}$	$O\bigl(\frac{L_{1}R^{2}}{k^{2}}\bigr)$
Second-order methods: $\bm{H}_{k}=\nabla^{2}f(\bm{y}_{k})$ in ( 3 )
Method	Parameters		Convergence Rate, $F_{k}$
Classical Newton’s Method	$\alpha_{k}=+\infty$	$\beta_{k}=0$	No global convergence

Table 1: Summary of optimization methods and their convergence rates in terms of the functional residual

F_{k}:=f(\bm{x}_{k})-f^{\star}

, and

O(\cdot)

hides an absolute numerical constant. We denote by

L_{1}

the Lipschitz constant of the gradient, and by

L_{2}

the Lipschitz constant of the Hessian, both measured w.r.t. the standard Euclidean norm. We denote by

D

the diameter of the initial sublevel set, and

R\geq\|\bm{x}_{0}-\bm{x}^{\star}\|_{2}

is an arbitrary bound for the initial distance to a solution

\bm{x}^{\star}

, which we assume to exist.

Second-Order Optimization

Second-order optimization uses curvature information, such as Hessians or their approximations, to choose efficient steps toward better solutions.

See all 90 papers

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima
Jul 13, 2023Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. BajwaNonconvex Optimization Accelerated Gradient Methods
Department of Electrical and Computer Engineering, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering, Management Science and Information Systems, and Statistics, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering and Statistics, Rutgers University–New Brunswick, NJ 08854 USA
A lower bound for stepsize-based acceleration of gradient descent
Aug 11, 2026Jianhao Ma, Yuxin ChenLearning Rate Scheduling Last-Iterate Convergence
Department of Industrial Engineering, Tsinghua University · Department of Statistics and Data Science, Wharton School, University of Pennsylvania
A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate
May 4, 2026Sichao Xiong, Sadok Jerad, Coralia CartisOptimization Convergence Analysis Gradient Descent
Department of Computer Science University of Oxford Oxford, OX1 3QG · Mathematical Institue University of Oxford Oxford, OX2 6GG

Jul 13, 2023J/K move · Enter open · S save

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

Rishabh Dixit, Mert Gurbuzbalaban, Waheed U. Bajwa

Department of Electrical and Computer Engineering, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering, Management Science and Information Systems, and Statistics, Rutgers University–New Brunswick, NJ 08854 USA · Departments of Electrical & Computer Engineering and Statistics, Rutgers University–New Brunswick, NJ 08854 USA

Nonconvex Optimization Accelerated Gradient Methods Optimization Convergence Analysis

Open paper AskPDF arXiv

This paper considers the problem of understanding the behavior of a general class of accelerated gradient methods on smooth nonconvex functions. Motivated by some recent works that have proposed effective algorithms, based on Polyak's heavy ball method and the Nesterov accelerated gradient method, to achieve convergence to a local minimum of nonconvex functions, this work proposes a broad class of Nesterov-type accelerated methods and puts forth a rigorous study of these methods encompassing the escape from saddle points and convergence to local minima through both an asymptotic and a non-asymptotic analysis. In the asymptotic regime, this paper answers an open question of whether Nesterov's accelerated gradient method (NAG) with variable momentum parameter avoids strict saddle points almost surely. This work also develops two metrics of asymptotic rates of convergence and divergence, and evaluates these two metrics for several popular standard accelerated methods such as the NAG and Nesterov's accelerated gradient with constant momentum (NCM) near strict saddle points. In the non-asymptotic regime, this work provides an analysis that leads to the "linear" exit time estimates from strict saddle neighborhoods for trajectories of these accelerated methods as well the necessary conditions for the existence of such trajectories. Finally, this work studies a sub-class of accelerated methods that can converge in convex neighborhoods of nonconvex functions with a near optimal rate to a local minimum and at the same time this sub-class offers superior saddle-escape behavior compared to that of NAG.

Abstract

Second-Order Optimization

Explore similar work

Accelerated Gradient Methods for Nonconvex Optimization: Escape Trajectories From Strict Saddle Points and Convergence to Local Minima

A lower bound for stepsize-based acceleration of gradient descent

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with O~(ε−5/3)\tilde{\mkern1mu O}(ε^{-5/3})O~(ε−5/3) Global Rate

A Parameter-Free First-Order Algorithm for Non-Convex Optimization with $\tilde{\mkern1mu O}(ε^{-5/3})$ Global Rate