{"id":"arxiv/2606.27082","url":"https://arxiv.org/abs/2606.27082","tags":["cs.LG","cs.DS","math.OC","quant-ph"],"score":0,"title":"Finding Stationary Points by Comparisons","domain":"cs.LG","source":"arxiv","authors":["Helin Wang","Chenyi Zhang","Xiwen Tao","Yexin Zhang","Tongyang Li"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-25","reactions":{}}