  We analyze Newton's method with lazy Hessian updates for solving general
possibly non-convex optimization problems. We propose to reuse a previously
seen Hessian for several iterations while computing new gradients at each step
of the method. This significantly reduces the overall arithmetical complexity
of second-order optimization schemes. By using the cubic regularization
technique, we establish fast global convergence of our method to a second-order
stationary point, while the Hessian does not need to be updated each iteration.
For convex problems, we justify global and local superlinear rates for lazy
Newton steps with quadratic regularization, which is easier to compute. The
optimal frequency for updating the Hessian is once every $d$ iterations, where
$d$ is the dimension of the problem. This provably improves the total
arithmetical complexity of second-order algorithms by a factor $\sqrt{d}$.
