{"id":"arxiv/2610.10495","url":"https://arxiv.org/abs/2610.10495","tags":["math.OC"],"score":0,"title":"An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity","domain":"math.OC","source":"arxiv","authors":["Artem Tsedenov","Dmitry Kovalev"],"reviews":0,"subject":"math.OC","summary":"In this paper, we consider a finite-sum optimization problem, where the objective function is convex, the $n$ component functions are twice continuously differentiable and their Hessians are mean-square Lipschitz. Our contribution is twofold. First, we develop a stochastic algorithm, which requires $\\tilde{\\mathcal{O}}(n + n^{6/7}/ε^{2/7})$ second-order oracle calls in expectation to find an approximate solution to the problem with the expected accuracy $ε$. Second, we establish a lower complexity bound of $Ω(n + n^{6/7}/ε^{2/7})$ for any stochastic second-order algorithm satisfying a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}