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

arXiv2006.01512MaRDI QIDQ6341898

Author name not available (Why is that?)

Publication date: 2 June 2020

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} = p r_{A_{n}, +} (v_{n}) - p r_{A_{n}, -} (v_{n})

, with

A_{n} = a b l a^{2} f (x_{n}) + d e l t a_{n} | | a b l a f (x_{n}) | |^{2} . I d

and

v_{n} = A_{n}^{- 1} . a b l a f (x_{n})

. Here

d e l t a_{n}

is an appropriate real number so that

A_{n}

is invertible, and

p r_{A_{n}, p m}

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

x_{n}

, constructed by the New Q-Newton's method from a random initial point

x_{0}

, {�f 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.

Has companion code repository: https://github.com/hphuongdhsp/Q-Newton-method

This page was built for publication: A fast and simple modification of Newton's method helping to avoid saddle points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341898)