# Generalisations and improvements of New Q-Newton's method Backtracking

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 15 references that are in the map.
- First posted on arXiv 23 Sep 2021.

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

- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [Convergence to minima for the continuous version of Backtracking Gradient Descent](https://mlsanity.com/paper/1911.04221/) (2019)
- [Some convergent results for Backtracking Gradient Descent method on Banach spaces](https://mlsanity.com/paper/2001.05768/) (2020)
- [New Q-Newton's method meets Backtracking line search: good convergence guarantee, saddle points avoidance, quadratic rate of convergence, and easy implementation](https://mlsanity.com/paper/2108.10249/) (2021)

## Abstract (arXiv)

In this paper, we propose a general framework for the algorithm New Q-Newton's method Backtracking, developed in the author's previous work. For a symmetric, square real matrix A, we define minsp(A):=min ||e||=1 ||Ae||. Given a C2 cost function f:ℝmrightarrow ℝ and a real number 0<τ , as well as m+1 fixed real numbers δ 0,ldots ,δ m, we define for each x∈ ℝm with nabla f(x)not= 0 the following quantities: kappa :=min inot= j|δ i-δ j|; A(x):=nabla 2f(x)+δ ||nabla f(x)||τId, where δ is the first element in the sequence δ 0,ldots ,δ m for which minsp(A(x))≥ kappa ||nabla f(x)||τ; e1(x),ldots ,em(x) are an orthonormal basis of ℝm, chosen appropriately; w(x)= the step direction, given by the formula: w(x)=sum i=1mfrac<nabla f(x),ei(x)>||A(x)ei(x)||ei(x); (we can also normalise by w(x)/max 1,||w(x)|| when needed) γ (x)>0 learning rate chosen by Backtracking line search so that Armijo's condition is satisfied: f(x-γ (x)w(x))-f(x)≤ -frac13γ (x)<nabla f(x),w(x)>. The update rule for our algorithm is xmapsto H(x)=x-γ (x)w(x). In New Q-Newton's method Backtracking, the choices are τ =1+α >1 and e1(x),ldots ,em(x)'s are eigenvectors of nabla 2f(x). In this paper, we allow more flexibility and generality, for example τ can be chosen to be <1 or e1(x),ldots ,em(x)'s are not necessarily eigenvectors of nabla 2f(x). New Q-Newton's method Backtracking (as well as Backtracking gradient descent) is a special case, and some versions have flavours of quasi-Newton's methods. Several versions allow good theoretical guarantees. An application to solving systems of polynomial equations is given.