8803 Connections between Learning, Game Theory,
and Optimization, Fall 2010
Learning, Game Theory, and Optimization
Time: Tues/Thurs 4:35-5:55, Place:
Instr Center 117.
Course description: Over the past 10 years, researchers have
discovered a number of important and deep connections between
machine learning theory, algorithmic game theory, and combinatorial
optimization. This course will explore these connections, discussing
fundamental topics in each area and how ideas from each area can
shed light on the others. You can find more info
Office hours: Just stop by my office or make an
Lecture Notes & Handouts
- 08/24: Introduction.
Online Learning, Combining Experts Advice, and Regret
Minimization. The Weighted Majority Algorithm.
See also: An
learning survey by A. Blum. The original Weighted
Majority paper by N. Littlestone and M. Warmuth.
Experts Learning and The Minimax Theorem for Zero-Sum Games.
See also: Game
On-line Prediction and Boosting by Y. Freund and R.
Schapire. COLT 1996.
- 09/02: A
generic conversion from algorithms with good external regret
guarantees to algorithms with good swap regret guarantees.
See also: From
External to Internal Regret by A. Blum and Y. Mansour,
COLT 2005, as well as chapter 4 of the Algorthmic Game Theory
Nash Equilibria in General-Sum Games.
- 09/09: Approximate Nash Equilibria in General Sum Games.
Large Games using Simple Strategies by R. Lipton, E.
Markakis, and A. Mehta, EC 2003.
- 09/14: Approximate Nash Equilibria in Stable Games.
Nash-Equilibria of Approximation-Stable Games. by P.
Awasthi, M. F. Balcan, A. Blum, O. Sheffet, and Santosh Vempala,
- 09/16: Passive
learning in a distributional setting with feature information.
The realizable case.
- 09/21: Passive
learning. Sample complexity results for the non-realizable
Sample complexity results for infinite hypothesis spaces.
- 09/28: Adaboost. See Rob
See also: a great 2007
NIPS tutorial by R. Schapire.
- 09/30: More on Boosting. Boosting and the Minimax Theorem.
Potential games. Congestion Games. Price of Anarchy and Price
See chapters 17, 18, 19 of the Algorthmic Game Theory book.
- 10/07: Price
in Unsplitable Linear Congestion Games.
See also: The
of Routing Unsplittable Flow by B. Awerbuch, Y. Azzar, and
A. Epstein, STOC 2005.
dynamics to good behavior.
See also: Improved
Equilibria via Public Service Advertising by M.F. Balcan,
A. Blum, and Y. Mansour, SODA 2009.
Weighted majority dynamics in congestion games.
Multiplicative updates outperform generic no-regret learning
in congestion games by R. Kleinberg, G. Piliouras, and É.
Tardos, STOC 2009.
- 10/14: Mechanism Design.
- 10/21: Mechanism Design (cont'd). See
Introduction to Mechanism Design (for Computer Scientists)
by N. Nisan.
- 10/26: Welfare
in Combinatorial Auctions with Single Minded Bidders. See
Combinatorial Auctions by L. Blumrosen and N. Nisan.
- 10/28: Mechanism
via Machine Learning.
Reducing Mechanism Design to Algorithm Design via Machine
Learning by M.F. Balcan, A. Blum, J. Hartline, and Y.
Mansour, JCSS 2008.
- 11/02: Mechanism Design via Machine Learning (cont'd).
- 11/04: Item
Pricing for Revenue Maximization in Combinatorial Auctions.
See also: Approximation
Algorithms and Online Mechanisms for Item Pricing. by M.F.
Balcan and A.Blum. TOC 2007.
- 11/09: Online
for Online Pricing Problems.
See also: Online
Online Auctions by A.Blum, V. Kumar, A. Rudra, and F. Wu.
SODA 2003; Near-Optimal
Online Auctions by A.Blum and J. Hartline, SODA 2005.
See also: The
multiarmed bandit problem. by P. Auer, N. Cesa-Bianchi,
Y. Freund, and R. Schapire. SICOMP 2002.
Matroid congestion games.
See also: On the
Impact of Combinatorial Structure on Congestion Games. by
H. Ackermann, H. Röglin, and B. Vöcking, Journal of the ACM,
Lecture notes on Matroid Optimization. by M. Goemans.
- 11/16: Submodular
functions and learning.
See also: Learning
Submodular Functions by M. F. Balcan and N. Harvey.
- 11/18: Students presentations.
Additional Readings & More Information
We will use a number of survery articles and tutorials. Students
may find the following (completely optional) textbooks useful for
exploring some of the topics that we cover in more depth: