Aktuelle Themen in Algorithmen für große Datenmengen 1+2:
Optimization and Uncertainty (Summer 2023)
Topical
- Logbook with detailed information about schedule and content.
- Part I ended with Lecture 13. Part II started with Lecture 14.
Organization
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Conrad Schecker, Lisa Wilhelmi
- LSF Entries: Part 1, Part 2, Complete course
- Lectures: Tue+Thu 10:15 - 11:45h, Magnus Hörsaal, R.M.S. 11-15
- Exercises: Fri 10:15 - 11:45h, SR 11, R.M.S. 11-15
Material
Lecture Notes
Current update: 14 July 2023 (restricted access).
Videos
Videos are recorded by studiumdigitale and are published on this page (HRZ login).
Videos from Summer 21 are available here (HRZ login). Note that contents of the lectures and their order might differ slightly from this year's iteration of the course.
Exercises
Each assignment is published on Tuesday and is due the following Tuesday at 10:00h. Your solutions have to be submitted as a single PDF file.
Exercise Sheets
Part 1:
- Exercise Sheet 1. Issued: 18.04.2023. Due: 25.04.2023, 10:00h.
- Exercise Sheet 2. Issued: 25.04.2023. Due: 02.05.2023, 10:00h.
- Exercise Sheet 3. Issued: 02.05.2023. Due: 09.05.2023, 10:00h.
- Exercise Sheet 4. Issued: 09.05.2023. Due: 23.05.2023, 10:00h.
- Exercise Sheet 5. Issued: 23.05.2023. Due: 30.05.2023, 10:00h.
- Exercise Sheet 6. Issued: 30.05.2023. Due: 13.06.2023, 10:00h.
Part 2:
- Exercise Sheet 7. Issued: 13.06.2023. Due: 20.06.2023, 10:00h.
- Exercise Sheet 8. Issued: 20.06.2023. Due: 27.06.2023, 10:00h.
- Exercise Sheet 9. Issued: 27.06.2023. Due: 04.07.2023, 10:00h.
- Exercise Sheet 10. Issued: 04.07.2023. Due: 11.07.2023, 10:00h.
Topic
Suppose you go on a sequence of n dates, after each of which you have to decide if you want to start a relationship or see more people - when is the best time to stop dating to get the best partner? Optimization problems of this type arise frequently in modern computer systems. Often large data sets can be used to infer probabilistic information about the expected benefit of the potential decisions. The course gives an introduction to algorithmic techniques for solving optimization problems with uncertainty. We will start with classic stopping problems as the one sketeched above (i.e., secretary and prophet-inequality problems) and advance to more general online optimization problems in which the input is partly stochastic and partly adversarial. Futher topics of interest are recent developments in online learning, Markov decision processes, testing and probing problems, as well as applications of these techniques in distributed systems and markets.
Literature
- See the logbook for pointers to the literature.