# Non-Stochastic CDF Estimation Using Threshold Queries

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 33 references that are in the map.
- First posted on arXiv 13 Jan 2023.

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

- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Optimal Quantile Approximation in Streams](https://mlsanity.com/paper/1603.05346/) (2016)
- [Pricing Query Complexity of Revenue Maximization](https://mlsanity.com/paper/2111.03158/) (2021)
- [Learning to Price Against a Moving Target](https://mlsanity.com/paper/2106.04689/) (2021)
- [Learning with Comparison Feedback: Online Estimation of Sample Statistics](https://mlsanity.com/paper/2101.04176/) (2021)
- [Learning Valuation Distributions from Partial Observation](https://mlsanity.com/paper/1407.2855/) (2014)

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

- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)

## Abstract (arXiv)

Estimating the empirical distribution of a scalar-valued data set is a basic and fundamental task. In this paper, we tackle the problem of estimating an empirical distribution in a setting with two challenging features. First, the algorithm does not directly observe the data; instead, it only asks a limited number of threshold queries about each sample. Second, the data are not assumed to be independent and identically distributed; instead, we allow for an arbitrary process generating the samples, including an adaptive adversary. These considerations are relevant, for example, when modeling a seller experimenting with posted prices to estimate the distribution of consumers' willingness to pay for a product: offering a price and observing a consumer's purchase decision is equivalent to asking a single threshold query about their value, and the distribution of consumers' values may be non-stationary over time, as early adopters may differ markedly from late adopters. Our main result quantifies, to within a constant factor, the sample complexity of estimating the empirical CDF of a sequence of elements of [n], up to varepsilon additive error, using one threshold query per sample. The complexity depends only logarithmically on n, and our result can be interpreted as extending the existing logarithmic-complexity results for noisy binary search to the more challenging setting where noise is non-stochastic. Along the way to designing our algorithm, we consider a more general model in which the algorithm is allowed to make a limited number of simultaneous threshold queries on each sample. We solve this problem using Blackwell's Approachability Theorem and the exponential weights method. As a side result of independent interest, we characterize the minimum number of simultaneous threshold queries required by deterministic CDF estimation algorithms.