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

Code

• github.com/hphuongdhsp/Q-Newton-method
  OfficialIn papernone★ 2

Abstract

We propose in this paper New Q-Newton's method. The update rule is very simple conceptually, for example x_n+1=x_n-w_n where w_n=pr_A_n,+(v_n)-pr_A_n,-(v_n), with A_n= ^2f(x_n)+ _n|| f(x_n)||^2.Id and v_n=A_n^-1. f(x_n). Here _n is an appropriate real number so that A_n is invertible, and pr_A_n, are projections to the vector subspaces generated by eigenvectors of positive (correspondingly negative) eigenvalues of A_n. The main result of this paper roughly says that if f is C^3 (can be unbounded from below) and a sequence _n\, constructed by the New Q-Newton's method from a random initial point x_0, 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.

Tasks

Reproductions