An Optimal Second-Order Algorithm for Finite-Sum Optimization under Average Smoothness and Convexity
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.10495
curl -X POST /api/v1/records/arxiv/2610.10495/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.10495/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'