Finding Stationary Points by Comparisons

Helin Wang, Chenyi Zhang, Xiwen Tao, Yexin Zhang, Tongyang Li

arXivarxiv/2606.27082Jun 25, 2026cs.LGscore 0

We study the problem of finding stationary points of non-convex functions when access to the objective is provided only through a comparison oracle that, given two points, outputs which has the larger function value. For a twice differentiable $f\colon\mathbb R^n\to\mathbb R$ with Lipschitz gradient and Hessian, we develop an algorithm that visits an $ε$-stationary point using $\widetilde O(n^2/ε^{1.5})$ queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy $δ$ using $\widetilde O(n^2\log(1/δ))$ queries. We further study this problem with a quantum…

SourceJSON

Comments and reviews

No comments yet.

API

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