# Near-Optimal Convex Optimization with Lazy Second-Order Oracles

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 25 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Builds on (most cited first, 16 of 16)

- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training](https://mlsanity.com/paper/2305.14342/) (2023)
- [A Kronecker-factored approximate Fisher matrix for convolution layers](https://mlsanity.com/paper/1602.01407/) (2016)
- [A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale](https://mlsanity.com/paper/2309.06497/) (2023)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [The Newton-Muon Optimizer](https://mlsanity.com/paper/2604.01472/) (2026)
- [Second-order optimization with lazy Hessians](https://mlsanity.com/paper/2212.00781/) (2022)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Balancing Gradient and Hessian Queries in Non-Convex Optimization](https://mlsanity.com/paper/2510.20786/) (2025)
- [Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexity](https://mlsanity.com/paper/2501.17488/) (2025)
- [Optimal Convex Optimization with Inexact Second-Order Oracles](https://mlsanity.com/paper/2607.24520/) (2026)
- [An Enhanced Levenberg--Marquardt Method via Gram Reduction](https://mlsanity.com/paper/2412.08561/) (2024)

## Abstract (arXiv)

This paper studies the complexity of convex optimization using lazy second-order oracles (Doikov, Chayti, and Jaggi, ICML 2023), where an algorithm queries gradients every iteration and Hessians once per m iterations. Under this setting, we show a lower bound of Omega(m+ m1/7 ε-2/7) on the number of total iterations to find an ε-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of tildeO(m+ m1/7 ε-2/7), which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of tildeO(m+ m13/21 ε-2/7) and is tight up to logarithmic factors.