Off-the-shelf Algorithmic Stability

on YouTube ↗54m

" summary

Bagging is shown to stabilize any black‑box learner by averaging models trained on random bags and yields provable epsilon‑delta stability where delta epsilon^2 scales with n and the per‑bag inclusion probability p; examples include CNNs, trees, and logistic regression across bag size regimes (m small, m proportional to n, or m≈n−√n). For classification, aggregating class weight vectors plus an inflated argmax returns small stable label sets; experiments on Fashion MNIST and SINDy model selection confirm stability while typically preserving accuracy, at the cost of extra compute.

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 1:29Algorithmic stability overview
3. 10:07Bagging for stability
4. 14:13Epsilon-delta stability guarantees
5. 22:57Bagging: bias vs accuracy
6. 30:48Stability in classification
7. 38:13Selection stability with argmax
8. 46:23Model selection trade-offs
9. 49:38Open questions
10. 50:22Q&A

" related talks

• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 41mGeneralization Bounds for Uniformly Stable AlgorithmsVitaly Feldman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 28mStability and Convergence Trade-Off of Iterative Optimization AlgorithmsBin Yu · Optimization, Statistics and Uncertainty
• 38mWhy giving your algorithm ALL THE FEATURES does not always workThomas Huijskens · PyData London 2018
• 27mPreventing Overfitting in Adaptive Data Analysis via StabilityThomas Steinke · Optimization, Statistics and Uncertainty
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 48mVariable Selection with Error Control: Another Look at Stability SelectionRichard Samworth · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity