Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
arXiv cs.AI · 31 Oct 2026, 03:04 AEST
The paper discusses advancements in stochastic second-order oracle complexity for smooth convex finite-sum optimization. It presents a new method that achieves better complexity under individual smoothness and convexity assumptions.
Key facts
- We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components.
- In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is $Ω(n+ n^{5/7} ε^{-2/7})$ under this stronger assumption.
- Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of $\tilde{\mathcal{O}}(n + n^{5/7} ε^{-2/7})$.
Read aloud
The paper discusses advancements in stochastic second-order oracle complexity for smooth convex finite-sum optimization. It presents a new method that achieves better complexity under individual smoothness and convexity assumptions. We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components. In this paper, we show that individual smoothness and convexity provably enable further acceleration, where the lower complexity bound is $Ω n+ n^ five/seven ε^ -two/seven $ under this stronger assumption. Then, by establishing a novel second-order self-bounding inequality, we design a new Taylor-corrected lazy Newton method, which can lead to a better complexity of $\tilde \mathcal O n + n^ five/seven ε^ -two/seven $.
Sources in this cluster
- Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness
arXiv cs.AI · 31 Oct 2026, 03:04 AEST