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 29, VP] The prophet inequality problem.
3. [Oct 5, VP] The prophet inequality problem.
4. [Oct 12, CD] The secretary problem. Scheduling in the Random-Order Model
5. [Oct 19, CD] Online Matching.
6. [Oct 26, VP] Primal-Dual framework.
7. [Nov 2, CD] Convex body chasing
8. [Nov 9, VP] Tree metric and Metrical Task Systems.

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.

(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.