Near-Optimal Convex Optimization with Lazy Second-Order Oracles
math.OC, cs.LG, stat.ML
Submitted: 2026-10-02
Updated: 2026-10-02
License: http://creativecommons.org/publicdomain/zero/1.0/
The gist: 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
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 Ω(m+ m 1/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 (m+ m 1/7 ε-2/7), which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of (m+ m 13/21 ε-2/7) and is tight up to logarithmic factors.
Sources
- Scalable Second Order Optimization for Deep Learning
- Optimal Convex Optimization with Inexact Second-Order Oracles
- The Newton-Muon Optimizer
- A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale
Related papers
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Adam-HNAG: A Convergent Reformulation of Adam with Accelerated Rate
- Incremental Learning in Mirror Flows
- Second-Order Optimization with Asynchronous Curvature
- Online Control via Counterfactual Tracking
- Asynchronous Replanning in Two Population Linear Quadratic Mean Field Games: Information Requirements and Stability