Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg, Eleanor Goh
arXiv 13 Jan 2023 · Machine Learning · 2 citations (OpenAlex)
arXiv:2301.05682 · PDF · DOI · OpenAlex · Extracted main text
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.
appendix boundary found by appendix_command · 49% of the source is main text. Read the extracted text to check this.
The works this paper leans on most, across its whole bibliography — not restricted to papers in our corpus. Ranked by composite intensity, which combines how often a work is mentioned, how many sections mention it, and how much of that falls in the main text rather than the appendix.
| Reference | Intensity | Mentions | Sections | Main text | |
|---|---|---|---|---|---|
| 1 | Meister, M. and Nietert, S (2021) Learning with comparison feedback: Online estimation of sample statistics | 0.916 | 13 | 5 | 77% |
| 2 | Barnes, L. P., Han, Y., and Ozgur, A (2020) Lower bounds for learning distributions under communication constraints via fisher information | 0.585 | 3 | 1 | 100% |
| 3 | Acharya, J., Canonne, C. L., Sun, Z., and Tyagi, H (2020) Unified lower bounds for interactive high-dimensional estimation under information constraints | 0.511 | 2 | 1 | 100% |
| 4 | Greenwald, M. and Khanna, S (2001) Space-efficient online computation of quantile summaries | 0.511 | 2 | 1 | 100% |
| 5 | Karp, R. M. and Kleinberg, R (2007) Noisy binary search and its applications self | 0.511 | 2 | 1 | 100% |
| 6 | Acharya, J., Canonne, C., Liu, Y., Sun, Z., and Tyagi, H (2021) Distributed estimation with multiple samples per user: Sharp rates and phase transition | 0.405 | 1 | 1 | 100% |
| 7 | Ali, S. and Ronaldson, S (2012) Ordinal preference elicitation methods in health economics and health services research: using discrete choice experiments and r… | 0.405 | 1 | 1 | 100% |
| 8 | Ben-Or, M. and Hassidim, A (2008) The bayesian learner is optimal for noisy binary search (and pretty good for quantum as well) | 0.405 | 1 | 1 | 100% |
| 9 | Blackwell, D (1956) An analog of the minimax theorem for vector payoffs | 0.405 | 1 | 1 | 100% |
| 10 | Blum, A., Mansour, Y., and Morgenstern, J (2015) Learning valuation distributions from partial observations | 0.405 | 1 | 1 | 100% |
Showing the top 10 of 31 scored citations.