A Necessary and Sufficient Stability Notion for Adaptive Generalization
summary
Defines local statistical stability (LSS) as average total-variation between prior and posterior over a sampled point and proves LSS is both necessary and sufficient for adaptive generalization assuming sample accuracy. Shows LSS composes under post-processing and adaptive composition, reproduces the VNSSS-style monitor that runs the mechanism T ≈ 1/Δ times to amplify failures, and constructs an overfitting query to prove necessity. Gives a separation example versus max-information and lists open problems about tighter composition and removing the sample-accuracy assumption.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 2:02Problem setting
- 5:40General notation
- 9:18Stability definitions
- 12:23Formal stability loss
- 17:47Local statistical stability
- 22:06Adaptive composition
- 28:35Generalization guarantees
- 33:01Necessity of the definition
- 35:31Conclusion and future work
- 39:10Q&A session
related talks
59mCompositional Properties of Statistical Procedures: An Information-Theoretic View
27mPreventing Overfitting in Adaptive Data Analysis via Stability
01h 03mOverview of Statistical Learning Theory Part 2
42mWhat (Doesn't) Make Learning Algorithms Generalize?
58mFirst-Order Stochastic Optimization
34mAlgorithmic Stability for Interactive Data Analysis
53mDesigning Robust Learners
41mGeneralization Bounds for Uniformly Stable Algorithms