{"id":"arxiv/2609.28238","url":"https://arxiv.org/abs/2609.28238","tags":["math.OC"],"score":0,"title":"Second-Order Stationarity with Common Random Losses: Matching Tolerance Bounds","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"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 ε$ and $λ_{\\min}(\\nabla^2 F(x))\\ge -γ$, with independent tolerances $ε,γ>0$. Under bounded gradient variance and almost-surely bounded Hessian error, the minimax number of fresh gradient or Hessian-vector-product calls is $\\widetildeΘ\\!\\left(ε^{-3}+γ^{-5}\\right)$. The characterization fixes positive gap, smoothness, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}