[AI Seminar] Fwd: AI Lunch -- Christian Kroer -- December 6

[Ellen Vitercik]

This is a reminder that this talk is tomorrow, Tuesday, December 6th, at
noon in NSH 3305. Also, we have recently uploaded Andrew Moore's great talk
from November 15th to the new AI lunch Youtube channel. We intend to update
the channel regularly from here on out. See the talk here
<https://www.youtube.com/watch?v=2cEUKKJoAdU>.

---------- Forwarded message ----------
From: Ellen Vitercik <vitercik at cs.cmu.edu>
Date: Thu, Dec 1, 2016 at 8:58 AM
Subject: AI Lunch -- Christian Kroer -- December 6
To: ai-seminar-announce at cs.cmu.edu, Christian Kroer <chrkroer at gmail.com>


Dear faculty and students,

We look forward to seeing you this Tuesday, December 6th, at noon in NSH
3305 for AI lunch. To learn more about the seminar and lunch, please visit
the AI Lunch webpage <http://www.cs.cmu.edu/~aiseminar/>.

On Tuesday, Christian Kroer <http://www.cs.cmu.edu/~ckroer/> will give a
talk titled "First-Order Methods for Extensive-Form Game Solving."

*Abstract:* We study the problem of computing a Nash equilibrium in
large-scale two-player zero-sum extensive-form games. While this problem
can be solved in polynomial time, sparse iterative methods, in particular
regret- based methods and first-order methods (FOMs), are much cheaper and
effective and hence usually preferred for large games. Thus far,
regret-based methods have largely been favored in practice in spite of
their theoretically inferior convergence rates. In this talk we investigate
the acceleration of FOMs both theoretically and numerically.

The convergence rates of FOMs depend heavily on the properties of the
distance-generating function (DGF) that they are based on. We investigate
the acceleration of FOMs for solving extensive-form games through a better
design of the dilated entropy function--a class of DGFs related to the
domains associated with the extensive-form games--and suggesting new
sampling schemes for stochastic FOMs. Our new weighting scheme for the
dilated entropy function establishes the first bound on the
strong-convexity parameter for DGFs over general treeplexes, i.e., the
strategy spaces of general sequential games, and it has no dependence on
the branching factor of the player. Thus, we establish first explicit FOM
convergence rates for general treeplexes, and significantly improve upon
previous results given only for some special cases. Building on this
result, we also introduce a class of gradient estimators which, along with
our DGF, leads to the first stochastic FOM for extensive-form games.

Experimentally, we investigate the performance of three FOMs (the excessive
gap technique, mirror prox, and stochastic mirror prox) and compare their
performance to the regret-based algorithms. Equipped with our
distance-generating function, we find that mirror prox and the excessive
gap technique outperform the prior regret-based methods for finding medium
accuracy solutions.

Joint work with Kevin Waugh, Fatma Kilinc-Karzan, and Tuomas Sandholm.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.srv.cs.cmu.edu/pipermail/ai-seminar-announce/attachments/20161205/b8d86490/attachment.html>