SPEAKER: Andrew Gilpin 

TIME: Wednesday 12-1pm, February 28, 2007

PLACE: NSH 1507

TITLE: Nesterov's excessive gap technique and poker

ABSTRACT:
For the generic convex optimization problem of minimizing a
(non-smooth) convex function f(x) over a convex domain D, any
subgradient method requires O(1/epsilon^2) iterations for obtaining an
epsilon-solution. However, this analysis is based on a black-box
oracle access model for f and D. Recently, Nesterov developed the
excessive gap technique which yields an algorithm needing only
O(1/epsilon) iterations to obtain an epsilon-solution in certain
problems having a non-smooth convex objective with a certain max-like
structure.

In this talk I will present the general theory behind Nesterov's
excessive gap technique, and I will describe how we extended the basic
framework to handle the problem of computing approximate Nash
equilibria in two-person zero-sum sequential games of imperfect
information. Also, I will discuss some additional heuristics we
developed which yield even faster convergence in practice.

Finally, I will describe how we used this algorithm (along with our
recent advances in automated abstraction for sequential games of
imperfect information) to develop an extremely competitive heads-up
Texas Hold'em poker player.

This talk describes joint work with Samid Hoda, Javier Pena, Tuomas
Sandholm, and Troels Sorensen.