Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Optimization for Data Science (2023)

Lecturers: Bernd Gärtner (CAB G31.1)
Niao He (CAB F62)
Assistants: Hongjie Chen (CAB F77)
Ilyas Fatkhullin (OAS J28)
Saeed Ilchi (CAB G19.2), contact assistant
Xiang Li (CAB F61.2)
Federico Soldà (CAB H31.2)
Junchi Yang (CAB F61.2)
Lectures: Mon 13-14 (NO C60),
Tue 10-12 (ETF C1),
Recordings of last year: ETH Video Portal (there may be a few changes in the content this year).
Credit Points: 10CP (261-5110-00L, 3V + 2U + 4A)
Language: English
Schedule: The course schedule can be found here. Please note that this plan is tentative and may be subject to changes during the semester.
Contents: This course provides an in-depth theoretical treatment of classical and modern optimization methods that are relevant in data science.
After a general discussion about the role that optimization has in the process of learning from data, we give an introduction to the theory of (convex) optimization. Based on this, we present and analyze algorithms in the following four categories: first-order methods (gradient and coordinate descent, Frank-Wolfe, subgradient and mirror descent, stochastic and incremental gradient methods); second-order methods (Newton and quasi Newton methods); non-convexity (local convergence, provable global convergence, cone programming, convex relaxations); min-max optimization (extragradient methods).
The emphasis is on the motivations and design principles behind the algorithms, on provable performance bounds, and on the mathematical tools and techniques to prove them. The goal is to equip students with a fundamental understanding about why optimization algorithms work, and what their limits are. This understanding will be of help in selecting suitable algorithms in a given application, but providing concrete practical guidance is not our focus.
Moodle: All materials in the course are published through the moodle page of the course.
Literature:
Prerequisites: A solid background in analysis and linear algebra; some background in theoretical computer science (computational complexity, analysis of algorithms); the ability to understand and write mathematical proofs.

Exams, Graded Assignments, and Grading

Grading: There will be a written exam in the examination session. Furthermore, there will be four mandatory written graded assignments during the semester. The final grade of the whole course will be calculated as a weighted average of the grades for the exam (60%) and the graded assignments (40%).
Concretely, let PE be the performance in the final exam, and P1, P2, P3, P4 be the performances in the four graded assignments, measured as the percentage of points being attained (between 0% and 100%). A graded assignment that is not handed in is counted with a performance of 0%. Then the overall course performance is computed as P = 0.1*P1 + 0.1*P2 + 0.1*P3 + 0.1*P4 + 0.6*PE. A course performance of P >= 50% is guaranteed to lead to a passing grade, but depending on the overall performance of the cohort, we may lower the threshold for a passing grade.
Graded Assignments: At four times during the course of the semester, we will hand out graded assignments (compulsory continuous performance assessments). The solutions are expected to be typeset in LaTeX or similar. Assignments can be discussed with colleagues, but we expect an independent writeup. The release dates of the graded assignments are as follows:
  • GA1 is out on March 6 (covers lectures 1 to 3)
  • GA2 is out on April 3 (covers lectures 4 to 7)
  • GA3 is out on May 9 (covers lectures 8 to 11)
  • GA4 is out on May 30 (covers lectures 12 to 14)
Exam: Date to be determined. The exam lasts 180 minutes, it is written and students can bring at most four A4 pages of written aids (no restrictions regarding form or content).

Regular Exercises

The exercises are discussed in classes. Students are expected to try to solve the problems beforehand. Your assistant is happy to look at your solutions and correct/comment them. We assign students to classes according to surnames. Attendance according to these assignments is not compulsory but encouraged. The details of the classes are as follows.

Group Time Room Assistant
A Tue 14-16 CAB G51 First Half: Federico Soldà,
Second Half: Xiang Li.
B Fri 14-16 ML H44 First Half: Junchi Yang,
Second Half: Ilyas Fatkhullin.