# Making the Most of Your Samples

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2014.

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

- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)
- [Beyond IID: data-driven decision-making in heterogeneous environments](https://mlsanity.com/paper/2206.09642/) (2022)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Robust Learning of Optimal Auctions](https://mlsanity.com/paper/2107.06259/) (2021)
- [Convex Surrogate Loss Functions for Contextual Pricing with Transaction Data](https://mlsanity.com/paper/2202.10944/) (2022)
- [Online Auction Design Using Distribution-Free Uncertainty Quantification with Applications to E-Commerce](https://mlsanity.com/paper/2405.07038/) (2024)
- [Learn then Decide: A Learning Approach for Designing Data Marketplaces](https://mlsanity.com/paper/2503.10773/) (2025)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (2022)
- [On the limitations of data-based price discrimination](https://mlsanity.com/paper/2204.12723/) (2022)
- [Learning Underspecified Models](https://mlsanity.com/paper/2207.10140/) (2022)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)

## Abstract (arXiv)

We study the problem of setting a price for a potential buyer with a valuation drawn from an unknown distribution D. The seller has "data"' about D in the form of m ≥ 1 i.i.d. samples, and the algorithmic challenge is to use these samples to obtain expected revenue as close as possible to what could be achieved with advance knowledge of D. Our first set of results quantifies the number of samples m that are necessary and sufficient to obtain a (1-ε)-approximation. For example, for an unknown distribution that satisfies the monotone hazard rate (MHR) condition, we prove that tildeTheta(ε-3/2) samples are necessary and sufficient. Remarkably, this is fewer samples than is necessary to accurately estimate the expected revenue obtained by even a single reserve price. We also prove essentially tight sample complexity bounds for regular distributions, bounded-support distributions, and a wide class of irregular distributions. Our lower bound approach borrows tools from differential privacy and information theory, and we believe it could find further applications in auction theory. Our second set of results considers the single-sample case. For regular distributions, we prove that no pricing strategy is better than tfrac12-approximate, and this is optimal by the Bulow-Klemperer theorem. For MHR distributions, we show how to do better: we give a simple pricing strategy that guarantees expected revenue at least 0.589 times the maximum possible. We also prove that no pricing strategy achieves an approximation guarantee better than frace4 ≈ .68.