Preventing Overfitting in Adaptive Data Analysis via Stability
summary
Claims that adaptive answers can have distribution-dependent accuracy that scales with each query's variance rather than worst-case range, and gives algorithms that achieve that. Core algorithm splits data into T-sized blocks and returns a median-of-means computed via a differentially private approximate median; a much simpler option adds Gaussian noise scaled to the empirical variance. Analysis uses average leave-one-out KL stability (composes adaptively) and mutual information bounds to prove generalization, yielding roughly √K savings in sample complexity versus fresh samples per query.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:29This talk versus previous talk
- 1:19Modelling Adaptivity
- 2:25Accuracy?
- 3:44Results
- 7:22Techniques
- 11:40Approximate Median Algorithm
- 12:53Our Algorithm
- 13:23Extensions
- 15:48Previous Algorithm
- 16:20Simple distribution-dependent algorithm
- 21:27Average stability and generalization
- 24:52Scaled noise: key points
related talks
43mIs Interaction Necessary for Distributed Private Learning?
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration
46mA Necessary and Sufficient Stability Notion for Adaptive Generalization
53mDesigning Robust Learners
17mData privacy and reliable learning
47mNot all data are created Equal: Robust Mean Estimation from Heterogeneous and Unreliable Users
01h 02mLarge-Scale Private Learning, Part I
54mOff-the-shelf Algorithmic Stability