An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
Abstract
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 𝒪̃(n + n6/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 + n6/7/ε2/7) for any stochastic second-order algorithm satisfying a stochastic second-order version of the first-order linear span assumption, which is widely adopted in the optimization literature. Our lower and upper complexity bounds match up to logarithmic factors and thus resolve an important open question of establishing the optimal complexity of this problem class.
Related
- Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
- An Adaptive Projected-Gradient Algorithm for Sample-Average Approximations of Stochastic Multi-Objective Optimization
- Improved Guarantees for Langevin Monte Carlo with Average Smoothness
- Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity
- The Tamed Subgradient Unadjusted Langevin Algorithm beyond Convexity
BibTeX
@misc{tsedenov2026optimal,
title = {{An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity}},
author = {Artem Tsedenov and Dmitry Kovalev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10495},
eprint = {2610.10495},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10495},
}
RIS
TY - UNPB
TI - An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
AU - Artem Tsedenov
AU - Dmitry Kovalev
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10495
UR - https://arxiv.org/abs/2610.10495
AB - 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 𝒪̃(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 stochastic second-order version of the first-order linear span assumption, which is widely adopted in the optimization literature. Our lower and upper complexity bounds match up to logarithmic factors and thus resolve an important open question of establishing the optimal complexity of this problem class.
ER -