Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds

Abstract

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 $\Vert \nabla F(x)\Vert \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 $\tilde{\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ölder exponent $\nu \in (0,1]$, fresh gradient/HVP complexity becomes $\tilde{\Theta }\left({\epsilon }^{-3}+{\gamma }^{-(3+2/\nu )}\right)$ under the corresponding dimension envelope.