2020/06/02 by Truong, Tuyen Trung, To, Tat Dat, Nguyen, Tuan Hang +3 · 1 citation
#Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2006.01512
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=∇ 2f(xn)+δn||∇ f(xn)||2.Id and vn=An-1.∇ 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.