# The Sample Complexity of Auctions with Side Information

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2015.

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

- [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)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [Loss Functions for Discrete Contextual Pricing with Observational Data](https://mlsanity.com/paper/2111.09933/) (2021)
- [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)
- [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)
- [Automated Mechanism Design for Classification with Partial Verification](https://mlsanity.com/paper/2104.05182/) (2021)
- [Convex Surrogate Loss Functions for Contextual Pricing with Transaction Data](https://mlsanity.com/paper/2202.10944/) (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)
- [Learning Optimal Posted Prices for a Unit-Demand Buyer](https://mlsanity.com/paper/2506.02284/) (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)
- [Contextual Learning for Stochastic Optimization](https://mlsanity.com/paper/2505.16829/) (2025)
- [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)
- [On the Learning Curves of Revenue Maximization](https://mlsanity.com/paper/2604.26922/) (2026)

## Abstract (arXiv)

Traditionally, the Bayesian optimal auction design problem has been considered either when the bidder values are i.i.d., or when each bidder is individually identifiable via her value distribution. The latter is a reasonable approach when the bidders can be classified into a few categories, but there are many instances where the classification of bidders is a continuum. For example, the classification of the bidders may be based on their annual income, their propensity to buy an item based on past behavior, or in the case of ad auctions, the click through rate of their ads. We introduce an alternate model that captures this aspect, where bidders are a priori identical, but can be distinguished based (only) on some side information the auctioneer obtains at the time of the auction. We extend the sample complexity approach of Dhangwatnotai, Roughgarden, and Yan (2014) and Cole and Roughgarden (2014) to this model and obtain almost matching upper and lower bounds. As an aside, we obtain a revenue monotonicity lemma which may be of independent interest. We also show how to use Empirical Risk Minimization techniques to improve the sample complexity bound of Cole and Roughgarden (2014) for the non-identical but independent value distribution case.