# Newton-CG methods for nonconvex unconstrained optimization with H"older continuous Hessian

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 22 Nov 2023.

## Builds on (most cited first, 17 of 17)

- [Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent](https://mlsanity.com/paper/1711.10456/) (2017)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Neon2: Finding Local Minima via First-Order Oracles](https://mlsanity.com/paper/1711.06673/) (2017)
- [A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimization](https://mlsanity.com/paper/1803.02924/) (2018)
- [Gradient Descent Finds the Cubic-Regularized Non-Convex Newton Step](https://mlsanity.com/paper/1612.00547/) (2016)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization](https://mlsanity.com/paper/1706.03131/) (2017)
- [Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization](https://mlsanity.com/paper/1912.04365/) (2019)
- [NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization](https://mlsanity.com/paper/1712.01033/) (2017)
- [Parameter-free accelerated gradient descent for nonconvex minimization](https://mlsanity.com/paper/2212.06410/) (2022)
- [Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization](https://mlsanity.com/paper/1709.07180/) (2017)
- [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)
- [A Parameter-Free Conditional Gradient Method for Composite Minimization under H"older Condition](https://mlsanity.com/paper/2305.18181/) (2023)
- [Gradient Method With Inexact Oracle for Composite Non-Convex Optimization](https://mlsanity.com/paper/1703.09180/) (2017)
- [Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints](https://mlsanity.com/paper/1811.01220/) (2018)
- [Universal regularization methods - varying the power, the smoothness and the accuracy](https://mlsanity.com/paper/1811.07057/) (2018)
- [Riemannian Adaptive Regularized Newton Methods with H"older Continuous Hessians](https://mlsanity.com/paper/2309.04052/) (2023)

## Abstract (arXiv)

In this paper we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with H"older continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate first- and second-order stationary point of this problem, assuming the associated the H"older parameters are explicitly known. Then we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To the best of our knowledge, this method is the first parameter-free second-order method achieving the best-known iteration and operation complexity for finding an approximate first- and second-order stationary point of this problem. Finally, we present preliminary numerical results to demonstrate the superior practical performance of our parameter-free Newton-CG method over a well-known regularized Newton method.