arXiv：cs.LG· Xinliang Zhang, Lesi Chen, Chengchang Liu, Jingzhao Zhang·· 4 小时前AI 评分37
惰性二阶预言机下的近最优凸优化：新下界与紧致上界
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
AI 导读
针对惰性二阶预言机（每轮查询梯度、每 m 轮查询一次 Hessian）的凸优化问题，研究者通过新的块零链构造证明了 Ω(m + m^{1/7} ε^{-2/7}) 的迭代下界，并提出达到 Õ(m + m^{1/7} ε^{-2/7}) 上界的新方法。该结果显著优于此前 Chen 等人（COLT 2026）的 Õ(m + m^{13/21} ε^{-2/7})，且在对数因子内紧致。
正文
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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.03222 [math.OC] |
| (or arXiv:2610.03222v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.03222 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Lesi Chen [view email]
[v1]
Fri, 2 Oct 2026 12:38:28 UTC (50 KB)
来源：arXiv：cs.LG · arxiv.org