Near-Optimal Convex Optimization with Lazy Second-Order Oracles

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.

Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
Xinliang Zhang, Lesi Chen, Zonghan Li +1
arXiv30 Oct 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L₀,L₁)-Smoothness
Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov +1
arXiv15 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Optimal Stochastic Bilevel Optimization with First-Order Oracles
Linxuan Pan, Junchi Yang
arXiv1 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Distributed Convex Second-Order Optimization for AC/DC Hybrid Distribution Systems within PROcess Orchestration Framework
Xinliang Dai, Yuning Jiang, Junyi Zhai +5
arXiv12 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Near-Optimal Acceleration for Smooth ℓ_p / ℓ_q Nondual Convex First-Order Oracle Optimization
David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1
arXiv18 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhang2026nearoptimal,
  title = {{Near-Optimal Convex Optimization with Lazy Second-Order Oracles}},
  author = {Xinliang Zhang and Lesi Chen and Chengchang Liu and Jingzhao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.03222},
  eprint = {2610.03222},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03222},
  note = {CC0},
}

RIS

TY  - UNPB
TI  - Near-Optimal Convex Optimization with Lazy Second-Order Oracles
AU  - Xinliang Zhang
AU  - Lesi Chen
AU  - Chengchang Liu
AU  - Jingzhao Zhang
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.03222
UR  - https://arxiv.org/abs/2610.03222
AB  - 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.
ER  -

Abstract

Related

Cite