Higher-Order Finite-Sum Bounds Close the Square-Root-n Gap
Verified recursive estimation and dense weak hiding yield matching higher-order oracle bounds with an $n^{1-1/(2p)}$ finite-sum term.
Underlying Paper
Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
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, $\Delta>0$ the initial objective-gap bound, $L_p>0$ an individual $p$-th derivative Lipschitz bound, and $\epsilon>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 \[ \Theta_p\!\left( n+\Delta L_p^{1/p}n^{1-1/(2p)} \epsilon^{-(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.
Finding an approximately stationary point is a core task in smooth nonconvex optimization, but finite sums constrain an algorithm to learn through individual component functions. For higher-order methods, the general upper and lower bounds had differed by a factor of in their dependence on the number of components. This paper closes that gap for every fixed derivative order , using an exact component oracle that returns function values and derivatives through order .
Core Contribution
The authors characterize the randomized minimax oracle complexity of finding a point with gradient norm at most for a nonconvex finite sum. With initial objective gap bounded by and individual -th derivative Lipschitz constant , the complexity is
The result retains the additive term, applies across positive parameter regimes and arbitrary finite dimensions, and counts component oracle calls while allowing unrestricted internal computation. The minimax guarantee succeeds with probability at least .
The paper supplies matching upper- and lower-bound arguments. Its upper bound retains the known finite-sum exponent while avoiding a fixed-confidence logarithmic loss. Its lower bound applies to unrestricted randomized adaptive algorithms, closing the prior square-root- separation.
Technical Approach
For the upper bound, the method uses recursive estimation together with higher-order information. The analysis requires mean-squared increments of the -th derivative rather than a stronger pointwise condition of the same form for every component.
A verified-epoch mechanism is central to the fixed-confidence analysis. The procedure checks complete recursive-estimation epochs with exact function values, preventing inaccurate stochastic estimates from being accepted without verification. This lets the upper-bound construction avoid the fixed-confidence logarithmic loss while preserving the finite-sum complexity scaling.
For the lower bound, the authors extend dense weak hiding to answer complete higher-order oracle queries through order . The construction keeps each component's regularity independent of the hard chain length, making the lower-bound instance compatible with the higher-order oracle model. The resulting argument applies against randomized, adaptive algorithms.
Results and Analysis
This is a theoretical result rather than an empirical benchmark study: its evidence is the pair of matching oracle-complexity proofs. The central quantitative conclusion is the matching rate, replacing the previously known separation in the general-order dependence on the number of components.
The additive term is part of the characterization rather than a lower-order detail. It captures the cost of component-level access and can matter when the target accuracy is moderate or the finite sum is large. The result should nevertheless be read as an oracle-complexity characterization, not as a direct runtime guarantee for large-scale learning: it assumes exact high-order component information and permits unrestricted internal computation.
Evidence Box
theoreticalKey Claims
- •Tight randomized higher-order oracle complexity for nonconvex finite sums
- •Dense weak hiding supports complete derivative replies through order p
- •Verified recursive estimation removes the fixed-confidence logarithmic loss
Key Results
- •Θp(n + ΔLₚ^(1/p)n^(1−1/(2p))ε^(-(p+1)/p)) component queries for every fixed p ≥ 2
- •Success probability at least 2/3 in the minimax characterization
- •The matching result closes the prior square-root-n gap in general-order bounds
- •The characterization includes the additive n term in every positive parameter regime
Limitations & Caveats
- •Exact component oracle must return function values and all derivatives through order p
- •Complexity counts queries while permitting unrestricted internal computation
- •Constants depend on the fixed derivative order p
- •No empirical runtime evaluation on finite-sum learning problems
