{"id":"arxiv/2607.24520","url":"https://arxiv.org/abs/2607.24520","tags":["math.OC"],"score":0,"title":"Optimal Convex Optimization with Inexact Second-Order Oracles","domain":"math.OC","source":"arxiv","authors":["Lesi Chen","Chengchang Liu","Luo Luo","John C. S. Lui","Jingzhao Zhang"],"reviews":0,"subject":"math.OC","summary":"In this paper, we present a novel second-order method called Accelerated Inexact Newton Extragradient (AINE) for convex optimization using $δ$-inexact Hessians. We show that AINE can find an $ε$-solution in the inexact second-order oracle (ISO) complexity of $\\mathcal{O}( (δ/ε)^{1/2} + (L_2/ε)^{2/7} )$ when the Hessian is $L_2$-Lipschitz continuous, and a better complexity of $\\mathcal{O}( (δ/ε)^{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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}