Speaker: Yu-Xiang Wang

Abstract: I will continue the topic that Larry started two months ago on "Adaptive Data Analysis" and "Reuseable Holdout". Specifically, I will talk about ideas in:

- "Algorithmic Stability for Adaptive Data Analysis" by Bassily, Nissim, SMith, Steinke, Stemmer and Ullman.
- "Controlling Bias in Adaptive Data Analysis Using Information Theory" by Russo and Zou.

I will not be following the exact sequence of presentation in these papers, but rather use a top-down approach to first give a precise formulation of the problem in terms of a sequence of expectations, then provide an upper bound by explicitly working out the adversarial case, which nicely matches the results in Russo and Zou that uses mutual information. Hopefully, this new presentation will make the concept much clearer. This approach leads to several directions how one can relax the assumptions in existing TCS approaches of adaptive data analysis that often relies on uniform boundedness of the query's sensitivity.