  In this paper, we use Proximal Cubic regularized Newton Methods (PCNM) to
optimize the sum of a smooth convex function and a non-smooth convex function,
where we use inexact gradient and Hessian, and an inexact subsolver for the
cubic regularized second-order subproblem. We propose inexact variants of PCNM
and accelerated PCNM respectively, and show that both variants can achieve the
same convergence rate as in the exact case, provided that the errors in the
inexact gradient, Hessian and subsolver decrease at appropriate rates.
Meanwhile, in the online stochastic setting where data comes endlessly, we give
the overall complexity of the proposed algorithms and show that they are as
competitive as the stochastic gradient descent. Moreover, we give the overall
complexity of the proposed algorithms in the finite-sum setting and show that
it is as competitive as the state of the art variance reduced algorithms.
Finally, we propose an efficient algorithm for the cubic regularized
second-order subproblem, which can converge to an enough small neighborhood of
the optimal solution in a superlinear rate.
