Outline

Unlike standard statistical approaches to algorithmic forecasting, prediction of individual sequences does not impose any probabilistic assumption on the data-generating mechanism. Yet, prediction algorithms can be constructed that work well for all possible sequences, in the sense that their performance is always nearly as good as the best forecasting strategy in a given reference class. In this course we will introduce a general model for sequential prediction and define some basic deterministic and randomized prediction strategies for various settings, including multiarmed bandit problems, game playing, sequential investment, and online convex optimization.

Syllabus

• Prediction with expert advice

• Multiarmed bandits

• Prediction and playing games

• Sequential investment

• Online convex optimization

In order to pass the exam you have to write a research note summarizing on one or more papers. Your note will typically be 10 page long and will include:

• motivation and explanation of the problem,
• rigorous illustration of the most important results (including the formal definitions necessary to understand the results),
• at least one significant proof carried out in detail,
• description of previous and follow-up results (use Google Scholar to track down follow-up results),
• a final section mentioning what are, in your opinion, strengths and weaknesses of the results' contributions.

You can also propose a paper you are interested in. In any case, contact me before starting.

News

• The course is scheduled to start on September 19, 2011.

Course calendar

Click on calendar entries to see the topics covered in each class.