OpenAlex ·
An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.10495
- Original
- Read it at the publisher
- Topics
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.
More in Artificial Intelligence
Particle-Number-Preserving Quantum Signal Processing for Thermal Properties: Canonical-Ensemble Estimation and Grand-Canonical Reconstruction
A structure-preserving neural density functional for the ions of a polymer electrolyte
An extended deep energy method for thermo-mechanical crack propagation
asdex: Automatic Sparse Differentiation in JAX
Physics-Informed Neural Plasticity: PDE Solvers That Reshape Themselves
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.