Problem (REF ) is arguably the most basic optimization problem, which nevertheless arises in many applications in machine learning and statistics [1]}, [2]}, [3]}, [4]}. There is a plethora of methods for solving (REF ), and each (type of) method has its own benefits under favorable settings. This paper particularly focuses on solving (REF ) via second-order methods, where a (approximated) Hessian matrix is involved in the scheme. Consider vanilla Newton's iteration of the form
\(_{t+1} = _t - \alpha _t _t^{-1}\nabla f_t,\) 
