Volume: 90 • Number: 2 • Pages: 607-630

In this paper, we present a version of the Cubic Regularization of Newton method for unconstrained nonconvex optimization, in which the Hessian matrices are approximated by forward gradient differences. The regularization parameter of the cubic models and the accuracy of the Hessian approximations are jointly adjusted using a nonmonotone line-search criterion. Assuming that the Hessian of the objective function is Lipschitz continuous, we show that the proposed method needs at most $\mathcal{O}\left(n\epsilon^{-3/2}\right)$ calls of the oracle to generate an $\epsilon$-approximate stationary point, where $n$ is the dimension of the domain of the objective function.