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

Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2609.28238Sep 23, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.28238
curl -X POST /api/v1/records/arxiv/2609.28238/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28238/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'