Learning Theory CS-526

Language: English

Credits: 4 ECTS

Prerequisites:

• Analysis I, II, III
• Linear Algebra
• Machine learning
• Probability
• Algorithms (CS-250)

Here is a link to official coursebook information.

Homework:
Some homework will be graded.

Grading:
If you do not hand in your final exam your overall grade will be NA. Otherwise, your grade will be determined based on the following weighted average: 10 % for the Homework, 90 % for the Final Exam. For the graded homeworks,  you can discuss the homework with other people. But you have to write down your own solution and note on the first page the set of people that you discussed with.

Special Announcements

Online exercise sessions

Exercise sessions will take place online on Zoom on Tuesdays, from 5pm to 7pm. See https://epfl.zoom.us/.  To access the exercise session please click the following link https://epfl.zoom.us/j/384790010

Due to unforeseeable reasons we must swap the lectures on tensors with the remaining lectures on gradient descent. Thank you for your understanding.

Graded homework

From Monday, 16 March, until Sunday, 19 April, all EPFL classes are given online. During this period, no handwritten homework can be handed in and we ask you to use LaTeX to write your homework.
Here is a template for the first graded homework: Latex template graded homework.

If you cannot compile LaTeX on your own computer, EPFL is providing Overleaf Professional accounts for all students: Overleaf EPFL . With Overleaf you can write and compile LaTeX directly from your web browser. To use the provided template (.tex), you can create a new project and upload the .tex file.

Submission instructions for Graded Homework 3
An email should be sent to both TAs with the corresponding PDF file (after you compile it from LaTex, no need to send the LaTex source code) and the filled notebook of Problem 4.
The title of the email should be LT-GHW3.
The pdf file should be titled Firstname_Lastname_GH3.pdf and the notebook Problem_4_Firstname_Lastname.ipynb.

Final exam

The final exam will take on Wednesday, 19 August 2020 from 8.15 am to 11.15 am in INM202.

The exam will be open-book (lecture notes, exercises, course materials) but no electronic devices allowed.

Q&A sessions prior to final exam

We will organize Q&A sessions on Zoom. The first session will take place on Tuesday, 28 July 2020 from 5pm to 7pm.

Link for 1st Q&A session: https://epfl.zoom.us/j/384790010

2019 final exam

Last year final exam
Solution to last year final exam

Topics

• PAC learning model (based on Chapters 2-7 in Understanding Machine Learning (UML) by Shalev-Shwartz and Ben David)
• Gradient descent (UML and notes by A. Montanari)
• Tensor decomposition (based on the review on Tensors Decompositions by Rabanser, Shchur and Günnemann).
  For more advanced material see also: Algorithmic Aspects of Machine Learning by Moitra

Detailed Schedule

Textbooks and notes:

• Understanding Machine Learning by Shalev-Shwartz and Ben David
• Bayesian Reasoning and Machine Learning by David Barber(Cambridge)
• Pattern recognition and Machine Learning by Christopher Bishop (Springer)
• Introduction to Tensor Decompositions and their Applications in Machine Learning (Ranbaser, Shchur, Gunneman)
• Probability on Graphs. Random processes on graph and lattices by Geoffrey Grimmett (Cambridge) [Chap 7]
• Neural Tangent Kernel references:

1. Original paper by Jakot et al.
2. An “easier to read” follow up paper by Arora et al.
3. A nice blog article by Rajat Vadiraj Dwaraknath