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 1516, HG E1.1, Tue 1012, ETF C1. 
Credit Points:  8CP for Data Science Master, Computer Science Master and Computational Science and Engineering Master (261511000L, 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 "252020900L 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 closedbook. 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 1315  CHN G22  Beginning with AC  Gleb Novikov 
B  Tue 1315  HG D3.2  Beginning with DO  Tommaso D'Orsi 
C  Tue 1315  RZ F21  Beginning with PZ  Stefan Tiegel 
These form a selfstudy 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.
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 nethzlogin.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 89) 
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: CauchySchwarz inequality, Sec 2.6 (pp 4849) 
Exercise Set 2 lab2template 
Chapter 2 with Solutions lab2solutions.ipynb 
Tue 26.02.19  
10  Mon 04.03.19 
Projected Gradient Descent (notes, slides) Blackboard: Sec 3.5 (pp 6266) 
Exercise Set 3 lab3template 
Chapter 3 with Solutions lab3solutions.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 lab4template 
Chapters 4&5 with Solutions lab4solutions.ipynb 
Tue 12.03.19 

12  Mon 18.03.19 
Nonconvex Functions (notes, slides) 
Exercise Set 5 lab5template 
Chapter 6 with Solutions lab5solutions.ipynb 
Tue 19.03.19 

13  Mon 25.03.19 
Newton's and QuasiNewton 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 
QuasiNewton Method (cont'd) (notes, slides) 
Exercise Set 7 lab7template 
lab7solutions 
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.26)  
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 1012)  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 1315)  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 