  In this paper, we propose a new randomized second-order optimization
algorithm---Stochastic Subspace Cubic Newton (SSCN)---for minimizing a high
dimensional convex function $f$. Our method can be seen both as a {\em
stochastic} extension of the cubically-regularized Newton method of Nesterov
and Polyak (2006), and a {\em second-order} enhancement of stochastic subspace
descent of Kozak et al. (2019). We prove that as we vary the minibatch size,
the global convergence rate of SSCN interpolates between the rate of stochastic
coordinate descent (CD) and the rate of cubic regularized Newton, thus giving
new insights into the connection between first and second-order methods.
Remarkably, the local convergence rate of SSCN matches the rate of stochastic
subspace descent applied to the problem of minimizing the quadratic function
$\frac12 (x-x^*)^\top \nabla^2f(x^*)(x-x^*)$, where $x^*$ is the minimizer of
$f$, and hence depends on the properties of $f$ at the optimum only. Our
numerical experiments show that SSCN outperforms non-accelerated first-order CD
algorithms while being competitive to their accelerated variants.
