# A Newton-MR algorithm with complexity guarantees for nonconvex smooth unconstrained optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2022.

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

- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Series of Hessian-Vector Products for Tractable Saddle-Free Newton Optimisation of Neural Networks](https://mlsanity.com/paper/2310.14901/) (2023)
- [First-ish Order Methods: Hessian-aware Scalings of Gradient Descent](https://mlsanity.com/paper/2502.03701/) (2025)

## Abstract (arXiv)

In this paper, we consider variants of Newton-MR algorithm for solving unconstrained, smooth, but non-convex optimization problems. Unlike the overwhelming majority of Newton-type methods, which rely on conjugate gradient algorithm as the primary workhorse for their respective sub-problems, Newton-MR employs minimum residual (MINRES) method. Recently, it has been established that MINRES has inherent ability to detect non-positive curvature directions as soon as they arise and certain useful monotonicity properties will be satisfied before such detection. We leverage these recent results and show that our algorithms come with desirable properties including competitive first and second-order worst-case complexities. Numerical examples demonstrate the performance of our proposed algorithms.