In many settings such as routing calls in a network, scheduling jobs in processors, or even trading in the stock market, the decision-maker operates in a status of uncertainty. The objective of the course is to study algorithmic models, techniques, analyses, and approaches that have been developed specifically for dealing with this class of problems. The course is will be focused on the following specific aspects of computation under uncertainty:

1. Online algorithms, in which the input is not known ahead of time;
2. Regret minimization and online optimization in machine learning; and
3. Recently introduced frameworks such as algorithms with predictions, and algorithms with explorable uncertainty.

The course will focus on the analytical/theoretical analysis of algorithms with uncertainty, but also on concrete applications.

• Spyros Angelopoulos (CNRS and International Laboratory on Learning Systems, Montreal, course supervisor)
• Christoph Dürr, CNRS and Sorbonne U.
• Vianney Perchet, ENSAE Paris
• Adi Rosén, CNRS and U. of Paris

Language: English by default

The following is a list of courses related to the topics of Algorithms and Uncertainty. (To be updated)

1. [Sep 21, CD] One max search. Linear search. Online bidding. Consistency-Robustness tradeoff.
2. [Sep 28, VP] The secretary problem.
3. [Oct 5, VP] The prophet inequality problem.
4. [Oct 12, CD] Online matching.
5. [Oct 19, CD] Paging, k-server.
6. [Oct 26, VP] Tree metric and Metrical Task Systems.
7. [Nov 2, VP] Primal-Dual framework.
8. [Nov 9, CD] Convex body chasing

Grading scheme: 100% from the final exam, and 0% from weekly homeworks.

EXAM INFORMATION

• Personal lecture notes are allowed. But not books or printed articles.

We will propose internships early in the course. We urge all students who are interested to talk to the instructors as soon as possible. The internships will be related to the topics of research of the instructors and the lectures given in the course, or, more broadly, to the research interests of the instructors.

• [BEY] Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press 1998.
• Lecture Notes which you can all freely edit

(to be updated)

• Nikhil Bansal's course on “Algorithms and Uncertainty” at TU Eindhoven.
• Kamesh Munagala’s course on “Optimization and Decision Making under Uncertainty” at Duke University.
• Sebastien Bubeck’s and James Lee’s course on “Competitive analysis via Convex Optimization” at the University of Washington.
• Allan Borodin’s course on “Online Algorithms and Other Myopic Algorithms” at the University of Toronto.
• Nicole Megow’s course on “Algorithms and Uncertainty” at the University of Bremen.