Blackwell Approachability meets Regret Minimization in the Dual



Jacob Abernethy
Berkelely, Department of Computer Science

Monday August 23, 2010
2:00 PM,
5126 Upson Hall



A result from the 1950's, Blackwell's Approachability Theorem, showed what was essentially a generalization of Von Neumann's minimax theorem for multi-dimensional payoffs. More recently, there has been a lot of work on constructing what are known as "no-regret algorithms", which provide a strong guarantee when optimizing an arbitrary sequence of convex functions. I'll show that two results, "existence of no-regret algorithms" and "Blackwell approachability", are essentially the same, each proving a convex dual version of the other. Using this equivalence we'll derive the first efficient algorithm for calibration, and prove a conjecture of Lehrer about approachability in Hilbert spaces.

Joint work with Peter Bartlett and Elad Hazan.