We present two new remarkably simple stochastic second-order methods for minimizing the average of a very large number of sufficiently smooth and strongly convex functions. The first is a stochastic variant of Newton's method (SN), and the second is a stochastic variant of cubically regularized Newton's method (SCN). We establish local linear-quadratic convergence results. Unlike existing stochastic variants of second order methods, which require the evaluation of a large number of gradients and/or Hessians in each iteration to guarantee convergence, our methods do not have this shortcoming. For instance, the simplest variants of our methods in each iteration need to compute the gradient and Hessian of a {\em single} randomly selected function only. In contrast to most existing stochastic Newton and quasi-Newton methods, our approach guarantees local convergence faster than with first-order oracle and adapts to the problem's curvature. Interestingly, our method is not unbiased, so our theory provides new intuition for designing new stochastic methods.

我们提出了两种非常简单的随机二阶方法，用于最小化大量充分光滑和强凸函数的平均值。第一种是牛顿方法的随机变体（SN），第二种是具有立方正则化的牛顿方法的随机变体（SCN）。与现有的随机二阶方法不同，我们的方法没有这种缺点，例如，我们的方法的最简单的变体每次迭代只需要计算一个随机选择函数的梯度和海森矩阵。与大多数现有的随机牛顿和拟牛顿方法相比，人们的方法保证了比一阶 oracle 更快的本地收敛，同时适应了问题的曲率。有趣的是，我们的方法不是无偏的，因此我们的理论为设计新的随机方法提供了新的直觉。

具有本地简单线性二次速度的随机牛顿和立方牛顿方法