8803 Connections between Learning, Game Theory, and
Optimization, Fall 2010
Learning, Game Theory, and
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 here
Office hours: Just stop by my office or make an appointment.
Lecture Notes & Handouts
- 08/24: Introduction.
- 08/26: Online
Learning, Combining Experts Advice, and Regret Minimization. The
Weighted Majority Algorithm.
See also: An
Online learning survey by A. Blum. The
Weighted Majority paper by N. Littlestone and M. Warmuth.
Experts Learning and The Minimax Theorem for Zero-Sum Games.
See also: Game
Theory, On-line Prediction and Boosting by Y. Freund and R.
Schapire. COLT 1996.
A generic conversion from algorithms with good external regret
guarantees to algorithms with good swap regret guarantees.
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.
Strategies by R. Lipton, E. Markakis, and
A. Mehta, EC 2003.
- 09/14: Approximate Nash Equilibria in Stable Games.
Games. by P. Awasthi, M. F.
Balcan, A. Blum, O. Sheffet, and Santosh Vempala, SAGT 2010.
- 09/16: Passive
supervised learning in a distributional setting
with feature information. The realizable case.
- 09/21: Passive
supervised learning. Sample complexity results for the non-realizable
Sample complexity results for infinite hypothesis spaces.
- 09/28: Adaboost.
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 of Stability.
See chapters 17, 18, 19 of the Algorthmic Game Theory book.
- 10/07: Price
Anarchy in Unsplitable Linear Congestion Games.
See also: The
Price of Routing Unsplittable Flow by B. Awerbuch, Y. Azzar, and A.
Epstein, STOC 2005.
See also: Improved
Advertising by M.F. Balcan, A. Blum,
and Y. Mansour, SODA 2009.
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.
Mechanism Design (cont'd). See
Introduction to Mechanism Design (for Computer Scientists) by N.
- 10/26: Welfare
Maximization in Combinatorial Auctions with
Single Minded Bidders. See
Combinatorial Auctions by L. Blumrosen and N. Nisan.
- 10/28: Mechanism
Design 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
Pricing. by M.F. Balcan and
A.Blum. TOC 2007.
- 11/09: Online
Learning for Online Pricing Problems.
See also: Online
in Online Auctions by A.Blum, V. Kumar, A. Rudra, and F.
Wu. SODA 2003; Near-Optimal
Auctions by A.Blum and J. Hartline, SODA 2005.
See also: The
nonstochastic multiarmed bandit problem. by P. Auer, N.
Cesa-Bianchi, Y. Freund, and R. Schapire. SICOMP 2002.
- 11/11: Matroid
On the Impact of Combinatorial Structure on Congestion Games.
by H. Ackermann, H. Röglin, and B. Vöcking, Journal of the ACM, 2008.
Lecture notes on Matroid Optimization.
by M. Goemans.
- 11/16: Submodular
Learning Submodular Functions
by M. F. Balcan and N. Harvey.
- 11/18: Students presentations.
& 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: