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 $\tilde{\mathcal{O}}(m+ m^{1/7} ε^{-2/7})$, which significantly improves the prior one (Chen, Liu, Luo, and Zhang, COLT 2026) of $\tilde{\mathcal{O}}(m+ m^{13/21} ε^{-2/7})$ and is tight up to logarithmic factors.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Zhang, X., Chen, L., Liu, C., & Zhang, J. (2026). Near-Optimal Convex Optimization with Lazy Second-Order Oracles. https://omanscience.com/en/articles/near-optimal-convex-optimization-with-lazy-second-order-oracles
MLA 9
Zhang, Xinliang, et al. "Near-Optimal Convex Optimization with Lazy Second-Order Oracles." https://omanscience.com/en/articles/near-optimal-convex-optimization-with-lazy-second-order-oracles.
Chicago (author–date)
Zhang, Xinliang, Lesi Chen, Chengchang Liu, and Jingzhao Zhang. 2026. "Near-Optimal Convex Optimization with Lazy Second-Order Oracles." https://omanscience.com/en/articles/near-optimal-convex-optimization-with-lazy-second-order-oracles.
Harvard
Zhang, X., Chen, L., Liu, C. and Zhang, J. (2026) 'Near-Optimal Convex Optimization with Lazy Second-Order Oracles', Available at: https://omanscience.com/en/articles/near-optimal-convex-optimization-with-lazy-second-order-oracles.
Vancouver
Zhang X, Chen L, Liu C, Zhang J. Near-Optimal Convex Optimization with Lazy Second-Order Oracles. https://omanscience.com/en/articles/near-optimal-convex-optimization-with-lazy-second-order-oracles
IEEE
X. Zhang, L. Chen, C. Liu, and J. Zhang, "Near-Optimal Convex Optimization with Lazy Second-Order Oracles," https://omanscience.com/en/articles/near-optimal-convex-optimization-with-lazy-second-order-oracles.