# OnlineLearning2018

## Contents

## Online learning, boosting and Games

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

## Plan of Classes

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

### Student Lectures

**Games and Hard-Core Sets**

## Books

- Prediction, Learning and Games / Cesa Binachi and Lugosi
- Online Convex Optimization / Elad Hazan
- Boosting, Foundations and Algorithms / Schapire and Freund (Chapters 6,7,8)
- Probability and Finance, It's only a game / Vovk and Shafer
- 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**

- 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.
- Universal Portfolios With and Without Transaction Costs / Adam Kalai and Avrim Blum
- Minimax Option Pricing Meets Black-Scholes in the Limit / Jacob Abernethy, Rafael M. Frongillo, Andre Wibisono
- Gambling in a rigged Casino, the adversarial multiple arm bandits / Auer, Cesa-Bianchi, Schapire, Freund
- Predicting a binary sequence almost as well as the optimal biased coin / Yoav Freund
- Tracking a Small Set of Experts by Mixing Past Posteriors / Olivier Bousquet and Manfred K. Warmuth
- Routing Without Regret: On Convergence to Nash Equilibria of Regret-Minimizing Algorithms in Routing Games / Avrim Blum, Eyal Even-Dar, and Katrina Ligett
- Putting Bayes To Sleep Wouter M. Koolen, Dimitri Adamskiy and Manfred K. Warmuth / NIPS 2013

## Other

- Adaptive Subgradient Methods for Online Learning and Stochastic Optimization / John Duchi, Elad Hazan and Yoram Singer

- Minimax theorem, Online learning Boosting and Correlated Equilibrium
- Relevant paper: Adaptive game playing using multiplicative weights Yoav Freund and Robert E. Schapire. / Games and Economic Behavior, 29:79--103, 1999.
- From Internal to External Regret / A. Blum, Y. Mansour, and R. Meir

- NormalHedge
- Relevant paper: A parameter-free hedging algorithm Chaudhuri, Freund, Hsu. NIPS 2009.
- Relevant paper: normalhedge in continuous time.

- Follow the leader algorithms.

## Related past courses

## Material from Previous Years

- Introduction to online learning and it's applications
- Hedge
- Relevant paper: the first part of A decision-theoretic generalization of online learning and an application to boosting

- Arithmetic coding, Log loss, Universal source coding and the Online Bayes algorithm, some more slides
- Compression and Arithmetic coding: On Wikipedia, Chapter 6 from David Mackay's book, Information Theory, Inference, and Learning Algorithms

- Talk4: The KT and Laplace prediction algorithm and The context algorithm, The context algorithm using
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://yoavfreund.miraheze.org/api/rest_v1/":): {\displaystyle \beta}**'s- Predicting a binary sequence almost as well as the optimal biased coin Freund 1996.
- web site devoted to work on the context weighting algorithm Willems, Starkov, Tjalkens 1995.

- Online learning, Bregman divergences.
- Mixable Losses and Switching experts
- Reading: in Prediction, Learning and Games / Cesa Binachi and Lugosi.
**Mixability:**Sections 3.5 - 3.8,**Switching experts:**Section 5.2

- Reading: in Prediction, Learning and Games / Cesa Binachi and Lugosi.
- Sleeping Experts and Applications
- Using and combining predictors that specialize / Yoav Freund, Robert E. Schapire, Yoram Singer and Manfred K. Warmuth.
- Tracking a Small Set of Experts by Mixing Past Posteriors Olivier Bousquet and Manfred Warmuth
- Context-sensitive learning methods for text categorization William W. Cohen & Yoram Singer (1999)
- Putting Bayes to sleep Wouter M. Koolen, Dimitri Adamskiy and Manfred K. Warmuth (NIPS12)

- Boosting and Repeated Matrix Games (Boosting book, chapter 6)
- Boosting and Information Geometry (Boosting book Chapter 8)
- Drifting games and binomial weights
- On-line prediction and conversion strategies / Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, and Manfred K. Warmuth / Machine Learning, 25:71--110, 1996.
- Boosting a weak learning algorithm by majority / Yoav Freund, Information and Computation, 121(2):256--285, 1995.
- Drifting games / Robert E. Schapire. Machine Learning, 43(3):265-291, 2001.
- Drifting games and Brownian motion / Yoav Freund and Manfred Opper. Journal of Computer and System Sciences, 64:113--132, 2002.
- Brownboost paper
- Normal-Hedge paper.

## Student Lectures

- Online Learning and Online Convex Optimization Shai-Shalev Shwartz / Stefanos Poulis
- Transforming online algorithms to batch / Chicheng Zhang
- Probability without Measure / Mark Sarufim
- Linear Pattern Recognition / David Lisuk
- Prediction, repeated games and Equilibria / Vineel Pratap
- Blackwell Approachability and online learning / Akshay Balsubramany
- ￼￼Pegasos: Primal Estimated sub-Gradient Solver for SVM / Zhimo Shen
- Adagrad / Joseph Perla
- Sequential investment and Universal Portfolios / Chaitanya Ryali
- Option Pricing through minimal regret meets black scholes in the limit / JiaPeng Zhang.
- Online Learning over Graphs / Shuang Song
- Boosting and Information Geometry / Yuncong Chen
- Online lossy compression / Matt Elkherj