Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness

@misc{zhang2026nearoptimal,
  title = {{Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness}},
  author = {Xinliang Zhang and Lesi Chen and Zonghan Li and Jingzhao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.42040},
  eprint = {2610.42040},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.42040},
}

TY  - UNPB
TI  - Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
AU  - Xinliang Zhang
AU  - Lesi Chen
AU  - Zonghan Li
AU  - Jingzhao Zhang
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.42040
UR  - https://arxiv.org/abs/2610.42040
AB  - 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 Θ̃(n + n^6/7 ε^−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 Ω(n+ n^5/7 ε^−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 𝒪̃(n + n^5/7 ε^−2/7) by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.
ER  -