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

Lecturers: Bernd Gärtner (CAB G31.1);
David Steurer (CAB H37.1).
Assistants: Luis Barba (CAB G33.3), contact assistant;
Tommaso D'Orsi (CAB H36.2);
Hung Hoang (CAB G19.2);
Gleb Novikov (CAB H36.2);
Stefan Tiegel.
Lectures: Mon 15-16, HG E1.1,
Tue 10-12, ETF C1.
Credit Points: 8CP for Data Science Master, Computer Science Master and Computational Science and Engineering Master (261-5110-00L, 3V + 2U + 2A)
Language: English
Contents: This course teaches an overview of modern optimization methods, with applications in particular for machine learning and data science.
  • In the first part of the course, we will discuss how classic first and second order methods such as gradient descent and Newton's method can be adapted to scale to large datasets, in theory and in practice. We also cover some new algorithms and paradigms that have been developed specifically in the context of data science. The emphasis is not so much on the application of these methods (many of which are covered in other courses), but on understanding and analyzing the methods themselves.
  • 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.
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 120 minutes, it is written and closed-book. No written material permitted!
Past year exam: Questions, Solutions.

Regular Exercises

Theoretical Exercises

The theoretical exercises are discussed in classes, which start from the second week of the semester, i.e., on 26 Feb 2019. Students are expected to try to solve the problems beforehand. We have assigned 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 Assistant
A Tue 13-15 CHN G22 Beginning with A-C Gleb Novikov
B Tue 13-15 HG D3.2 Beginning with D-O Tommaso D'Orsi
C Tue 13-15 RZ F21 Beginning with P-Z Stefan Tiegel

Practical Exercises

These form a self-study component which provides guidance to implement some of the methods discussed in the lectures. Students are encouraged to attempt these exercises and check against the suggested solutions, which will be made available online some time after the release of the exercises. Although they are not discussed in the regular classes, students can contact the practical exercise assistant (Hung Hoang) with any questions.

Announcements

Important announcements about the course during the semester will be published here. Please check back regularly.

14 Feb 2019: The first exercise class on 19 Feb 2019 will be in HG D3.2 only. We will give installation support and an introduction to Jupyter Notebook for the practical exercises. Please refer to the exercise document in the Schedule section for more information.

12 Mar 2019: The past year exam has been published. Please look at the exam section for a version with and one without the solutions.

27 Mar 2019: Special Assignment 1 has been published. Please refer to the Schedule section.

2 Apr 2019: Updated Addendum of Special Assignment has been uploaded to the Schedule section.

2 Apr 2019: New textbook by Martin J. Wainwright, just released last month, has been added in the Literature section. It is available through the link in that section, using the ETH library access.

21 May 2019: Solution of Special Assignment 1 has been published. Please refer to the Schedule section.

24 May 2019: Special Assignment 2 has been published. Please refer to the Schedule section.

15 Jul 2019: Solution of Special Assignment 2 has been published. Please refer to the Schedule section.

Schedule

In the table below are the lecture dates and the preliminary topics. The exercises and their solutions will be published here.

Note: Documents are password protected. Please use your nethz-login.

Calendar Week Date Topic Exercises and Special
Assignments (by due date)
Solutions
8 Mon 18.02.19 Theory of Convex Functions (notes, slides)
Blackboard: Def 1.9, Thm 1.10 (pp 8-9)
Exercise Set 1
npprimer.ipynb

Chapter 1 with Solutions
(Note: Exercise 7 is not examinable)
Tue 19.02.19
9 Mon 25.02.19 Gradient Descent (notes, slides)
Blackboard: Cauchy-Schwarz inequality,
Sec 2.6 (pp 48-49)
Exercise Set 2
lab2-template

Chapter 2 with Solutions
lab2-solutions.ipynb
Tue 26.02.19
10 Mon
04.03.19
Projected Gradient Descent (notes, slides)
Blackboard: Sec 3.5 (pp 62-66)
Exercise Set 3
lab3-template
Chapter 3 with Solutions
lab3-solutions.ipynb
(Put this in the same folder as the template file.)
Tue
05.03.19
11 Mon
11.03.19
Subgradient Descent & Stochastic Gradient Descent (notes, slides)
Blackboard: Nesterov's GD
Exercise Set 4
lab4-template
Chapters 4&5 with Solutions
lab4-solutions.ipynb
Tue
12.03.19
12 Mon
18.03.19
Nonconvex Functions (notes, slides) Exercise Set 5
lab5-template
Chapter 6 with Solutions
lab5-solutions.ipynb
Tue
19.03.19
13 Mon
25.03.19
Newton's and Quasi-Newton Methods (notes, slides) Special Assignment 1
Addendum to Special Assignment 1
Exercise Set 6
Solution of Special Assignment 1
Chapters 7&8 with Solutions
Tue
26.03.19
14 Mon
01.04.19
Quasi-Newton Method (cont'd) (notes, slides) Exercise Set 7
lab7-template
lab7-solutions
Tue
02.04.19
Local Optimization Is Hard (slides)
15 Mon
08.04.19
Sechseläuten – No Lecture! Exercises 1.1, 1.3, 1.4, 1.7 Chapter with Solutions
Tue
09.04.19
Regression (notes) (pp.2-6)
16 Mon
15.04.19
Out of Sample Prediction Error and Matrix Concentration Bound (notes) Exercise Set 9
Solutions to Exercise Set 9
Tue
16.04.19
17 Mon
22.04.19
Easter – No Lecture!
Tue
23.04.19
Easter – No Lecture!
18 Mon
29.04.19
Bayesian Linear Regression and Optimality of Least Squares (notes) Exercise Set 10
Solutions to Exercise Set 10
Tue
30.04.19
19 Mon
06.05.19
Sparse Linear Regression, Likelihood Maximization and Guarantees of Best Subset Selection (pp 10-12) Exercise Set 11 Solutions to Exercise Set 11
Tue
07.05.19
20 Mon
13.05.19
Statistical Guarantees of LASSO for Sparse Linear Regression, Slow and Fast Rates (pp 13-15) Exercise Set 12 Solutions to Exercise Set 12
Tue
14.05.19
21 Mon
20.05.19
Factorization (notes) Special Assignment 2
Exercise 2.1, 2.4, 2.5
Solution of Special Assignment 2
Solutions to Exercise Set 13
Tue
21.05.19
22 Mon
27.05.19
Factorization (cont'd)
Tue
28.05.19