For subsampled Newton methods, aside from extensive empirical studies on different problems [1]}, [2]}, [3]}, [4]}, the pioneering work in [5]} established the very first asymptotic global convergence by showing that \(\Vert \nabla f_t\Vert \rightarrow 0\)  as \(t\rightarrow \infty \) , while the quantitative rate is unknown. Furthermore, [6]}, [7]} studied Newton-type algorithms with subsampled gradient and/or subsampled Hessian, and established global \(Q\) -linear convergence in function value \(f(_t)-f({^\star })\) . However, the above analyses neglected the underlying probabilistic nature of subsampled Hessian \({\hat{}}_t\) ; and required \({\hat{}}_t\)  to be lower bounded away from zero deterministically. Such a condition holds if each \(f_i\)  in (REF ) is strongly convex, which is restrictive in general. [8]} relaxed such condition by developing a novel algorithm, where the subsampled Hessian is adjusted by a truncated eigenvalue decomposition. With the exact gradient information and properly prespecified stepsizes, the authors showed a linear-quadratic error recursion for \(\Vert _t-{^\star }\Vert \)  in high probability. Arguably, the convergence of vanilla subsampled Newton method is originally analyzed in [9]} and [10]} from different perspectives. In particular, for both sampling and not sampling the gradient, [9]} showed a global \(Q\) -linear convergence for \(f(_t) - f({^\star })\)  and a local linear-quadratic convergence for \(\Vert _t-{^\star }\Vert \)  in high probability. Under some additional conditions, [10]} derived a global \(R\) -linear convergence for the expected function value \(\mathbb {E}[f(_t) - f({^\star })]\)  and a (similar) local linear-quadratic convergence for the expected iteration error \(\mathbb {E}[\Vert _t-{^\star }\Vert ]\) . For both works, the authors also discussed how to gradually increase the sample size for Hessian approximation to achieve a local \(Q\) -superlinear convergence. Building on these studies, various modifications of subsampled Newton methods have been reported with similar convergence guarantees. We refer to [13]}, [14]}, [15]}, [16]} and references therein.
