arXiv cs.AI· Xinliang Zhang, Lesi Chen, Zonghan Li, Jingzhao Zhang·· 10 小时前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 最优复杂度。
正文 · AI 翻译
摘要：我们研究求解具有 $n$ 个分量的光滑凸有限和优化的随机二阶 oracle 复杂度。最近，Tsedenov \& Kovalev (2026) 通过建立几乎匹配的上下界，证明了在平均光滑性和凸性下的极小极大最优复杂度为 $\tilde{\Theta}(n + n^{6/7} \epsilon^{-2/7})$。在本文中，我们证明个体光滑性和凸性可证明地带来进一步加速，其中在该更强假设下的复杂度下界为 $\Omega(n+ n^{5/7} \epsilon^{-2/7})$。然后，通过建立一种新颖的二阶自界定不等式，我们设计了一种新的泰勒校正惰性牛顿法，通过应用最优的 Monteiro-Svaiter 加速，可得到 $\tilde{\mathcal{O}}(n + n^{5/7} \epsilon^{-2/7})$ 的更优复杂度，与我们的下界仅相差对数因子。
| 学科： | 优化与控制 (math.OC)；人工智能 (cs.AI)；机器学习 (stat.ML) |
| 引用为： | arXiv:2610.42040 [math.OC] |
| （或 arXiv:2610.42040v1 [math.OC] 为此版本） | |
| https://doi.org/10.48550/arXiv.2610.42040 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Lesi Chen [查看电子邮件]
[v1]
2026年10月30日星期五 17:04:25 UTC（46 KB）
来源：arXiv cs.AI · arxiv.org