仅通过比较函数值大小，高效找到非凸函数的驻点。
Finding Stationary Points by Comparisons
- 用比较查询估计归一化海森矩阵，实现精准定位。
- 经典算法需约 $n^2/ε^{1.5}$ 次查询到达 ε-驻点。
- 量子版本提速至 $n/ε^{1.5}$ 次查询，首次实现此目标。
我们研究在仅能通过比较两个点函数值大小获取信息的情况下，寻找非凸函数驻点的问题。对于梯度和海森矩阵均满足Lipschitz条件的二阶可微函数 $fackslashcolon\mathbb R^n\to\mathbb R$，我们提出一种算法，在 $ ilde O(n^2/ε^{1.5})$ 次查询内达到 $ε$-驻点。该方法包含一个子程序，可在 $ ilde O(n^2\log(1/δ))$ 次查询内将归一化海森矩阵估计到精度 $δ$。此外，我们还研究了量子比较查询模型，即允许在叠加态中进行查询，提出首个量子算法，可在 $ ilde O(n/ε^{1.5})$ 次查询内找到 $ε$-驻点。
原文摘要 · Abstract (English)
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 comparison oracle model where queries can be made in superpositions, and develop the first quantum algorithm that finds an $ε$-stationary point, which takes $\widetilde O(n/ε^{1.5})$ queries.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。