Algorithmic Stability for Interactive Data Analysis

on YouTube ↗34m

" summary

Interactive reuse of data causes severe overfitting: naive empirical answers let an adaptive procedure reach correlation about √D/√N (even perfect when D > N). Stability measured as distributional stability (inspired by differential privacy) prevents that by limiting information leaked about the sample. Practical remedy: answer statistical queries by adding noise (e.g. add Gaussian noise to empirical estimates) and get improved accuracy roughly error O(K^{1/4}/√N) instead of √K/√N. Remaining limits: dependence on ambient dimension D and worst-case computational barriers via fingerprinting-code attacks.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:48Statistical Theory: One-Way Streets
3. 2:04Statistical Practice: Traffic Circles
4. 2:57Examples of Interaction
5. 4:48Possible Approaches
6. 8:23Overfitting in Interactive Data Analysis
7. 13:07How to Avoid This Trap?
8. 14:51Output Stability
9. 16:19Distributional Stability (aka Privacy)
10. 18:55A General Framework
11. 21:11Example: Statistical Queries (SQs)
12. 22:03The Empirical Estimator
13. 23:19An Improved Estimator
14. 24:37Proof Overview
15. 29:10Summary of Results

" related talks

• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 01h 04mAlgorithmic High Dimensional Robust Statistics IIIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 01h 14mStatistical Inference and Privacy, Part IIIRachel Cummings, Sesa Slavkovic · Data Privacy: Foundations and Applications Boot Camp
• 01h 00mAlgorithmic High Dimensional Robust Statistics IIlias Diakonikolas · Foundations of Data Science Boot Camp 2018
• 01h 30mHigh-Dimensional Statistics IMartin Wainwright · Big Data Boot Camp 2013
• 48mComputational-Statistical Tradeoffs in Robust High-Dimensional EstimationIlias Diakonikolas · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 00mDifferential Privacy And The Complexity Of Simple QueriesJonathan Ullman · Rigorous Evidence for Information-Computation Trade-offs
• 43mIs Interaction Necessary for Distributed Private Learning?Abhradeep Guha Thakurta · Privacy and the Science of Data Analysis 2019