Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem
This work addresses generalization in machine learning for product distributions, offering theoretical advances with applications in algorithmic game theory, but it is incremental as it builds on existing frameworks.
The paper tackles the problem of generalization for learning on product distributions without relying on hypothesis class complexity, establishing two sample complexity bounds: one for distributions with finite support and another for strongly monotone problems. It applies these bounds to match or improve state-of-the-art results in auctions, prophet inequalities, and Pandora's problem, providing tight sample complexity bounds.
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) $\tilde{O} \big( \frac{nk}{ε^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) $\tilde{O} \big( \frac{n}{ε^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.