# Settling the Sample Complexity of Single-parameter Revenue Maximization

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2019.

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

- [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)
- [A Context-Integrated Transformer-Based Neural Network for Auction Design](https://mlsanity.com/paper/2201.12489/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Are Bounded Contracts Learnable and Approximately Optimal?](https://mlsanity.com/paper/2402.14486/) (2024)
- [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)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [New Guarantees for Learning Revenue Maximizing Menus of Lotteries and Two-Part Tariffs](https://mlsanity.com/paper/2302.11700/) (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)
- [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)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (2025)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)
- [On the limitations of data-based price discrimination](https://mlsanity.com/paper/2204.12723/) (2022)
- [Sample Complexity of Forecast Aggregation](https://mlsanity.com/paper/2207.13126/) (2022)
- [Refined Mechanism Design for Approximately Structured Priors via Active Regression](https://mlsanity.com/paper/2310.07874/) (2023)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)
- [Pricing Query Complexity of Multiplicative Revenue Approximation](https://mlsanity.com/paper/2602.10483/) (2026)
- [Is Online Linear Optimization Sufficient for Strategic Robustness?](https://mlsanity.com/paper/2602.12253/) (2026)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)
- [Learning to Price with Persuasion](https://mlsanity.com/paper/2608.16699/) (2026)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

This paper settles the sample complexity of single-parameter revenue maximization by showing matching upper and lower bounds, up to a poly-logarithmic factor, for all families of value distributions that have been considered in the literature. The upper bounds are unified under a novel framework, which builds on the strong revenue monotonicity by Devanur, Huang, and Psomas (STOC 2016), and an information theoretic argument. This is fundamentally different from the previous approaches that rely on either constructing an ε-net of the mechanism space, explicitly or implicitly via statistical learning theory, or learning an approximately accurate version of the virtual values. To our knowledge, it is the first time information theoretical arguments are used to show sample complexity upper bounds, instead of lower bounds. Our lower bounds are also unified under a meta construction of hard instances.