
The presence of the linear term with coefficient \(c_1>0\)  in the recursion means that, once we reach sufficiently close to the optimum, the algorithm can only achieve a linear convergence, as opposed to quadratic or superlinear convergence of deterministic methods. Prior works [1]}, [2]} discussed how to achieve local superlinear convergence by diminishing the coefficient \(c_1 = c_{1,t}\)  gradually as \(t\)  increases. However, since \(c_1\)  is proportional to the size of stochastic noise in the Hessian estimates, diminishing it requires increasing the sample size for estimating the Hessian, which results in a blow-up of the per-iteration computational cost. To be specific, \(c_1\)  is proportional to the reciprocal of the square root of the sample size; thus this blow-up in terms of the sample size can be as fast as exponential if we wish to attain the quadratic convergence rate, and linear if we wish to attain the superlinear convergence rate established in this paper later.

The presence of the failure probability \(\delta \)  in (REF ) means that after \(T\)  iterations, a convergence guarantee may only hold with probability \(1-T\delta \) . Thus, the failure probability explodes when \(T\rightarrow \infty \) . To resolve this approach one can gradually diminish the failure probability, i.e., \(\delta = \delta _t = O(1/t^2)\)  such that \(\sum _t \delta _t<\infty \) . However, once again, such adjustment on \(\delta \)  leads to an increasing sample/sketch size as iteration proceeds, although not as drastic as in (a) (it is sufficient to increase the sample size logarithmically). Thus, in our stochastic Hessian oracle model, where the noise level (and therefore, the sample size) remains constant, it is problematic to show any convergence with high probability from (REF ) as \(T\rightarrow \infty \) .

