Blackwell Approachability meets Regret Minimization in the Dual
Jacob Abernethy
Berkelely, Department of Computer Science
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.