In summary, none of the existing works can achieve superlinear convergence with fixed per-iteration computational cost. Additionally, high probability convergence guarantees generally fail as \(t\rightarrow \infty \) . (The potent exception of certain stochastic trust-region methods [1]} enjoy almost sure convergence, however, the per-iteration computation is not fixed and the local rate is unknown.) Furthermore, for finite-sum objectives, existing literature on stochastic Newton methods assumed each \(f_i\)  to be strongly convex [2]} or to be convex [3]}. However, \(f_i\)  need not be convex even if \(f\)  is strongly convex. See [4]}, [5]}, [6]}, [7]} and references therein for first-order algorithms designed under such a setting. We address the above limitations of stochastic Newton methods by reusing all the past samples to average Hessian estimates. Our scheme is especially preferable when we have limited budget for per-iteration computation (e.g., when we use very few samples in subsampled Newton, resulting in an ill-conditioned Hessian estimate). Our established non-asymptotic superlinear rates are stronger than the existing results, and our numerical experiments demonstrate the superiority of Hessian averaging.
