From seed
(Redirected from OnlineLearning2014)
Jump to navigation Jump to search

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


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

Related past courses[edit]

  1. Freund Course 2006
  2. Chaudhuri Course 2011

Plan of classes[edit]

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

  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
  8. Adagrad / Joseph Perla
  9. Sequential investment and Universal Portfolios / Chaitanya Ryali
  10. Option Pricing through minimal regret meets black scholes in the limit / JiaPeng Zhang.
  11. Online Learning over Graphs / Shuang Song
  12. Boosting and Information Geometry / Yuncong Chen
  13. Online lossy compression / Matt Elkherj

Student Presentations List

Papers for presentations[edit]

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:

  1. Any chapter from one of the books above which has not been covered in class.
  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. Multiple arms bandit / Auer, Cesa-Bianchi, Schapire, Freund
  5. Contextualized multiple arm bandit / Auer ...
  6. Particle filters using Normal-Hedge.
  7. Predicting a binary sequence almost as well as the optimal biased coin / Yoav Freund
  8. Tracking a Small Set of Experts by Mixing Past Posteriors / Olivier Bousquet and Manfred K. Warmuth
  9. Sub-gradient online algorithms / Singer?
  10. Blum and ... an application of online algorithm to network optimization.
  11. Putting Bayes To Sleep Wouter M. Koolen, Dimitri Adamskiy and Manfred K. Warmuth / NIPS 2013
  12. Predicting the labelings of a graph, Mark Hebster:


  1. Probability theory without measure (overview of book by Vovk and Shafer)
  2. Stochastic Gradient Descent
  3. Minimax theorem, Online learning Boosting and Correlated Equilibrium
  4. NormalHedge
  5. Follow the leader algorithms.