A fast and simple modification of Newton's method helping to avoid saddle points

We propose in this paper New Q-Newton's method. The update rule is very simple conceptually, for example xn+1=xn-wn where wn=prAn,+(vn)-prAn,-(vn), with An=nabla 2f(xn)+δ n||nabla f(xn)||2.Id and vn=An-1.nabla f(xn). Here δ n is an appropriate real number so that An is invertible, and prAn,± are projections to the vector subspaces generated by eigenvectors of positive (correspondingly negative) eigenvalues of An. The main result of this paper roughly says that if f is C3 (can be unbounded from below) and a sequence xn, constructed by the New Q-Newton's method from a random initial point x0, bf converges, then the limit point is a critical point and is not a saddle point, and the convergence rate is the same as that of Newton's method. The first author has recently been successful incorporating Backtracking line search to New Q-Newton's method, thus resolving the convergence guarantee issue observed for some (non-smooth) cost functions. An application to quickly finding zeros of a univariate meromorphic function will be discussed. Various experiments are performed, against well known algorithms such as BFGS and Adaptive Cubic Regularization are presented.