This study investigates the problem of finding stationary points of non-convex functions when access to the objective is provided solely through a comparison oracle. Specifically, for a twice differentiable function $f\colon\mathbb{R}^n\to\mathbb{R}$ with Lipschitz continuous gradient and Hessian, we develop an algorithm that visits an $\epsilon$-stationary point using $\widetilde{O}(n^2/\epsilon^{1.5})$ queries. Our approach employs a subroutine that estimates the normalized Hessian to an accuracy of $\delta$ using $\widetilde{O}(n^2\log(1/\delta))$ queries.
Furthermore, we explore this problem in the context of a quantum comparison oracle model, where queries can be made in superpositions. We present the first quantum algorithm that finds an $\epsilon$-stationary point, requiring $\widetilde{O}(n/\epsilon^{1.5})$ queries.
Blogger's Review: This research opens new avenues in non-convex optimization, particularly in finding stationary points relying solely on comparison oracles. The complexity analysis of the algorithms and the application of quantum models provide significant insights for future studies.