# Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Nov 2019.

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

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [VC Theory for Inventory Policies](https://mlsanity.com/paper/2404.11509/) (2024)
- [Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade](https://mlsanity.com/paper/2509.22563/) (2025)
- [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)
- [Selling Joint Ads: A Regret Minimization Perspective](https://mlsanity.com/paper/2409.07819/) (2024)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Online Combinatorial Allocations and Auctions with Few Samples](https://mlsanity.com/paper/2409.11091/) (2024)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [Learning to Play Multi-Follower Bayesian Stackelberg Games](https://mlsanity.com/paper/2510.01387/) (2025)
- [Uniform Laws of Large Numbers in Product Spaces](https://mlsanity.com/paper/2603.24493/) (2026)
- [How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions](https://mlsanity.com/paper/2212.06422/) (2022)
- [Survey of Data-driven Newsvendor: Unified Analysis and Spectrum of Achievable Regrets](https://mlsanity.com/paper/2409.03505/) (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)
- [Learning Markov Decision Processes under Fully Bandit Feedback](https://mlsanity.com/paper/2602.02260/) (2026)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (2022)
- [Sample Complexity of Forecast Aggregation](https://mlsanity.com/paper/2207.13126/) (2022)
- [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)
- [Optimal No-Regret Learning for Repeated Prophet Inequality](https://mlsanity.com/paper/2609.23265/) (2026)

## Abstract (arXiv)

This paper explores a theory of generalization for learning problems on product distributions, complementing the existing learning theories in the sense that it does not rely on any complexity measures of the hypothesis classes. The main contributions are two general sample complexity bounds: (1) tildeO big( fracnkε2 big) samples are sufficient and necessary for learning an ε-optimal hypothesis in any problem on an n-dimensional product distribution, whose marginals have finite supports of sizes at most k; (2) tildeO big( fracnε2 big) samples are sufficient and necessary for any problem on n-dimensional product distributions if it satisfies a notion of strong monotonicity from the algorithmic game theory literature. As applications of these theories, we match the optimal sample complexity for single-parameter revenue maximization (Guo et al., STOC 2019), improve the state-of-the-art for multi-parameter revenue maximization (Gonczarowski and Weinberg, FOCS 2018) and prophet inequality (Correa et al., EC 2019), and provide the first and tight sample complexity bound for Pandora's problem.