Timezone: »
Poster
A Sample Complexity Measure with Applications to Learning Optimal Auctions
Vasilis Syrgkanis
We introduce a new sample complexity measure, which we refer to as split-sample growth rate. For any hypothesis $H$ and for any sample $S$ of size $m$, the split-sample growth rate $\hat{\tau}_H(m)$ counts how many different hypotheses can empirical risk minimization output on any sub-sample of $S$ of size $m/2$. We show that the expected generalization error is upper bounded by $O\left(\sqrt{\frac{\log(\hat{\tau}_H(2m))}{m}}\right)$. Our result is enabled by a strengthening of the Rademacher complexity analysis of the expected generalization error. We show that this sample complexity measure, greatly simplifies the analysis of the sample complexity of optimal auction design, for many auction classes studied in the literature. Their sample complexity can be derived solely by noticing that in these auction classes, ERM on any sample or sub-sample will pick parameters that are equal to one of the points in the sample.
Author Information
Vasilis Syrgkanis (Microsoft Research)
More from the Same Authors
-
2021 : Double/Debiased Machine Learning for Dynamic Treatment Effects via $g$-Estimation »
Greg Lewis · Vasilis Syrgkanis -
2021 : Estimating the Long-Term Effects of Novel Treatments »
Keith Battocchi · Maggie Hei · Greg Lewis · Miruna Oprescu · Vasilis Syrgkanis -
2021 Poster: Double/Debiased Machine Learning for Dynamic Treatment Effects »
Greg Lewis · Vasilis Syrgkanis -
2021 Poster: Asymptotics of the Bootstrap via Stability with Applications to Inference with Model Selection »
Morgane Austern · Vasilis Syrgkanis -
2021 Poster: Estimating the Long-Term Effects of Novel Treatments »
Keith Battocchi · Eleanor Dillon · Maggie Hei · Greg Lewis · Miruna Oprescu · Vasilis Syrgkanis -
2020 Poster: Minimax Estimation of Conditional Moment Models »
Nishanth Dikkala · Greg Lewis · Lester Mackey · Vasilis Syrgkanis -
2019 : Coffee break, posters, and 1-on-1 discussions »
Julius von Kügelgen · David Rohde · Candice Schumann · Grace Charles · Victor Veitch · Vira Semenova · Mert Demirer · Vasilis Syrgkanis · Suraj Nair · Aahlad Puli · Masatoshi Uehara · Aditya Gopalan · Yi Ding · Ignavier Ng · Khashayar Khosravi · Eli Sherman · Shuxi Zeng · Aleksander Wieczorek · Hao Liu · Kyra Gan · Jason Hartford · Miruna Oprescu · Alexander D'Amour · Jörn Boehnke · Yuta Saito · Théophile Griveau-Billion · Chirag Modi · Shyngys Karimov · Jeroen Berrevoets · Logan Graham · Imke Mayer · Dhanya Sridhar · Issa Dahabreh · Alan Mishler · Duncan Wadsworth · Khizar Qureshi · Rahul Ladhania · Gota Morishita · Paul Welle -
2019 Poster: Semi-Parametric Efficient Policy Learning with Continuous Actions »
Victor Chernozhukov · Mert Demirer · Greg Lewis · Vasilis Syrgkanis -
2019 Poster: Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing »
Jonas Mueller · Vasilis Syrgkanis · Matt Taddy -
2019 Poster: Machine Learning Estimation of Heterogeneous Treatment Effects with Instruments »
Vasilis Syrgkanis · Victor Lei · Miruna Oprescu · Maggie Hei · Keith Battocchi · Greg Lewis -
2019 Spotlight: Machine Learning Estimation of Heterogeneous Treatment Effects with Instruments »
Vasilis Syrgkanis · Victor Lei · Miruna Oprescu · Maggie Hei · Keith Battocchi · Greg Lewis -
2018 Workshop: Smooth Games Optimization and Machine Learning »
Simon Lacoste-Julien · Ioannis Mitliagkas · Gauthier Gidel · Vasilis Syrgkanis · Eva Tardos · Leon Bottou · Sebastian Nowozin -
2017 Workshop: Learning in the Presence of Strategic Behavior »
Nika Haghtalab · Yishay Mansour · Tim Roughgarden · Vasilis Syrgkanis · Jennifer Wortman Vaughan -
2017 Poster: Welfare Guarantees from Data »
Darrell Hoy · Denis Nekipelov · Vasilis Syrgkanis -
2017 Poster: Robust Optimization for Non-Convex Objectives »
Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis -
2017 Oral: Robust Optimization for Non-Convex Objectives »
Robert S Chen · Brendan Lucier · Yaron Singer · Vasilis Syrgkanis -
2016 Poster: Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits »
Vasilis Syrgkanis · Haipeng Luo · Akshay Krishnamurthy · Robert Schapire -
2015 Poster: No-Regret Learning in Bayesian Games »
Jason Hartline · Vasilis Syrgkanis · Eva Tardos -
2015 Poster: Fast Convergence of Regularized Learning in Games »
Vasilis Syrgkanis · Alekh Agarwal · Haipeng Luo · Robert Schapire -
2015 Oral: Fast Convergence of Regularized Learning in Games »
Vasilis Syrgkanis · Alekh Agarwal · Haipeng Luo · Robert Schapire