Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
Abstract
We establish tight randomized higher-order oracle complexity for finding first-order stationary points of nonconvex finite sums. Let n be the number of components, Δ>0 the initial objective-gap bound, Lp>0 an individual p-th derivative Lipschitz bound, and ε>0 the target gradient norm. For every fixed integer p≥ 2, the minimax number of exact component queries returning the value and all derivatives through order p, with success probability at least 2/3, is Θp ( n+ΔLp1/pn1−1/(2p) ε−(p+1)/p ), where the constants depend only on p and the worst case ranges over all finite dimensions. The lower bound holds for unrestricted randomized adaptive algorithms and closes the √n gap between the previously known general-order upper and lower bounds in their dependence on n. We extend dense weak hiding to complete higher-order replies while keeping each component's regularity independent of the chain length. The matching upper bound retains the known finite-sum exponent, requires only mean-squared p-th derivative increments, and removes the fixed-confidence logarithmic loss by verifying entire recursive-estimation epochs with exact function values. The characterization includes the additive n term for every positive parameter regime; it counts oracle calls with unrestricted internal computation.
Related
- Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Randomized Bounds for Finite-Sum Nonconvex-Concave Optimization
- Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
- Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
BibTeX
@misc{wu2026matching,
title = {{Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization}},
author = {Wendao Wu and Haihan Zhang and Chenheng Zhang and Yanyi Li and Chunyuan Zheng and Cong Fang and Haoxuan Li and Zhouchen Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28202},
eprint = {2609.28202},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28202},
}
RIS
TY - UNPB
TI - Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
AU - Wendao Wu
AU - Haihan Zhang
AU - Chenheng Zhang
AU - Yanyi Li
AU - Chunyuan Zheng
AU - Cong Fang
AU - Haoxuan Li
AU - Zhouchen Lin
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2609.28202
UR - https://arxiv.org/abs/2609.28202
AB - We establish tight randomized higher-order oracle complexity for finding first-order stationary points of nonconvex finite sums. Let n be the number of components, Δ>0 the initial objective-gap bound, L_p>0 an individual p-th derivative Lipschitz bound, and ε>0 the target gradient norm. For every fixed integer p≥ 2, the minimax number of exact component queries returning the value and all derivatives through order p, with success probability at least 2/3, is Θ_p ( n+ΔL_p^1/pn^1−1/(2p) ε^−(p+1)/p ), where the constants depend only on p and the worst case ranges over all finite dimensions. The lower bound holds for unrestricted randomized adaptive algorithms and closes the √n gap between the previously known general-order upper and lower bounds in their dependence on n. We extend dense weak hiding to complete higher-order replies while keeping each component's regularity independent of the chain length. The matching upper bound retains the known finite-sum exponent, requires only mean-squared p-th derivative increments, and removes the fixed-confidence logarithmic loss by verifying entire recursive-estimation epochs with exact function values. The characterization includes the additive n term for every positive parameter regime; it counts oracle calls with unrestricted internal computation.
ER -