Robustness, Stochastics, Uncertainty 1
summary
Shows that finite-sample learning guarantees come from concrete optimization tools: Blackwell approachability gives a randomized strategy that matches the empirical majority benchmark for arbitrary bit sequences; uniform convergence is controlled by empirical Rademacher complexity (e.g. L2 gives O(1/√n), L1 gives O(√(log d / n)); nuclear‑norm matrix completion needs O(R·p / n) samples under iid sampling but fails in spiky worst cases); and plain stochastic gradient descent with Polyak averaging attains the same O(1/√n) generalization rate.
AI-written summary · about
chapters (8)
- 0:00Start
- 1:34Learning as Optimization
- 13:08Outline
- 13:49Example: Linear Prediction
- 21:22Statistical Learning
- 38:38Performance of ERM
- 45:02A few more details about
- 56:35Performance of SGD
related talks
42mWhat (Doesn't) Make Learning Algorithms Generalize?
58mFirst-Order Stochastic Optimization
01h 18mOptimization I
01h 03mOverview of Statistical Learning Theory Part 2
53mDesigning Robust Learners
01h 06mAnalytic Methods for Supervised Learning III
34mDistributional Robustness, Learning, and Empirical Likelihood
22mPanel Discussion