  While there already exist randomized subspace Newton methods that restrict
the search direction to a random subspace for a convex function, we propose a
randomized subspace regularized Newton method for a non-convex function {and
more generally we investigate thoroughly the local convergence rate of the
randomized subspace Newton method}.
  In our proposed algorithm using a modified Hessian of the function restricted
to some random subspace, with high probability, the function value decreases
even when the objective function is non-convex.
  In this paper, we show that our method has global convergence under
appropriate assumptions and its convergence rate is the same as that of the
full regularized Newton method. %We also prove that Furthermore, we can obtain
a local linear convergence rate under some additional assumptions, and prove
that this rate is the best we can hope, in general, when using random subspace.
We furthermore prove that if the Hessian at the local optimum is rank
defficient then superlienar convergence holds.
