Matching Complexity for Second-Order Stationary Point with Sample Reuse

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

arXivarxiv/2610.16832Oct 12, 2026math.OCscore 0

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,γ)$-second-order stationary point is \begin{equation*} \widetildeΘ(\varepsilon^{-3}+γ^{-3}). \end{equation*} The upper bound combines curvature-first randomly signed…

SourceJSON

Comments and reviews

No comments yet.

API

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