# OnlineLearning2018

## Online learning, boosting and Games

• Instructor: Prof. Yoav Freund
• Location: Room 4140
• Time: Tuesdays and Thursdays 9:30am - 10:50am

## Plan of Classes

2. Introduction halving, Hedge, Perceptron, Laplace law of succession.- - - - - - - (Handout)
3. The Hedge Algorithm - - - - - - - - (handout)
4. Compression of Individual sequences (Bayes algorithm)
5. Learning in repeated games - - - (handout, paper)
6. Repeated games, Boosting and information geometry- - - (handout, Rob's slides,Elementary proof of Chernoff,Hoeffding,Sanov,Sanov,boosting the margin)
7. Potential Functions and Blackwell condition
8. Convex potential functions, Dual Gradient algorithm, Bregman Divergences, Polynomial and Exponential potential functions
9. Drifting games - You can find pdf slides and papers here

### Student Lectures

1. Games and Hard-Core Sets

## Books

1. Prediction, Learning and Games / Cesa Binachi and Lugosi
2. Online Convex Optimization / Elad Hazan
3. Boosting, Foundations and Algorithms / Schapire and Freund (Chapters 6,7,8)
4. Probability and Finance, It's only a game / Vovk and Shafer
5. Options, Futures, and other Derivatives / John C. Hull. (Chapter 12: Binomial trees).

## Registration list

If you are interested in taking the class, please fill in your information in this google doc

## Papers for presentations

Students registered to the class have to present a paper. The presentation will be 45 minutes long and needs to cover a book chapter or a journal paper. Students need to decide which paper/chapter they want to present by January 18,2014.

Possible papers

1. Any chapter from one of the books above which has not been covered in class (It is possible to have two lectures on the same chapter, but in that case both lectures have to be scheduled for the same day.
2. Universal Portfolios With and Without Transaction Costs / Adam Kalai and Avrim Blum
3. Minimax Option Pricing Meets Black-Scholes in the Limit / Jacob Abernethy, Rafael M. Frongillo, Andre Wibisono
4. Gambling in a rigged Casino, the adversarial multiple arm bandits / Auer, Cesa-Bianchi, Schapire, Freund
5. Predicting a binary sequence almost as well as the optimal biased coin / Yoav Freund
6. Tracking a Small Set of Experts by Mixing Past Posteriors / Olivier Bousquet and Manfred K. Warmuth
7. Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games / Avrim Blum, Eyal Even-Dar, and Katrina Ligett
8. Putting Bayes To Sleep Wouter M. Koolen, Dimitri Adamskiy and Manfred K. Warmuth / NIPS 2013

## Other

1. Minimax theorem, Online learning Boosting and Correlated Equilibrium
2. NormalHedge

## Material from Previous Years

1. Introduction to online learning and it's applications
2. Hedge
3. Arithmetic coding, Log loss, Universal source coding and the Online Bayes algorithm, some more slides
4. Talk4: The KT and Laplace prediction algorithm and The context algorithm, The context algorithm using $\beta$'s
5. Online learning, Bregman divergences.
6. Mixable Losses and Switching experts
7. Sleeping Experts and Applications
8. Boosting and Repeated Matrix Games (Boosting book, chapter 6)
9. Boosting and Information Geometry (Boosting book Chapter 8)
10. Drifting games and binomial weights

## Student Lectures

1. Online Learning and Online Convex Optimization Shai-Shalev Shwartz / Stefanos Poulis
2. Transforming online algorithms to batch / Chicheng Zhang
3. Probability without Measure / Mark Sarufim
4. Linear Pattern Recognition / David Lisuk
5. Prediction, repeated games and Equilibria / Vineel Pratap
6. Blackwell Approachability and online learning / Akshay Balsubramany
7. ￼￼Pegasos: Primal Estimated sub-Gradient Solver for SVM / Zhimo Shen