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

Xinliang Zhang; Lesi Chen; Zonghan Li; Jingzhao Zhang

math.OCOct 30, 2026

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

Authors: Xinliang Zhang, Lesi Chen, Zonghan Li, Jingzhao Zhang

Organizations: IIIS, Tsinghua University

Abstract

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.

Figures & tables

Oracle	Smoothness & Convexity	Upper Bound	Lower Bound
First-Order	Averaged	${\mathcal{O}}(n+n^{3/4}{\epsilon}^{-1/2})$ ( Allen-Zhu [7] )	$\Omega(n+n^{3/4}{\epsilon}^{-1/2})$ ( Zhou and Gu [56] )
First-Order	Individual	$\tilde{\mathcal{O}}(n+n^{1/2}{\epsilon}^{-1/2})$ ( Allen-Zhu [8] )	$\Omega(n+n^{1/2}{\epsilon}^{-1/2})$ ( Woodworth and Srebro [51] )
Second-Order	Averaged	$\tilde{\mathcal{O}}(n+n^{6/7}{\epsilon}^{-2/7})$ ( Tsedenov and Kovalev [49] )	$\Omega(n+n^{6/7}{\epsilon}^{-2/7})$ ( Tsedenov and Kovalev [49] )
Second-Order	Individual	$\tilde{\mathcal{O}}(n+n^{5/7}{\epsilon}^{-2/7})$ (This Paper)	$\Omega(n+n^{5/7}{\epsilon}^{-2/7})$ (This Paper)

Table 1: Comparison of first-order and second-order stochastic methods for solving Problem ( 1 ) under different smoothness assumptions. The averaged smooth lower bounds [ 56 , 49 ] also satisfy individual convexity.

Smooth Convex Optimization

See all 16 papers

Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
Aug 30, 2026Yuxing Peng, Zhiqing Tang, Weijia JiaOracle Complexity Nonconvex Optimization
Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, BNU-HKBU United International College, Zhuhai 519087, China
Near-Optimal Convex Optimization with Lazy Second-Order Oracles
Oct 2, 2026Xinliang Zhang, Lesi Chen, Chengchang Liu +1Second-Order Optimization
IIIS, Tsinghua University · Department of Artificial Intelligence, Westlake University.
Accelerated stochastic first-order method for convex optimization under heavy-tailed noise
Oct 13, 2025Chuan He, Bowen Li, Zhaosong LuStochastic Optimization Heavy-Tailed Noise
Department of Mathematics, Linköping University, Sweden · Department of Industrial and Systems Engineering, University of Minnesota, USA

Aug 30, 2026J/K move · Enter open · S save

Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

Yuxing Peng, Zhiqing Tang, Weijia Jia

Institute of Artificial Intelligence and Future Networks, Faculty of Arts and Sciences, Beijing Normal University, Zhuhai 519087, China · Guangdong Key Lab of AI and Multi-Modal Data Processing, BNU-HKBU United International College, Zhuhai 519087, China

Oracle Complexity Nonconvex Optimization Variance Reduction

Open paper AskPDF arXiv

Under individual smoothness, known algorithms for nonconvex finite-sum optimization use

O(n+\sqrt nΔL_{\max}/\varepsilon^2)

incremental first-order oracle (IFO) calls, while existing lower bounds miss the factor

\sqrt n

in the second term. We prove the matching lower bound

Ω(n+\sqrt nΔL_{\max}/\varepsilon^2)

for randomized IFO algorithms, allowing component indices and query points to depend on the complete preceding history. Thus PAGE and SPIDER are minimax optimal up to universal constants under individual and mean-squared smoothness. Under the global Polyak-Lojasiewicz (PL) condition, prior lower bounds did not capture the correct dependence on

n

under individual smoothness, and the regime of small

κ

remained open for randomized IFO algorithms. We prove an

Ω(n+κ_{\max}\sqrt n\log(Δ/\varepsilon))

lower bound for

κ_{\max}\ge\sqrt n

, and an

Ω(n+n\log(Δ/\varepsilon)/(1+\log(\sqrt n/κ_{\max})))

lower bound for

3\leκ_{\max}\le\sqrt n

. Restarted PAGE attains matching upper bounds under mean-squared smoothness in terms of

κ_{\rm ms}=L_{\rm ms}/μ

. Our lower bounds use dense weak hiding. Each hidden direction is spread across all components, making individual queries weakly informative while preserving the direction in the average. A sufficiently large dimension makes premature activation of future stages unlikely within the query budget. Balancing the cost of revealing a stage against the number of stages permitted by individual smoothness yields the missing

\sqrt n

factor.

Abstract

Smooth Convex Optimization

Explore similar work

Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness

Near-Optimal Convex Optimization with Lazy Second-Order Oracles

Accelerated stochastic first-order method for convex optimization under heavy-tailed noise