Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity

摘要

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 𝒪( d̅ + d̅^1/2ϵ^-3/2) and 𝒪( 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 𝒪( d̅ + d̅^1/3ϵ^-3/2ln^18ϵ^-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 𝒪( d̅ + d̅^1/3ϵ^-3/2) and 𝒪( (d̅ + d̅^13/21ϵ^-2/7) lnd̅) for nonconvex and convex optimization, respectively, improving best-known results for both setups.