Optimal Convex Optimization with Inexact Second-Order Oracles

2026/07/28 by Lesi Chen, Chengchang Liu, Luo Luo +2
#math.OC

paper · pdf

Abstract

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 + (L₂/ε)^2/7 ) when the Hessian is L₂-Lipschitz continuous, and a better complexity of O( (δ/ε)^1/2 + (L₃/ε)^1/5 ) when the third-order derivative is L₃-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.

Citations

• Balancing Gradient and Hessian Queries in Non-Convex Optimization
• The Potential of Second-Order Optimization for LLMs: A Study with Full Gauss-Newton
• Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
• Convex optimization with p-norm oracles
• Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations
• More Asymmetry Yields Faster Matrix Multiplication
• Krylov Cubic Regularized Newton: A Subspace Second-Order Method with Dimension-Free Convergence Rate
• Advancing the lower bounds: An accelerated, stochastic, second-order method with optimal adaptation to inexactness
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization
• Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training
• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
• Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence
• Second-order optimization with lazy Hessians
• Extra-Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods
• Faster Matrix Multiplication via Asymmetric Hashing
• Optimal and Adaptive Monteiro-Svaiter Acceleration
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization
• On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization
• Inexact Tensor Methods and Their Application to Stochastic Convex Optimization
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
• Stochastic Subspace Cubic Newton Method
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Near-optimal method for highly smooth convex optimization
• An Optimal High-Order Tensor Method for Convex Optimization
• Shampoo: Preconditioned Stochastic Tensor Optimization
• Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimization
• Stochastic Cubic Regularization for Fast Nonconvex Optimization
• Second-Order Methods with Cubic Regularization Under Inexact Information
• Oracle Complexity of Second-Order Methods for Smooth Convex Optimization
• Relatively-Smooth Convex Optimization by First-Order Methods, and Applications
• A Kronecker-factored approximate Fisher matrix for convolution layers

Related

• Inexact and Implementable Accelerated Newton Proximal Extragradient Method for Convex Optimization
• Solving Convex-Concave Problems with O(ε^-4/7) Second-Order Oracle Complexity
• Oracle Complexity of Second-Order Methods for Smooth Convex Optimization
• Second-order optimization with lazy Hessians
• Exploiting higher-order derivatives in convex optimization methods