arXiv cs.AI· Xinliang Zhang, Lesi Chen, Zonghan Li, Jingzhao Zhang·· 11 小时前AI 评分18
个体光滑性下的近最优二阶凸有限和优化
Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
AI 导读
针对光滑凸有限和优化，论文证明在个体光滑性与凸性假设下，二阶随机 oracle 复杂度下界为 Ω(n + n^{5/7} ε^{-2/7})，优于 Tsedenov & Kovalev（2026）在平均光滑性下的 minimax 最优复杂度。
正文 · 原文
Abstract:We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components. Very recently, Tsedenov \& Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is $\tilde{\Theta}(n + n^{6/7} \epsilon^{-2/7})$ by establishing nearly matching upper and lower bounds. In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is $\Omega(n+ n^{5/7} \epsilon^{-2/7})$ under this stronger assumption. Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of $\tilde{\mathcal{O}}(n + n^{5/7} \epsilon^{-2/7})$ by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.42040 [math.OC] |
| (or arXiv:2610.42040v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2610.42040 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Lesi Chen [view email]
[v1]
Fri, 30 Oct 2026 17:04:25 UTC (46 KB)
来源：arXiv cs.AI · arxiv.org