Sample Reuse Does Not Beat Second-Order Query Limits
A curvature-first algorithm and reuse-aware lower bounds match total derivative complexity at near ε⁻³ + γ⁻³ scaling.
Underlying Paper
Matching Complexity for Second-Order Stationary Point with Sample Reuse
We consider stochastic nonconvex optimization with sample-wise Lipschitz gradients and Hessians, and reusable opaque sample handles. Gradient and complete-Hessian evaluations are charged separately, including both endpoints of a same-sample difference. For fixed positive problem parameters and in the high-dimensional worst case, we prove that the minimax total derivative-query complexity of finding an $(\varepsilon,\gamma)$-second-order stationary point is \begin{equation*} \widetilde\Theta(\varepsilon^{-3}+\gamma^{-3}). \end{equation*} The upper bound combines curvature-first randomly signed negative-curvature steps with binary-ancestor derivative estimators; a truncated increment estimate charges predictable drift linearly and martingale motion quadratically. The curvature lower bound uses a deterministic smooth bounded-gradient chain, a radial barrier, and a random rotation. The new first-order lower bound is specifically robust to persistent sample reuse and to complete-Hessian access. It uses a slowly parameterized conservative sign chain, a third-order reverse stick-breaking localization inequality, and stateful relative-entropy accounting for reusable handles. Thus the total rate is near-optimally matched for every relation between $\varepsilon$ and $\gamma$.
Second-order stationarity requires more than a small gradient: an optimizer must also avoid directions with sufficiently negative curvature. In stochastic nonconvex optimization, that accounting becomes uncertain when an algorithm can keep an opaque handle to a sampled loss and query the same sample repeatedly. Reuse can reveal local structure that ordinary fresh-sample lower bounds do not address. This paper closes that gap by proving a near-matching upper and lower total derivative-query rate for finding an (ε, γ)-second-order stationary point in the high-dimensional worst case.
Core Contribution
The paper's main theorem gives minimax total derivative-query complexity of near Θ(ε⁻³ + γ⁻³), with logarithmic factors suppressed and positive problem parameters fixed. Its accounting charges gradients and complete Hessians separately, including both endpoints of a same-sample difference. That choice matters: it permits sample reuse without treating reused evaluations as free.
The upper bound shows that the target rate is attainable under sample-wise Lipschitz gradient and Hessian assumptions. The lower bounds show that persistent handles and complete-Hessian access do not improve the asymptotic total rate. This is distinctive because a fresh-sample lower bound alone would not rule out an adaptive algorithm learning enough from repeated queries to one sample to evade the usual first-order barrier.
Technical Approach
For the upper bound, the authors use curvature-first randomly signed negative-curvature steps before concentrating on gradient reduction. Their binary-ancestor derivative estimators reuse cached same-sample differences through a tree structure, sharing evaluations while retaining a tractable error analysis. A truncated increment estimate separates predictable drift from martingale motion, charging the former linearly and the latter quadratically.
The target combines small first-order error with an approximate curvature certificate: the gradient norm is at most ε and the minimum Hessian eigenvalue is at least −γ. The analysis converts estimator guarantees into finite iteration and derivative budgets while distinguishing gradient and Hessian spending rather than compressing all information into a single oracle unit.
For the curvature lower bound, the proof starts from a deterministic smooth bounded-gradient chain. Its sequential-revelation construction ensures that, while a coordinate remains incomplete, function values, gradients, and complete Hessians only expose a revealed prefix. A radial barrier prevents easy stationary outputs away from the chain, and a random rotation conceals the chain from adaptive algorithms. This construction yields the γ-dependent obstruction even when complete Hessians are available.
The first-order lower bound uses a slowly parameterized conservative sign chain with a finite coefficient table. A third-order reverse stick-breaking localization argument controls the required derivatives. Stateful relative-entropy accounting then tracks the information disclosed by each reusable handle. Once a handle has revealed its relevant table entry, re-querying it does not reveal the next hidden block; persistence therefore does not eliminate the sequential information bottleneck.
Results and Analysis
This is a proof paper rather than an empirical benchmark. Its substantive result is a matched asymptotic characterization: an upper bound at near ε⁻³ + γ⁻³, a curvature lower bound of Ω(γ⁻³), and a reuse-aware first-order construction that supplies the ε-dependent obstruction.
The evidence applies within the stated oracle model, which allows arbitrary adaptive queries, complete-Hessian responses, and persistent sample handles. The conclusion is not a practical runtime forecast. It is a high-dimensional minimax statement under smoothness and opaque-handle assumptions. For variance-reduced or sample-reuse methods, the implication is narrow but useful: an asymptotic improvement must exploit assumptions beyond this model, improve constants or logarithmic terms, or aim at a different optimization criterion.
Evidence Box
theoreticalKey Claims
- •Near-optimal total derivative complexity under persistent sample reuse
- •Complete-Hessian access does not improve the matched asymptotic rate
- •Reuse-aware information accounting recovers the first-order lower bound
Key Results
- •Minimax total complexity near Θ(ε⁻³ + γ⁻³) for fixed positive parameters
- •Curvature hard instance requires Ω(γ⁻³) total derivative queries
- •Upper bound uses curvature-first steps and reusable derivative estimators
- •First-order lower bound remains robust to persistent sample reuse and complete-Hessian access
Limitations & Caveats
- •Worst-case high-dimensional analysis rather than finite-dimensional performance
- •Assumes sample-wise Lipschitz gradients and Hessians
- •Opaque reusable-handle oracle may not represent all practical data-access models
- •The result characterizes asymptotic query complexity, not wall-clock performance
