Optimization via Comparison Oracles

20 concepts14 papers1 proposal

Traditional optimization algorithms are hungry for magnitudes. Whether calculating a precise gradient step $\nabla f(x)$ or evaluating a scalar loss $f(x)$, classical frameworks rely on knowing how much better or worse one solution is compared to another. However, in many real-world domains—such as human preference elicitation, reinforcement learning from human feedback (RLHF), and clinical trials—absolute numerical scores are non-existent or heavily distorted by noise. Humans excel at stating a preference ("Option A is better than Option B") but struggle to assign a consistent, precise scalar value to complex outputs.

This constraint motivates the study of optimization via comparison oracles (or order oracles). In this paradigm, the algorithm cannot observe function values or gradients; it can only query pairs of points $(x, y)$ and receive a single binary bit indicating whether $f(x) > f(y)$. As formalized by Saha et al. in Dueling Convex Optimization, this setup introduces a severe information bottleneck: how do you navigate a continuous parameter space toward an optimum when you are completely stripped of magnitude information?

Extracting Geometry from Binary Choices

To understand why optimization is possible under this constraint, we must look at how continuous geometric signals can be extracted from purely ordinal feedback.

Imagine standing on a dark, foggy hillside. You do not have an altimeter to read your exact elevation, but you can stick out your left foot and your right foot along a random direction vector $u$ and feel which foot is higher. If the position at $x + \delta u$ is higher than $x - \delta u$, you know the function increases along that direction.

This is the core intuition behind gradient estimation via comparisons. By sampling a random direction vector $u$ and querying the comparison oracle around the current iterate $x$, an algorithm can determine the sign of the directional derivative. As shown by Karabag et al. in Smooth Convex Optimization Using Sub-Zeroth-Order Oracles, knowing merely the sign of directional derivatives is sufficient to optimize smooth convex functions with polynomial sample complexity.

To build an explicit gradient vector, an algorithm can sample multiple random directions $\{u_i\}$ and aggregate the binary feedback. Zhang et al. demonstrate in Comparisons Are All You Need for Optimizing Smooth Functions that these binary responses contain enough statistical information to reconstruct the direction of the true gradient. Furthermore, Tao et al. prove in Gradient Testing and Estimation by Comparisons that one can test whether the gradient aligns with any given direction in constant time, completely independent of the dimensionality of the space.

Once the direction of the gradient is recovered, the algorithm can update its position using a normalized gradient descent framework, as explored by Гасников et al. in On Quasi-Convex Smooth Optimization Problems by a Comparison Oracle. Because the step size cannot scale with the gradient's magnitude, these algorithms rely on carefully engineered step-size decay schedules or line-search dichotomies to guarantee convergence.

Why Ordinal Feedback Costs Nothing Asymptotically

It is natural to assume that throwing away exact numerical values inflicts a heavy penalty on convergence speed. Remarkably, in stochastic or noisy settings, this penalty disappears entirely.

In Query Complexity of Derivative-Free Optimization, Jamieson et al. analyzed derivative-free optimization under stochastic noise. They proved that when function evaluations are noisy, traditional methods relying on absolute scalar values hit a fundamental convergence floor of $\Omega(1/\sqrt{T})$. Crucially, the authors showed that an algorithm utilizing only noisy binary comparisons achieves this exact same optimal rate.

Why does access to exact values offer no asymptotic advantage over binary comparisons? In a noisy environment, the precise difference between $f(x)$ and $f(y)$ is dominated by variance. The magnitude information is mostly noise. The binary comparison acts as a robust filter: it discards the noisy magnitude and preserves the sign, which contains the resilient directional signal.

This insight opens the door to advanced optimization techniques. For instance, Lobanov et al. show in Acceleration Exists! Optimization Problems When Oracle Can Only Compare Objective Function Values that Nesterov-style accelerated convergence is achievable using only comparison oracles, matching the efficiency of high-end gradient methods up to a small logarithmic factor. Similarly, Chervonenkis et al. adapt these principles to multi-variable coordinate spaces in Nesterov's Method of Dichotomy via Order Oracle: The Problem of Optimizing a Two-Variable Function on a Square.

To handle the residual noise inherent in stochastic comparisons, Smirnov et al. demonstrate in Asymptotic Analysis of the Ruppert – Polyak Averaging for Stochastic Order Oracle that applying Ruppert-Polyak averaging to the sequence of comparison-driven iterates minimizes asymptotic covariance, allowing the algorithm to smoothly home in on the exact optimum.

Beyond Convexity: Reconstructing Higher-Order Landscapes

The utility of comparison oracles extends beyond simple convex minimization. Recent developments show that binary comparisons can map out highly complex, non-convex landscapes and guide global exploration.

For non-convex optimization, finding stationary points requires understanding curvature, which typically demands second-order derivatives (the Hessian matrix). In Finding Stationary Points by Comparisons, Wang et al. show that by evaluating structured triplets of points rather than pairs, a comparison oracle can be used to reconstruct second-order geometric information. This allows the algorithm to detect saddle points and successfully navigate non-convex landscapes with query complexities that match classical second-order methods.

Furthermore, comparison-based frameworks can be integrated into global Bayesian optimization. When exploring an unknown function space where evaluations are expensive and preferential, Lazzaro et al. prove in A Finite Time Analysis of Thompson Sampling for Bayesian Optimization with Preferential Feedback that maintaining a posterior distribution over the latent objective function using only pairwise comparisons achieves the same theoretical sample efficiency as traditional scalar-based Thompson Sampling.

Key Foundational Work

Query Complexity of Derivative-Free Optimization (2012) — contributed 2 concept elements to this direction.
Comparison-Based Algorithms for One-Dimensional Stochastic Convex Optimization (2020) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_ordinal_feedback_constraints_f6468098,
  title = {ordinal feedback constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ordinal-feedback-constraints/rdr_f64680989eb740e4b9e74799f2d43a5b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_ordinal_feedback_constraints_f6468098_v1,
  title = {ordinal feedback constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ordinal-feedback-constraints/rdr_f64680989eb740e4b9e74799f2d43a5b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake