mlsanityData to 14 Oct 2026

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

arXiv 2610.03222 ↗First posted 2 Oct 2026math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

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.

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

16 of 25 references.

References · 16

  1. 2015Optimizing Neural Networks with Kronecker-factored Approximate Curvaturecited by 796
  2. 2018Shampoo: Preconditioned Stochastic Tensor Optimizationcited by 426
  3. 2023Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-trainingcited by 265
  4. 2016A Kronecker-factored approximate Fisher matrix for convolution layerscited by 141
  5. 2023A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scalecited by 77
  6. 2017Oracle Complexity of Second-Order Methods for Smooth Convex Optimizationcited by 24
  7. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 24
  8. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 20
  9. 2026The Newton-Muon Optimizercited by 18
  10. 2022Second-order optimization with lazy Hessianscited by 15
  11. 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 12
  12. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 5
4 more
  1. 2025Balancing Gradient and Hessian Queries in Non-Convex Optimizationcited by 3
  2. 2025Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexitycited by 2
  3. 2026Optimal Convex Optimization with Inexact Second-Order Oraclescited by 2
  4. 2024An Enhanced Levenberg--Marquardt Method via Gram Reductioncited by 1

Built on by

Not cited yet.