Research map / Learning theory and algorithms / Sample complexity
A Sample Complexity Measure with Applications to Learning Optimal Auctions
Vasilis Syrgkanis
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound ERM generalization with the split-sample hypothesis space rather than the full hypothesis class | General ERM · General PAC learning | expected generalization error upper bound: \sqrt{\frac{2\log(\hat{\tau}_H(2m))}{m}} | Improved |
| Choose reserve prices from observed valuations | ERM reserve pricing · Single bidder, single item | expected revenue loss upper bound: \sqrt{\frac{2\log(2m)}{m}} | Improved |
| Choose a shared reserve from observed valuations | ERM second-price auction · Multiple i.i.d. regular bidders, single item | expected revenue loss upper bound: \sqrt{\frac{2\log(2\cdot n\cdot m)}{m}} | Improved |
| Use player-specific reserves selected from observed values | ERM second-price auction · Non-i.i.d. regular bidders, single item | expected revenue loss upper bound: \sqrt{\frac{2n\log(2m)}{m}} | Improved |
| Coarsen virtual value functions to an epsilon grid | ERM over t-level auctions · Non-i.i.d. irregular bidders, single item | expected revenue loss upper bound: 2\left(\frac{2n\log(2m)}{m}\right)^{1/3} | Improved |
Closest papers by meaning
- Sample Complexity of Posted Pricing for a Single Item (NeurIPS 2024 · similarity 0.88)
- Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization (NeurIPS 2025 · similarity 0.86)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.85)
- Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response (ICML 2025 · similarity 0.84)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.84)
- Procurement Auctions via Approximately Optimal Submodular Optimization (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
