### The course

Machine learning is currently one of the most influential subfields of Computer Science. With applications in numerous fields, including information technologies, medicine, physics, and finances, Machine Learning has an ever growing influence on science and society.

This course will take a foundational perspective and cover some of the mathematical principles and concepts that underlie machine learning algorithms. Topics will range from well-established results in learning theory, to current methods and research challenges. We will start with classic results from the 70's and 80's, such as Vapnik-Chervonenkis (VC) theory and the Probably-Approximately-Correct (PAC) framework, which lay the ground for a formal theory of automated learning. Building on this, we will present and analyze several popular machine learning methods, such as Nearest Neighbors, Boosting, and Support Vector Machines. We will also point to directions of current research.

This course invites students from all faculties and levels that enjoy mathematical rigor and are curious to gain a deeper understanding of machine learning. It will be most suitable for Masters and PhD students with a background in Mathematics or theoretical Computer Science (especially if you are looking for an exciting research topic). Be prepared for theorems and proofs :)

We are looking forward to seeing you there!

**Required background:** basic knowledge on probability and linear algebra.

### Announcements

**February 13**

A brief reminder. Tomorrow we will have a written exam. It starts at 8:15 and lasts until 9:45.

You can use any printed sources during the exam. In order not to fail the course, you need to score

at least 30 points for the exam.

**February 9**

Next tutorial (next Monday) will be devoted to Quastions-and-Answers session.

Next Tuesday we will have a written exam, which starts at 8:15.

**January 26**

Assignment 5 is out!

It is due Monday, January 30, 12:15pm.

Please hand it in **at the beginning** of the tutorial.

**January 20**

We propose to schedule the exam on the day of last lecture, which is **February 14th**.

The exam will be written, consisting of a set of problems on the topics covered in the course.
The students will all sit in the lecture room and receive their test sheets.
Within a limited amount of time the students will need to solve the problems, write down the solutions, and hand them to us.

Students are allowed to use any **printed or written sources** on paper, but no electronic devices.

**January 13**

There was a mistake in problem 2 of assignment 4. Now it is fixed.

**January 10**

Assignment 4 is out!

It is due Monday, January 16, 12:15pm.

Please hand it in **at the beginning** of the tutorial.

**January 8**

No tutorial on Monday, January 9!

**December 11**

Assignment 3 is out!

It is due Monday, December 19, 12:15pm.

Please hand it in **at the beginning** of the tutorial.

**December 6**

Next week, **tutorial and lecture times are switched**.

The lecture will be on Monday, Dec 12 at noon and the tutorial on Tuesday, Dec 13, at 8am.

**December 4**

Recall that there is **no class** and **no tutorial** this week.

**November 15**

Assignment 2 has been updated, some typos fixed.

**November 14**

Assignment 2 is out!

It is due Monday, November 21, 12:15pm.

Please hand it in **at the beginning** of the tutorial.

**October 31**

The first assignment is out!

It is due Monday, November 7, 12:15pm.

Please hand it in **at the beginning** of the tutorial.

Classes start on October 18. Tutorials start on October 24.

### Assignments

- October 31: Assignment 1
- November 14: Assignment 2
- December 11: Assignment 3
- January 10: Assignment 4
- January 26: Assignment 5

### Material for individual lectures

- October 18, Lecture 1: Intro to Learning Theory pdf
- October 25, Lecture 2: Learnability of finite classes, definition of learnability, VC-dimension pdf
- November 8, Lecture 3: Learnability of classes with finite VC dimensions, VC-bound pdf
- November 15, Lecture 4: No-free-lunch Theorem pdf
- November 22, Lecture 5: Linear classifiers pdf
- November 29, Lecture 6: Boosting pdf
- December 23, Lecture 7: Nearest Neighborpdf
- January 10, Lecture 9: Rademacher Complexity pdf
- January 16, Lecture 10: Bounding Rademacher Complexities pdf
- January 24, Lecture 11: Kernels, Reproducing Kernel Hilbert spaces, representer theorem pdf
- January 31, Lecture 12: Support Vector Machines, hard-margin and soft-margin SVM, kernel trick pdf
- February 7, Lecture 13: Risk bounds for kernel methods pdf

### Literature

Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.

*A large part of the course will follow closely this book.*Bousquet O., Boucheron S., Lugosi G. Introduction to statistical learning theory, 2004.

*This one is a nice reference for getting an idea about the topic.*Boucheron S., Bousquet O., Lugosi G. Theory of Classification: a Survey of Recent Advances, 2005.

*This is an extended version of the previous reference. For those who want to go deeper into the details.*

### Lecturers

Ruth Urner |
Ilya Tolstikhin |

### Teaching assistants

Carl-Johann Simon-Gabriel |
Paul Rubenstein |

### Rules of the game

- There will be an exam with a total of 100 marks
- 30/100 marks are sufficient to pass the exam
- You need to pass the exam to pass the course
- An extra of 20 marks on the exam can be gained by homework

That is: Your homework marks will be scaled to a total of 20 and added to your exam mark

Ruth Urner

Ilya Tolstikhin

MPI for Intelligent Systems

Department of Empirical Inference