Blackwell Approachability meets Regret Minimization in the Dual

演讲人: Jacob Abernethy UC Berkeley
时间: 2010-04-23 14:00-2010-04-23 15:00

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.