Common-Loss Oracles Match Second-Order Tolerance Bounds
Random-line Hessian estimates and a dyadic gradient tracker attain the minimax $\widetilde{\Theta}(\epsilon^{-3}+\gamma^{-5})$ oracle rate without the earlier mixed tolerance cost.
Underlying Paper
Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds
We establish tight polynomial tolerance bounds for stochastic second-order stationarity when each fresh oracle response is a derivative of one common random scalar loss. For a population objective $F$ with Lipschitz gradient and Hessian, the target is $\|\nabla F(x)\|\le \epsilon$ and $\lambda_{\min}(\nabla^2 F(x))\ge -\gamma$, with independent tolerances $\epsilon,\gamma>0$. Under bounded gradient variance and almost-surely bounded Hessian error, the minimax number of fresh gradient or Hessian-vector-product calls is $\widetilde{\Theta}\!\left(\epsilon^{-3}+\gamma^{-5}\right)$. The characterization fixes positive gap, smoothness, and noise parameters, suppresses logarithmic factors, and allows dimension to grow within an explicit polynomial envelope. The upper bound removes the mixed term $\epsilon^{-2}\gamma^{-2}$ from the earlier fresh-HVP guarantee. Direct random-line Hessian estimates and a dyadic gradient tracker separate gradient drift from randomly signed curvature motion. The lower bound realizes the endpoint costs through globally defined smooth random losses: a smooth partition localizes scalar noise without a chain-length penalty, while exact cancellation limits the information in the entire response. Consequently, the same tolerance exponents hold even for joint value, gradient, and full-Hessian responses with bounded value variance. For a population Hessian with H\"older exponent $\nu\in(0,1]$, fresh gradient/HVP complexity becomes $\widetilde{\Theta}\!\left(\epsilon^{-3}+\gamma^{-(3+2/\nu)}\right)$ under the corresponding dimension envelope.
The authors establish matching upper and lower bounds for this setting. Under Lipschitz gradient and Hessian assumptions, bounded gradient variance, and almost-surely bounded Hessian error, they characterize the fresh gradient or Hessian-vector-product cost as . The key editorial point is not merely the exponent pair: the additive form separates first-order and curvature accuracy rather than charging an extra product of the two tolerances.
Core Contribution
Earlier fresh-HVP guarantees contained a mixed term. The paper removes that term in the common-random-loss model and pairs the improved upper bound with a minimax lower bound of the same polynomial order, up to logarithmic factors. That match is meaningful because it says the proposed analysis is not simply improving an existing algorithmic estimate; within the stated oracle class, neither tolerance dependence can generally be improved in polynomial order.
The lower-bound construction is also designed around the stronger information available from a common scalar loss. The authors construct globally defined smooth random losses in which scalar noise is localized through a smooth partition, avoiding a chain-length penalty. Exact cancellation then constrains how much information an entire response reveals. The abstract states that this conclusion persists even when an oracle supplies value, gradient, and full-Hessian information jointly, provided value variance is bounded. In other words, access to a richer derivative package does not change the stated tolerance exponents for the hard instances.
Technical Approach
The upper-bound argument separates two sources of stochastic difficulty. Direct random-line Hessian estimates are used to assess curvature along random directions, while a dyadic gradient tracker handles gradient drift independently of the randomly signed curvature motion. That division is the mechanism behind removing the mixed term: gradient estimation is not repeatedly paid for at the curvature-search scale.
The result is framed for fresh oracle calls, meaning the complexity counts newly sampled gradient or Hessian-vector-product information. This detail matters because methods that can reuse a fixed sample set face a different statistical-computational trade-off. The paper's statement is therefore a characterization of an online-style stochastic derivative regime, not a universal complexity result for every finite-sum or deterministic second-order method.
The analysis also extends beyond a Lipschitz population Hessian. If the Hessian is Hölder continuous with exponent , the stated complexity becomes
At , this recovers the curvature dependence. Lower regularity makes curvature certification more expensive, which is consistent with the need to infer negative-curvature structure from less stable Hessian variation.
Results and Analysis
This is a theoretical result, so its evidence is a matched upper/lower-bound analysis rather than benchmark tables or empirical speed measurements. The paper directly supports the claim that, under its assumptions and an explicit polynomial dimension envelope, the fresh-oracle complexity has additive and terms. It also directly identifies the removed contribution from the earlier guarantee.
The practical implication is narrow but useful for researchers designing stochastic second-order methods. If their oracle genuinely returns derivatives of a shared sampled loss, then treating gradient accuracy and negative-curvature detection as separate tracking problems can avoid an unnecessary tolerance coupling. The lower bound strengthens that message: within the modeled regime, reducing the cost requires changing assumptions or oracle access rather than refining the same tolerance accounting.
Scope and Caveats
The result fixes positive gap, smoothness, and noise parameters and suppresses logarithmic factors, so it does not provide constant-sensitive guidance for a concrete implementation. Its dimension may grow only within an explicit polynomial envelope. Moreover, the upper bound relies on bounded gradient variance and almost-surely bounded Hessian error; those conditions can be restrictive for heavy-tailed losses or derivative estimators without uniform control. The paper establishes oracle complexity, not observed wall-clock behavior on a numerical workload.
Evidence Box
strongKey Claims
- •Common random losses admit additive first- and second-order tolerance costs
- •Fresh gradient/HVP complexity matches ε⁻³ + γ⁻⁵ up to logarithmic factors
- •Richer joint value, gradient, and Hessian responses do not improve the hard-instance exponents
- •Hölder Hessian regularity changes the curvature tolerance exponent
Key Results
- •Fresh gradient/HVP complexity $\widetilde{\Theta}(\epsilon^{-3}+\gamma^{-5})$ under Lipschitz Hessian assumptions
- •The upper bound removes the earlier $\epsilon^{-2}\gamma^{-2}$ mixed term
- •For Hölder exponent $\nu\in(0,1]$, complexity is $\widetilde{\Theta}(\epsilon^{-3}+\gamma^{-(3+2/\nu)})$
- •At $\nu=1$, the Hölder expression yields the $\gamma^{-5}$ curvature term
Limitations & Caveats
- •Logarithmic factors are suppressed in the complexity characterization
- •Gap, smoothness, and noise parameters are fixed as positive constants
- •Dimension must remain within an explicit polynomial envelope
- •Upper-bound assumptions require bounded gradient variance and almost-surely bounded Hessian error
