# Optimal Convex Optimization with Inexact Second-Order Oracles

arXiv: https://arxiv.org/abs/2607.24520 · HTML: https://mlsanity.com/paper/2607.24520/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2026.

## Built on by (most cited first, 2 of 2)

- [Primal Acceleration of Newton's Method](https://mlsanity.com/paper/2608.21359/) (2026)
- [Near-Optimal Convex Optimization with Lazy Second-Order Oracles](https://mlsanity.com/paper/2610.03222/) (2026)

## Abstract (arXiv)

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 O( (δ/ε)1/2 + (L2/ε)2/7 ) when the Hessian is L2-Lipschitz continuous, and a better complexity of O( (δ/ε)1/2 + (L3/ε)1/5 ) when the third-order derivative is L3-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 matching oracle complexity lower bounds for both setups, demonstrating the optimality of our methods.