aiqbench analysis
This research advances the theoretical efficiency of convex optimization by establishing tight complexity bounds for algorithms utilizing lazy second-order oracles, which query Hessians less frequently than gradients. By matching a novel lower bound with an improved upper bound, the work provides fundamental insights into the computational limits of scalable machine learning training methods that rely on Hessian information.
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
arXiv:2610.03222v1 Announce Type: cross Abstract: 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+ m^{1/7} \epsilon^{-2/7})$ on the number of total iterations to find an $\epsilon$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} \epsilon^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} \epsilon^{-2/7})$ and is tight up to logarithmic factors.
Abstract: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+ m^{1/7} \epsilon^{-2/7})$ on the number of total iterations to find an $\epsilon$-solution using a novel block zero-chain construction. Then we propose a novel method that achieves a new upper bound of $\tilde{\mathcal{O}}(m+ m^{1/7} \epsilon^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} \epsilon^{-2/7})$ and is tight up to logarithmic factors.
Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2610.03222 [math.OC]
(or arXiv:2610.03222v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2610.03222 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 200 words
Related coverage
On the Condition Number Dependency in Bilevel Optimization
arXiv · Jun 10, 2026
Dual Certified White-Box Inference for Input Convex Neural Networks
arXiv · Oct 6, 2026
When Partial Credit Opposes Completion
Snorkel AI Blog · Oct 15, 2026
Learned Preconditioning for a Primal-Dual Interior-Point Method
arXiv · Sep 30, 2026