Compositional Properties of Statistical Procedures: An Information-Theoretic View

on YouTube ↗59m

" summary

Argues that mutual information and KL chain rules explain linear degradation under adaptive composition but fail for deterministic estimators (mutual information can be infinite), so stability uses erasure mutual information and, crucially, Wasserstein stability and transportation inequalities. Derives concrete bounds: Gibbs gives ~beta/N stability, SGD approximates ERM with extra error O(1/sqrt(T)) (so total O(1/N + 1/sqrt(T)); under strong convexity synchronous coupling yields contraction and stability essentially O(1/N). Uses Dobrushin comparison, couplings, and Markov-chain viewpoints; MCMC analysis is suggested but not completed.

AI-written summary · about

" chapters (6)

1. 0:00Introduction to statistical decision procedures
2. 17:37Stability and information theoretic measures
3. 26:12Geometric approach to stability and Wasserstein distance
4. 35:13Analyzing stochastic gradient descent stability
5. 44:15The de Bruijn comparison theorem for composition
6. 52:52Detailed SGD analysis and conclusion

" related talks

• 31mStrong Data Processing Inequalities and Estimation with ConstraintsJohn Duchi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 46mA Necessary and Sufficient Stability Notion for Adaptive GeneralizationMoshe Shenfeld · Privacy and the Science of Data Analysis 2019
• 01h 15mAn overview of classical robust statistics and generalizations to the futurePo-Ling Loh · Modern Paradigms in Generalization Boot Camp 2024
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 28mData Driven Convergence in Statistical EstimatorsNarayana Santhanam · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 12mIterative Methods and High-Dimensional StatisticsKevin Tian · Meet the Fellows Welcome Event