Sidebar
MA-INF 1218: Algorithms and Uncertainty
Lecture
| When | Where | Start | Lecturer |
|---|---|---|---|
| Monday, 10:15-11:45 Wednesday, 12:15-13:45 | online | April 20 | Kesselheim |
Tutorials
Online Teaching
The lecture will start on April 20 as remote teaching. Please sign up to the eCampus course so that we can keep you posted. The recorded lectures are available on Sciebo. Please find the link in eCampus.
Exams
The exams will be oral, about 30 minutes long, and take place as a video conference via Zoom. You will need to show and identify yourself on camera. It does not matter whether it is a computer or a smartphone. No other hardware is required. If you would like to take the exam but not in this form as a video conference, please contact us.
The first period will take place from July 27 to 30. Please contact Alexander Braun to be assigned a time slot. Please also state your preference which of these days you like best and whether your exam should be in the morning or in the afternoon. Please do so by July 10. If you do not plan to take the exam in the first period, you can also be assigned a time slot for the second period already, which will start on August 31.
The second period will take place from August 31 to September 3. Please contact Alexander Braun before July 25 to be assigned a time slot. Again, you can also state your preference concerning which of these days you like best and whether your exam should be in the morning or in the afternoon.
One more thing: If you have been assigned a time slot but then decide to not take the exam, please remember to cancel it. It is very important for us to know that you will not show up because otherwise we will be waiting for you. In this case, send an e-mail to Thomas Kesselheim or Alexander Braun. Even a last-minute cancellation is better than a no-show. Of course, make sure that you also follow the official procedures (if applicable).
Content
In many application scenarios, algorithms have to make decisions under some kind of uncertainty. This affects different kinds of problems. For example, when planing a route, a navigation system should take into consideration the traffic. Also, any machine-learning problem is about some kind of uncertainty. A random sample of data is used as a representative for the entire world.
In this course, we will get to know different techniques to model uncertainty and what approaches algorithms can use to cope with it. We will cover topics such as
- Online Algorithms
- Online Learning Algorithms and Online Convex Optimization
- Markov Decisions Processes
- Stochastic and Robust Optimization
Prerequisites
You should bring a solid background in algorithms, calculus, and probability theory. Specialized knowledge about certain algorithms is not necessary.
Lecture Notes
- Lecture Notes May 20, 2020 (Adaptivity Gap) (Update May 31: z_{1, 24} was incorrect in Example 10.2)
- Lecture Notes Jul 1, 2020 (No-Regret Learning: Lower Bound) (Update Jul 2: There was some confusion regarding the constants in the lecture. The notes seem to be correct now.)