# A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization

arXiv: https://arxiv.org/abs/1803.02924 · HTML: https://mlsanity.com/paper/1803.02924/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2018.

## Built on by (most cited first, 23 of 23)

- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Escaping strict saddle points of the Moreau envelope in nonsmooth optimization](https://mlsanity.com/paper/2106.09815/) (2021)
- [Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods](https://mlsanity.com/paper/2412.02175/) (2024)
- [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023)
- [NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Information](https://mlsanity.com/paper/2510.05516/) (2025)
- [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimism](https://mlsanity.com/paper/2510.03167/) (2025)
- [A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees](https://mlsanity.com/paper/2207.05697/) (2022)
- [A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization](https://mlsanity.com/paper/2301.04204/) (2023)
- [Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks](https://mlsanity.com/paper/2310.14901/) (2023)
- [A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees](https://mlsanity.com/paper/2310.18841/) (2023)
- [Newton methods based convolution neural networks using parallel processing](https://mlsanity.com/paper/2112.01401/) (2021)
- [Deep Learning Methods for Protein Family Classification on PDB Sequencing Data](https://mlsanity.com/paper/2207.06678/) (2022)
- [An Efficient Nonlinear Acceleration method that Exploits Symmetry of the Hessian](https://mlsanity.com/paper/2210.12573/) (2022)
- [Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points](https://mlsanity.com/paper/2211.00866/) (2022)
- [Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessian](https://mlsanity.com/paper/2311.13094/) (2023)
- [Efficient algorithms for regularized Poisson Non-negative Matrix Factorization](https://mlsanity.com/paper/2404.16505/) (2024)
- [Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problems](https://mlsanity.com/paper/2411.15769/) (2024)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)
- [A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxation](https://mlsanity.com/paper/2507.09148/) (2025)
- [A Parameter-Free First-Order Algorithm for Non-Convex Optimization with tildemkern1mu O(ε-5/3) Global Rate](https://mlsanity.com/paper/2605.02127/) (2026)
- [CG-GLORE: A Conjugate Gradient-Based Global-Local Regularization Network for Sparse-View CT Reconstruction](https://mlsanity.com/paper/2608.15246/) (2026)

## Abstract (arXiv)

We consider minimization of a smooth nonconvex objective function using an iterative algorithm based on Newton's method and the linear conjugate gradient algorithm, with explicit detection and use of negative curvature directions for the Hessian of the objective function. The algorithm tracks Newton-conjugate gradient procedures developed in the 1980s closely, but includes enhancements that allow worst-case complexity results to be proved for convergence to points that satisfy approximate first-order and second-order optimality conditions. The complexity results match the best known results in the literature for second-order methods.