在这篇研究中，我们探讨了如何在仅通过比较oracle访问目标的情况下找到非凸函数的驻点。具体来说，对于一个二次可微的函数 $f\colon\mathbb{R}^n\to\mathbb{R}$，其梯度和Hessian矩阵都是Lipschitz连续的，我们提出了一种算法，能够使用 $\widetilde{O}(n^2/\epsilon^{1.5})$ 次查询访问一个 $\epsilon$-驻点。该方法使用了一个子例程，该子例程通过 $\widetilde{O}(n^2\log(1/\delta))$ 次查询来估计归一化的Hessian矩阵到达精度 $\delta$。
此外，我们还研究了使用量子比较oracle模型的问题，在该模型中查询可以在叠加态中进行。我们开发了第一个量子算法，能够找到一个 $\epsilon$-驻点，查询次数为 $\widetilde{O}(n/\epsilon^{1.5})$。
博主点评： 这项研究在非凸优化领域开辟了新思路，尤其是在仅依赖比较oracle的情况下，展示了如何有效地找到驻点。算法的复杂度分析和量子模型的应用都为未来的研究提供了重要的启示。