Generalization Bounds for Uniformly Stable Algorithms

on YouTube ↗41m

" summary

Shows a new high‑probability generalization bound for uniformly stable algorithms that replaces the prior γ·√n blowup with a bound that scales like √(γ + 1/n) (so for typical γ ≈ 1/√n it yields meaningful 1/√n rates). Proof stabilizes the maximum via the exponential mechanism (soft‑max sampling), converts stability to concentration, and proves a tight second‑moment claim second moment ≤ γ^2 + 1/n giving a γ + 1/√n tail via Chebyshev. Applications include SGD, regularized ERM, and differentially private predictors.

AI-written summary · about

" chapters (16)

1. 0:00Intro
2. 0:56Uniform stability
3. 2:54Generalization error
4. 4:45Stochastic convex optimization
5. 9:24Stable optimization
6. 12:31Generalization bounds
7. 15:27Comparison
8. 16:08Second moment
9. 18:26Implications
10. 22:59Data-dependent functions
11. 24:55Generalization in expectation
12. 27:32Concentration via McDiarmid For all neighboring 5,5
13. 29:33Proof technique
14. 34:12Stablo max
15. 37:44Game over
16. 39:14Conclusions

" related talks

• 01h 17mGeneralization IPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 42mWhat (Doesn't) Make Learning Algorithms Generalize?Roi Livni · Lower Bounds, Learning, and Average-Case Complexity
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 28mStability and Convergence Trade-Off of Iterative Optimization AlgorithmsBin Yu · Optimization, Statistics and Uncertainty
• 53mDesigning Robust LearnersJacob Steinhardt · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 01h 18mGeneralization IIIPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 01h 23mGeneralization IIPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019