Preprint
Jul 2026
Optimal Convex Optimization with Inexact Second-Order Oracles
This paper shows that AINE can find an $\epsilon$-solution in the inexact second-order oracle (ISO) complexity of $\delta/\epsilon)^{1/2} + (L_2/\epsilon)^{2/7} )$ when the Hessian is $L_2$-Lipschitz continuous, and establishes matching oracle complexity lower bounds for both setups.
Lesi Chen, Chengchang Liu, Luo Luo et al.
· 1 citation