When \(_t\notin {\mathcal {N}}_\nu \) , the iteration is in the damped Newton phase, where the objective \(f(_t)\)  is decreased by at least a fixed amount in each iteration, and converges linearly. In this phase, \(\Vert _t-{^\star }\Vert \)  may converge slowly (e.g., it provably converges \(R\) -linearly using the fact that \(\Vert _t-{^\star }\Vert ^2\le 2/\lambda _{\min }(f(_t)-f({^\star }))\) ). When \(_t\in {\mathcal {N}}_\nu \) , the iteration transits to the quadratically convergent phase, where the unit stepsize is accepted and \(\Vert _t-^\star \Vert \)  converges quadratically. See [1]} for the analysis. Compared to first-order methods, although second-order methods often enjoy a faster convergence rate and behave more robustly to tuning parameters, they hinge on a high computational cost of forming the exact Hessian matrix \(_t\)  at each iteration. To resolve such a computational bottleneck, which is particularly pressing in large-scale data applications, a variety of deterministic and stochastic methods have been proposed for constructing different approximations of the Hessian.
