# OnlineLearning2015

(Redirected from OnlineLearning2014)

This is a course on online learning algorithms and related topics in finance, Game theory and information theory.

**Instructor:**Prof. Yoav Freund**Location:**Room 4109**Time:**Tuesdays and Thursdays 10am to 11:30am

## Contents

## Books

- Prediction, Learning and Games / Cesa Binachi and Lugosi
- Probability and Finance, It's only a game / Vovk and Shafer
- Boosting, Foundations and Algorithms / Schapire and Freund (Chapters 6,7,8)
- Options, Futures, and other Derivatives / John C. Hull. (Chapter 12: Binomial trees).

## Related past courses

## Plan of classes

- 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 <math>\beta</math>'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

## 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 February 4, 2014.

Possible papers include:

- Any chapter from one of the books above which has not been covered in class.
- 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
- Multiple arms bandit / Auer, Cesa-Bianchi, Schapire, Freund
- Contextualized multiple arm bandit / Auer ...
- Particle filters using Normal-Hedge.
- 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
- Sub-gradient online algorithms / Singer?
- Blum and ... an application of online algorithm to network optimization.
- Putting Bayes To Sleep Wouter M. Koolen, Dimitri Adamskiy and Manfred K. Warmuth / NIPS 2013
- Predicting the labelings of a graph, Mark Hebster: http://www0.cs.ucl.ac.uk/staff/M.Herbster/pubs/index.html

## Other

- Probability theory without measure (overview of book by Vovk and Shafer)
- Stochastic Gradient Descent
- 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.