---
title: "Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2610.42040v1"
permalink: "https://feed.astralor.com/items/itm_f5f5501ca6063e3c97cb79b6"
published: "2026-10-30T17:04:25.000Z"
score: 52
channel: "ai"
tags: ["RAG","Near-Optimal Second-Order Convex","Finite-Sum Optimization","Individual Smoothness","Very","Tsedenov","Kovalev"]
---

# Near-Optimal Second-Order Convex Finite-Sum Optimization under Individual Smoothness

## 速览

We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components. Very recently, Tsedenov \& Kovalev (2026) showed that the minimax optimal complexity under ave…

## 关键点

- We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components.
- Very recently, Tsedenov \& Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is $\tildeΘ(n + n^{6/7} ε^{-2/7})$ by establishing nearly matching upper and lower bounds.
- 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.

## 全文

We study the stochastic second-order oracle complexity of solving smooth convex finite-sum optimization with $n$ components. Very recently, Tsedenov \& Kovalev (2026) showed that the minimax optimal complexity under averaged smoothness and convexity is $\tildeΘ(n + n^{6/7} ε^{-2/7})$ by establishing nearly matching upper and lower bounds. 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})$ by applying the optimal Monteiro-Svaiter acceleration, matching our lower bound up to only logarithmic factors.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_f5f5501ca6063e3c97cb79b6