Optimal Convex Optimization with Inexact Second-Order Oracles

In this paper, we present a novel second-order method called Accelerated Inexact Newton Extragradient (AINE) for convex optimization using $\delta$-inexact Hessians. We show that AINE can find an $ϵ$-solution in the inexact second-order oracle (ISO) complexity of $\mathcal{O}((\delta /ϵ{)}^{1/2}+(L_2/ϵ{)}^{2/7})$ when the Hessian is $L_2$-Lipschitz continuous, and a better complexity of $\tilde{\mathcal{O}}((\delta /ϵ{)}^{1/2}+(L_3/ϵ{)}^{1/5})$ when the third-order derivative is $L_3$-Lipschitz continuous. Notably, each iteration of our method can be conducted in the same running time as matrix multiplication up to logarithmic factors. In addition, we also establish complexity lower bounds to demonstrate that our methods are (nearly) optimal.