Protocol | Main constraint on algorithm design |

Success Measure | sometimes impossible to practically measure. May serve as a guide for designing algorithms |

Type of Analysis | what we want to prove |

Data generation mechanism | Only relevant for the analysis, not for designing an algorithm |

Further Restrictive Assumptions | used for designing algorithms or proving restricted results |

- Off-line supervised learning: training pairs are given, the goal is to produce a

model that predicts well

- Semi-supervised: training pairs and unlabeled data are given, the goal

is to produce a model that predicts well

- Transductive: training pairs and unlabeled data are given, the goal is

to predict well on the unlabeled examples

- On-line: repeated transductive learning (one new example

at a time, prediction to be performed at each step)

- Variants of on-line: actions instead of predictions (e.g.

reinforcement learning)

Predictor receives x, takes an action y, and gets reward r.

It is possible to combine r with x.

A prediction function takes a history of pairs ((x,r), y) and a new x to predict y.

Name | X | Y |

Fixed design | fixed | iid |

Random design | iid | iid |

Sequence prediction | fixed | worst-case |

Online learning | worst-case | worst-case |

Online compression | fixed | iid |