Advanced Topics:

Algorithmic game Theory and Machine Learning

Tentative Schedule:

Lecture 1: Oct 31, 2011

Introduction. Regret Minimization, Online Convex Optimization. Regularized Follow The Leader Prime- Dual using Berman Divergence

source: Elad Hazan, The convex optimization approach to regret minimization (sections 1.2 and 1.3)

Lecture Notes

Lecture 2: Nov 5, 2011

Stochastic sub-gradient decent

Logarithmic regret for strict convex function

sources:

Boyd, Xiao and Mutapcic, Subgradient Methods also here

Shai Shalev Shwatz, Class notes, lecture 6

Lecture Notes

Lecture 3.

Regret in Large Action spaces.

sources:

A. Kalai and S. Vempala, Efficient algorithms for online decision problems

S. Kakade, A. Kalai and K. Ligett, Playing Games with Approximation Algorithms

Lecture Notes

Lecture 4.

Multi-Arm Bandit,

Adversarial Model,

P. Auer, N. Cesa-Bianchi, Y. Freund and R. E. Schapire, The Nonstochastic Multi-Armed Bandit Problem (Section 3 and 7)

Lecture Notes

Lecture 5.

Lower Bound

Multi-Arm Bandit & Supervised learning (using KL-divergence)

P. Auer, N. Cesa-Bianchi, Y. Freund and R. E. Schapire, The Nonstochastic Multi-Armed Bandit Problem (section 5)

Lecture Notes

Lecture 6. Dec. 5, 2011

MAB Gradient Descent

Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan Online convex optimization in the bandit setting: gradient descent without a gradient

Oblivious versus Adaptive adversary

Varsha Dan and Thomas P. Hayes, How to Beat the Adaptive Multi-Armed Bandit(section 8)

Lecture Notes

Lecture 7. Dec. 12, 2011

Bayesian approach to MAB: Gittins index

J. Gittins, K. Glazerbrook and R. Weber, Multi-Arm Bandit Allocation Indices

John N. Tsitsiklis, A short proof of the Gittins index theorem

Lecture Notes

Lecture 8. Dec. 19, 2011

Information Cascading [sources]

Lecture Notes

Lecture 9. Dec. 26, 2011

Sponsored search optimization.

Nikhil Devanur Online Algorithms with Stochastic Input

Nikhil Devanur and Tom Hayes The Adwords Problem: Online Keyword Matching with Budgeted Bidders under Random Permutations

Lecture Notes

Lecture 10. Jan. 2, 2012

Market Equilibrium and Convex Programming

Combinatorial Algorithms for Market Equilibria, Vijai Vazirani, Chapter 5 sections 5.2 and 5.11 in Algorithmic Game Theory, editors: Nisan, Roughgarden, Tardos, and Vazirani.

A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities, Kamal Jain (Sections 3 and 5)

Lecture Notes

Lecture 11, Jan 9, 2012

Indivisible items and market equilibrium

Avinatan Hassidim, Haim Kaplan, Yishay Mansour and Noam Nisan, Non-Price Equilibria in Markets of Discrete Goods

Lecture 12, Jan 16, 2012

Uriel Feige, On Maximizing Welfare when Utility Functions are Subadditive

Lecture 13, Jan 23, 2012

Regret Minimization of Global Cost functions

Lecture 14, Jan 30, 2012

Nash Equilibrium and communication complexity

Home Work:

homework 1

homework 2

homework 3