OpenAlex ·
Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.28202
- Original
- Read it at the publisher
- Topics
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, $L_p>0$ an individual $p$-th derivative Lipschitz bound, and $ε>0$ the target gradient norm. For every fixed integer $p\ge 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\!\left( n+ΔL_p^{1/p}n^{1-1/(2p)} ε^{-(p+1)/p} \right), \] 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 $\sqrt{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Claim-Gated Source-Risk Auditing for Generative Search
Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs
A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth
Biplanar graphs with independence number two are 9-colorable
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.