# Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity

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

## Key facts

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

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

- [Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity](https://mlsanity.com/paper/2506.08362/) (2025)
- [Near-Optimal Convex Optimization with Lazy Second-Order Oracles](https://mlsanity.com/paper/2610.03222/) (2026)

## Abstract (arXiv)

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( bar d + bar d1/2 ε-3/2) and O( bar d + bar d1/2 ε-1/2) for nonconvex and convex optimization, respectively, where bar 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( bar d + bar d1/3 ε-3/2 ln18 ε-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( bar d + bar d1/3 ε-3/2) and O( (bar d + bar d13/21 ε-2/7) ln bar d) for nonconvex and convex optimization, respectively, improving best-known results for both setups.