Second-Order Methods with Cubic Regularization Under Inexact Information

Understand

In this paper, we generalize (accelerated) Newton's method with cubic regularization under inexact second-order information for (strongly) convex optimization problems.

• Under mild assumptions, we provide global rate of convergence of these methods and show the explicit dependence of the rate of convergence on the problem parameters.
• While the complexity bounds of our presented algorithms are theoretically worse than those of their exact counterparts, they are at least as good as those of the optimal first-order methods.
• Our numerical experiments also show that using inexact Hessians can significantly speed up the algorithms in practice.