mlsanityData to 7 Oct 2026

Finding Stationary Points by Comparisons

arXiv 2606.27082 ↗First posted 25 Jun 2026cs.LG cs.DS math.OCcited by 0

Not on the map. Why?

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 47 references that are in the map. First posted on arXiv 25 Jun 2026.

Builds on

29 of 47 references.

References · 29

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2017Deep reinforcement learning from human preferencescited by 3,846
  3. 2018signSGD: Compressed Optimisation for Non-Convex Problemscited by 561
  4. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 244
  5. 2017Lower Bounds for Finding Stationary Points Icited by 125
  6. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  7. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  8. 2023Is RLHF More Difficult than Standard RL?cited by 96
  9. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  10. 2013Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optimacited by 66
  11. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  12. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
17 more
  1. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  2. 2019Gradientless Descent: High-Dimensional Zeroth-Order Optimizationcited by 42
  3. 2023Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oraclescited by 34
  4. 2019Stochastic Three Points Method for Unconstrained Smooth Minimizationcited by 24
  5. 2017On the Optimization Landscape of Tensor Decompositionscited by 21
  6. 2024FedRLHF: A Convergence-Guaranteed Federated Framework for Privacy-Preserving and Personalized RLHFcited by 11
  7. 2015Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithmscited by 10
  8. 2019A Stochastic Derivative Free Optimization Method with Momentumcited by 9
  9. 2021On Faster Convergence of Scaled Sign Gradient Descentcited by 6
  10. 2023First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessianscited by 6
  11. 2022Dueling Convex Optimization with General Preferencescited by 5
  12. 2021Smooth Convex Optimization using Sub-Zeroth-Order Oraclescited by 3
  13. 2024Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Valuescited by 3
  14. 2024On The Global Convergence Of Online RLHF With Neural Parametrizationcited by 3
  15. 2023Faster Convergence with Multiway Preferencescited by 2
  16. 2025Balancing Gradient and Hessian Queries in Non-Convex Optimizationcited by 2
  17. 2026Function-free Optimization via Comparison Oraclescited by 1

Built on by

Not cited yet.