Blackwell’s Approachability Theorem

on YouTube ↗57m

" summary

Blackwell’s approachability theorem gives a concrete claim: if each stage’s vector outcome has expected inner product ≤0 with the outward normal at the average’s nearest point to a convex target set, then the running average converges into that set even without IID assumptions, by a semi‑martingale argument. The proof yields a randomized stagewise strategy and an explicit algorithm. Consequences include Hannan no‑regret, no internal regret, constructive calibration for any countable checking rules, and links to Blackwell‑Dubins merging of opinions.

AI-written summary · about

" chapters (13)

1. 0:00Start
2. 0:55The Copenhagen Principle
3. 5:28The Legacy of David Blackwell
4. 20:24David Harrell Blackwell
5. 25:26About David Blackwell
6. 29:01On Merging of Opinions
7. 30:44Misspecified Priors
8. 31:16The Approachability Theorem
9. 36:36Approachability Theorem
10. 46:39Internal Regret
11. 48:22Measuring the Accuracy of My Forecast
12. 49:39The Checking Rule
13. 50:20Naive Calibration

" related talks

• 33mA Few Connections Between Optimization and ProbabilitySasha Rakhlin · Optimization, Statistics and Uncertainty
• 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
• 09mConvex Programs, Computational Phase Transitions, and Robust AlgorithmsSam Hopkins · Meet the Fellows Welcome Event
• 48mA Simple Condition for Constant Regret in Online Decision-MakingDaniel Freund · Matching and Objectives
• 49mAnalysis of Algorithms on Dense Matrices using Approximate Message PassingAndrea Montanari · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 00mMin-Max Optimization from a Dynamical Systems ViewpointPanayotis Mertikopoulos · Adversarial Approaches in Machine Learning 2022
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013