# A One-bit, Comparison-Based Gradient Estimator

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

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

- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Zeroth-Order Optimization Meets Human Feedback: Provable Learning via Ranking Oracles](https://mlsanity.com/paper/2303.03751/) (2023)
- [Prompt-Tuning Decision Transformer with Preference Ranking](https://mlsanity.com/paper/2305.09648/) (2023)
- [ComPO: Preference Alignment via Comparison Oracles](https://mlsanity.com/paper/2505.05465/) (2025)
- [Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations](https://mlsanity.com/paper/2510.19975/) (2025)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Curvature-Aware Derivative-Free Optimization](https://mlsanity.com/paper/2109.13391/) (2021)
- [Stochastic Zeroth Order Gradient and Hessian Estimators: Variance Reduction and Refined Bias Bounds](https://mlsanity.com/paper/2205.14737/) (2022)
- [Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Function](https://mlsanity.com/paper/2506.03066/) (2025)
- [On the Optimal Construction of Unbiased Gradient Estimators for Zeroth-Order Optimization](https://mlsanity.com/paper/2510.19953/) (2025)
- [Convergence of Batch Updating Methods with Approximate Gradients and/or Noisy Measurements: Theory and Computational Results](https://mlsanity.com/paper/2209.05372/) (2022)
- [Gradient Testing and Estimation by Comparisons](https://mlsanity.com/paper/2405.11454/) (2024)
- [Sequential Resource Trading Using Comparison-Based Gradient Estimation](https://mlsanity.com/paper/2408.11186/) (2024)
- [Riemannian Dueling Optimization](https://mlsanity.com/paper/2603.00023/) (2026)
- [A Zeroth-Order Paradigm for LLM Preference Alignment](https://mlsanity.com/paper/2609.19144/) (2026)
- [Learning in Continuous Games from Pairwise Preference Feedback](https://mlsanity.com/paper/2610.05428/) (2026)

## Abstract (arXiv)

We study zeroth-order optimization for convex functions where we further assume that function evaluations are unavailable. Instead, one only has access to a textitcomparison oracle, which given two points x and y returns a single bit of information indicating which point has larger function value, f(x) or f(y). By treating the gradient as an unknown signal to be recovered, we show how one can use tools from one-bit compressed sensing to construct a robust and reliable estimator of the normalized gradient. We then propose an algorithm, coined SCOBO, that uses this estimator within a gradient descent scheme. We show that when f(x) has some low dimensional structure that can be exploited, SCOBO outperforms the state-of-the-art in terms of query complexity. Our theoretical claims are verified by extensive numerical experiments.