# Learning with Comparison Feedback: Online Estimation of Sample Statistics

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 12 references that are in the map.
- First posted on arXiv 11 Jan 2021.

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

- [Deterministic and Probabilistic Binary Search in Graphs](https://mlsanity.com/paper/1503.00805/) (2015)
- [An Efficient Noisy Binary Search in Graphs via Median Approximation](https://mlsanity.com/paper/2005.00144/) (2020)

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

- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Non-Stochastic CDF Estimation Using Threshold Queries](https://mlsanity.com/paper/2301.05682/) (2023)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)

## Abstract (arXiv)

We study an online version of the noisy binary search problem where feedback is generated by a non-stochastic adversary rather than perturbed by random noise. We reframe this as maintaining an accurate estimate for the median of an adversarial sequence of integers, x1, x2, dots, in a model where each number xt can only be accessed through a single threshold query of the form 1(xt ≤ qt). In this online comparison feedback model, we explore estimation of general sample statistics, providing robust algorithms for median, CDF, and mean estimation with nearly matching lower bounds. We conclude with several high-dimensional generalizations.