Blackwell Approachability meets Regret Minimization in the Dual

**Jacob Abernethy **

Berkelely, Department of Computer Science**
**

**M****onday August 23, 2010 **

2:00 PM,
5126 Upson Hall

__Abstract:__

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.