# The Sample Complexity of Revenue Maximization

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

## Key facts

- Cited by 48 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Feb 2015.

## Built on by (most cited first, 30 of 48)

- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Optimal-er Auctions through Attention](https://mlsanity.com/paper/2202.13110/) (2022)
- [A Scalable Neural Network for DSIC Affine Maximizer Auction Design](https://mlsanity.com/paper/2305.12162/) (2023)
- [Customizing ML Predictions for Online Algorithms](https://mlsanity.com/paper/2205.08715/) (2022)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [A Context-Integrated Transformer-Based Neural Network for Auction Design](https://mlsanity.com/paper/2201.12489/) (2022)
- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (2025)
- [Learning Revenue-Maximizing Auctions With Differentiable Matching](https://mlsanity.com/paper/2106.07877/) (2021)
- [Benefits of Permutation-Equivariance in Auction Mechanisms](https://mlsanity.com/paper/2210.05579/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Learning to Maximize Gains From Trade in Small Markets](https://mlsanity.com/paper/2401.11596/) (2024)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (2023)
- [Machine Learning-Powered Combinatorial Clock Auction](https://mlsanity.com/paper/2308.10226/) (2023)
- [Robust Learning of Optimal Auctions](https://mlsanity.com/paper/2107.06259/) (2021)
- [Learning Thresholds with Latent Values and Censored Feedback](https://mlsanity.com/paper/2312.04653/) (2023)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [The Pseudo-Dimension of Contracts](https://mlsanity.com/paper/2501.14474/) (2025)
- [Automated Mechanism Design for Classification with Partial Verification](https://mlsanity.com/paper/2104.05182/) (2021)
- [Prices, Bids, Values: One ML-Powered Combinatorial Auction to Rule Them All](https://mlsanity.com/paper/2411.09355/) (2024)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Convex Surrogate Loss Functions for Contextual Pricing with Transaction Data](https://mlsanity.com/paper/2202.10944/) (2022)
- [Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation](https://mlsanity.com/paper/2211.15792/) (2022)
- [How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions](https://mlsanity.com/paper/2212.06422/) (2022)
- [User Response in Ad Auctions: An MDP Formulation of Long-Term Revenue Optimization](https://mlsanity.com/paper/2302.08108/) (2023)
- [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)

## Abstract (arXiv)

In the design and analysis of revenue-maximizing auctions, auction performance is typically measured with respect to a prior distribution over inputs. The most obvious source for such a distribution is past data. The goal is to understand how much data is necessary and sufficient to guarantee near-optimal expected revenue. Our basic model is a single-item auction in which bidders' valuations are drawn independently from unknown and non-identical distributions. The seller is given m samples from each of these distributions "for free" and chooses an auction to run on a fresh sample. How large does m need to be, as a function of the number k of bidders and eps > 0, so that a (1 - eps)-approximation of the optimal revenue is achievable? We prove that, under standard tail conditions on the underlying distributions, m = poly(k, 1/eps) samples are necessary and sufficient. Our lower bound stands in contrast to many recent results on simple and prior-independent auctions and fundamentally involves the interplay between bidder competition, non-identical distributions, and a very close (but still constant) approximation of the optimal revenue. It effectively shows that the only way to achieve a sufficiently good constant approximation of the optimal revenue is through a detailed understanding of bidders' valuation distributions. Our upper bound is constructive and applies in particular to a variant of the empirical Myerson auction, the natural auction that runs the revenue-maximizing auction with respect to the empirical distributions of the samples. Our sample complexity lower bound depends on the set of allowable distributions, and to capture this we introduce alpha-strongly regular distributions, which interpolate between the well-studied classes of regular (alpha = 0) and MHR (alpha = 1) distributions. We give evidence that this definition is of independent interest.