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 (2021)

Lecturers: Bernd Gärtner (CAB G31.1)
Niao He
David Steurer (CAB H37.1)
Assistants: Rares Buhai (CAB H37.1)
Jingqiu Ding (CAB H37.1)
Tommaso D'Orsi (CAB H37.2)
Yuan Gao
Saeed Ilchi (CAB G32.1)
Chih-Hung Liu (CAB H19.3)
Federico Soldà (CAB H31.2)
Stefan Tiegel (CAB J21.3), contact assistant
Yuhao Yao
Lectures: Mon 13-14 (online),
Tue 10-12 (online).
Credit Points: 10CP (261-5110-00L, 3V + 2U + 4A)
Language: English
Contents: This course provides an in-depth theoretical treatment of optimization methods that are particularly relevant in machine learning and data science.
  • In the first part of the course, we will first give a brief introduction to convex optimization, with some basic motivating examples from machine learning. Then we will analyse classical and more recent first and second order methods for convex optimization: gradient descent, Nesterov's accelerated method, proximal and splitting algorithms, subgradient descent, stochastic gradient descent, variance-reduced methods, Newton's method, and Quasi-Newton methods. The emphasis will be on analysis techniques that occur repeatedly in convergence analyses for various classes of convex functions. We will also discuss some classical and recent theoretical results for nonconvex optimization.
  • In the second part, we discuss convex programming relaxations as a powerful and versatile paradigm for designing efficient algorithms to solve computational problems arising in data science. We will learn about this paradigm and develop a unified perspective on it through the lens of the sum-of-squares semidefinite programming hierarchy. As applications, we are discussing non-negative matrix factorization, compressed sensing and sparse linear regression, matrix completion and phase retrieval, as well as robust estimation.
Moodle: All materials in the course are published through the moodle page of the course.
Literature:
Prerequisites: As background, we require material taught in the course "252-0209-00L Algorithms, Probability, and Computing". It is not necessary that participants have actually taken the course, but they should be prepared to catch up if necessary.

Exams, Special Assignments and Grading

Grading: There will be a written exam in the examination session. Furthermore, there will be two mandatory written special assignments during the semester. The final grade of the whole course will be calculated as a weighted average of the grades for the exam (80%) and the special assignments (20%).
Special Assignments: At two times in the course of the semester, we will hand out specially marked exercises or term projects — the written part of the solutions are expected to be typeset in LaTeX or similar. Solutions will be graded, and the grades will account for 20% of the final grade. Assignments can be discussed with colleagues, but we expect an independent writeup.
Exam: Date to be determined. The exam lasts 180 minutes, it is written and closed-book. No written material permitted!

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 Students with Surnames (Last Names) Assistant
A Tue 14-16 online M - Z First half: Federico Soldà
Second half: Yuan Gao
B Tue 16-18 online A - L First half: Rares Buhai
Second half: Yuhao Yao