OpenAlex ·

An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity

Artem Tsedenov and Dmitry A. Kovalev

Published
Source
OpenAlex
Published in
arXiv (Cornell University)
DOI
10.48550/arxiv.2610.10495
Original
Read it at the publisher
Topics
Artificial IntelligenceSystems & ControlNumerical Analysis

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 $\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 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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

Read it on ReadSearch

Each opens after you create an account, and brings you back to this paper.

Already a reader? Sign in

All new papers in Artificial Intelligence

Get the few papers worth your time in Artificial Intelligence every morning.

ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.

Papers belong to their authors and publishers; every page here links to the original. All research topics