Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
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.
|
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. |
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. |
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 |
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.
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.
13 Sep 2019: Exam inspection is at CAB G15.2, 10:30am-12:30pm on Friday 20 Sep 2019. Please come if you would like to inspect your exam.
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 |