Outline

Motivation

Decision Theory: Review

Sequential Loss Evaluation

Worst Case Analysis and No Free Lunch Theorems

Regret Analysis

Interpretation of Regret

Example 1: Prediction with Expert Advice

Example 2: Online Regression

Algorithms

Realizable Case

Analysis of Majority Vote

Non-realizable Case

Randomized Weighted Majority

Claude Shannon’s Mind-Reading Machine

Mind-reading machine, MIT museum, Photo: Poundstone (2014)

Hedge

Hedge: Applications

General Purpose Methods: Online Convex Optimization

Conclusions

References