Second, the parameter \(\Upsilon \)  characterizes the noise level of stochastic Hessian oracle. When the Hessian is generated by subsampling or sketching, \(\Upsilon \)  depends on the adopted sample/sketch sizes. As illustrated in Examples  and , \(\Upsilon =O(\kappa )\)  for popular Hessian estimators when sample/sketch sizes are independent of \(\kappa \) . In this case, \({\mathcal {T}}= O(\kappa ^2)\) . We require \({\mathcal {T}}\ge O(\Upsilon ^2)\)  only to ensure that \(\lbrace {\tilde{}}_t\rbrace _{t\ge {\mathcal {T}}}\)  are positive definite with condition numbers scaling as \(\kappa \) , so that the Newton step based on \({\tilde{}}_t\)  leads to a usual decrease of the objective.
On the other hand, popular stochastic Newton methods often generate a larger sample size (which depends on \(\kappa \) ) to enforce \(\Vert _t\Vert \le \epsilon \lambda _{\min }\)  for any \(t\ge 0\)  with an \(\epsilon \in (0,1)\)  [1]}, [2]}. In that case, \(\lbrace {\hat{}}_t\rbrace _{t\ge 0}\)  are positive definite and so are \(\lbrace {\tilde{}}_t\rbrace _{t\ge 0}\) . Importantly, our method does not require such well-conditioned Hessian oracles.
