mlsanityData to 14 Oct 2026

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

arXiv 1803.02924 ↗First posted 8 Mar 2018math.OCcited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 6; 2024: 3; 2025: 4; 2026: 2.

23 papers.

Sort:

  1. 2022Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexitycited by 17
  2. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  3. 2024Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methodscited by 7
  4. 2023A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guaranteescited by 6
  5. 2025NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Informationcited by 6
  6. 2022Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decompositioncited by 5
  7. 2023Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketchingcited by 5
  8. 2025Improving Online-to-Nonconvex Conversion for Smooth Optimization via Double Optimismcited by 3
  9. 2022A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guaranteescited by 2
  10. 2023A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimizationcited by 2
  11. 2023Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networkscited by 1
  12. 2023A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guaranteescited by 1
11 more
  1. 2021Newton methods based convolution neural networks using parallel processingcited by 0
  2. 2022Deep Learning Methods for Protein Family Classification on PDB Sequencing Datacited by 0
  3. 2022An Efficient Nonlinear Acceleration method that Exploits Symmetry of the Hessiancited by 0
  4. 2022Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle pointscited by 0
  5. 2023Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessiancited by 0
  6. 2024Efficient algorithms for regularized Poisson Non-negative Matrix Factorizationcited by 0
  7. 2024Gradient Norm Regularization Second-Order Algorithms for Solving Nonconvex-Strongly Concave Minimax Problemscited by 0
  8. 2025What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?cited by 0
  9. 2025A Randomized Algorithm for Sparse PCA based on the Basic SDP Relaxationcited by 0
  10. 2026A Parameter-Free First-Order Algorithm for Non-Convex Optimization with tildemkern1mu O(ε-5/3) Global Ratecited by 0
  11. 2026CG-GLORE: A Conjugate Gradient-Based Global-Local Regularization Network for Sparse-View CT Reconstructioncited by 0