Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity

2025/01/29 by Lesi Chen, Chengchang Liu, Chen, Lesi +5 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Mathematics #Matrix Theory and Algorithms #Model Reduction and Neural Networks #Numerical Methods and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2501.17488

openalex publication_date 2025/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Second-order optimization methods are computationally expensive for large-scale problems. Recently, Doikov, Chayti, and Jaggi (ICML 2023) proposed the LazyCRN method that reduces computation by studying the gradient complexity of second-order methods. Their method can achieve a gradient complexity of O( d + d^1/2 ε^-3/2) and O( d + d^1/2 ε^-1/2) for nonconvex and convex optimization, respectively, where d is the effective dimension and ε is the target precision. Very recently, Adil, Bullins, Sidford, and Zhang (NeurIPS 2025) improved the gradient complexity to O( d + d^1/3 ε^-3/2 ln¹⁸ ε^-1) for nonconvex optimization. However, the tightness of these methods remains open. In this work, we propose new methods that achieve an improved complexity of O( d + d^1/3 ε^-3/2) and O( ( d + d^13/21 ε^-2/7) ln d) for nonconvex and convex optimization, respectively, improving best-known results for both setups.

Cited by

• Solving Convex-Concave Problems with O(ε^-4/7) Second-Order Oracle Complexity

Related

• Second-order optimization with lazy Hessians
• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence
• Inexact and Implementable Accelerated Newton Proximal Extragradient Method for Convex Optimization
• Multilevel Regularized Newton Methods with Fast Convergence Rates
• Faithful-Newton Framework: Bridging Inner and Outer Solvers for Enhanced Optimization