# Finding Stationary Points by Comparisons

arXiv: https://arxiv.org/abs/2606.27082 · HTML: https://mlsanity.com/paper/2606.27082/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 47 references that are in the map.
- First posted on arXiv 25 Jun 2026.

## Builds on (most cited first, 29 of 29)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Dueling Posterior Sampling for Preference-Based Reinforcement Learning](https://mlsanity.com/paper/1908.01289/) (2019)
- [Gradientless Descent: High-Dimensional Zeroth-Order Optimization](https://mlsanity.com/paper/1911.06317/) (2019)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [Stochastic Three Points Method for Unconstrained Smooth Minimization](https://mlsanity.com/paper/1902.03591/) (2019)
- [On the Optimization Landscape of Tensor Decompositions](https://mlsanity.com/paper/1706.05598/) (2017)
- [FedRLHF: A Convergence-Guaranteed Federated Framework for Privacy-Preserving and Personalized RLHF](https://mlsanity.com/paper/2412.15538/) (2024)
- [Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms](https://mlsanity.com/paper/1504.05287/) (2015)
- [A Stochastic Derivative Free Optimization Method with Momentum](https://mlsanity.com/paper/1905.13278/) (2019)
- [On Faster Convergence of Scaled Sign Gradient Descent](https://mlsanity.com/paper/2109.01806/) (2021)
- [Dueling Convex Optimization with General Preferences](https://mlsanity.com/paper/2210.02562/) (2022)
- [First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians](https://mlsanity.com/paper/2309.02412/) (2023)
- [Smooth Convex Optimization using Sub-Zeroth-Order Oracles](https://mlsanity.com/paper/2103.00667/) (2021)
- [Faster Convergence with Multiway Preferences](https://mlsanity.com/paper/2312.11788/) (2023)
- [Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values](https://mlsanity.com/paper/2402.09014/) (2024)
- [On The Global Convergence Of Online RLHF With Neural Parametrization](https://mlsanity.com/paper/2410.15610/) (2024)
- [Balancing Gradient and Hessian Queries in Non-Convex Optimization](https://mlsanity.com/paper/2510.20786/) (2025)
- [Function-free Optimization via Comparison Oracles](https://mlsanity.com/paper/2604.26867/) (2026)

## Built on by (most cited first, 1 of 1)

- [Learning in Continuous Games from Pairwise Preference Feedback](https://mlsanity.com/paper/2610.05428/) (2026)

## Abstract (arXiv)

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 fcolonmathbb Rn→mathbb R with Lipschitz gradient and Hessian, we develop an algorithm that visits an ε-stationary point using widetilde O(n2/ε1.5) queries. Our approach uses a subroutine that estimates the normalized Hessian to accuracy δ using widetilde O(n2log(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.