Accelerated Methods for Nonconvex Optimization Using Comparisons

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:{\mathbb{R}}^n\to \mathbb{R}$ with Lipschitz gradient and Hessian, we develop an algorithm that outputs a list of points containing at least one $ϵ$-stationary point using $\tilde{O}(n/{ϵ}^{7/4})$ queries, matching the state-of-the-art result of zeroth-order methods with function evaluations. To the best of our knowledge, our algorithm is the first one that achieves Nesterov-type acceleration with comparison queries. Technically, our approach combines restarted accelerated gradient descent with comparison-based estimates of gradient directions. Specifically, we design a geometric grid of guesses for gradient norms at reference points and an anchor-based procedure for estimating gradient norm ratios, enabling accelerated updates under controlled errors without direct access to gradient magnitudes.