Learning Theory

Instructor Nicolas Macris Instructor Ruediger Urbanke
Office INR 134 Office INR 116
Email [email protected] Email [email protected]
Teaching Assistant

Kirill Ivanov [email protected]

Teaching Assistant

Shuqi Wang

[email protected]

Lectures Monday, 08:15 – 10:00 Room INM 202 Zoom
Exercises Tuesday, 17:15 – 19:00 Room INR 219 Zoom

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


Lectures will be online on Zoom on Monday, from 8:15pm to 10:15pm. To access the session use https://epfl.zoom.us/j/95827964653 

If you have any questions during the lecture, use the chat to ask questions. The lectures will be recorded and the recordings are made available here https://tube.switch.ch/channels/868590a6

WhatsApp: there is also a WhatsApp chat. You can join using the following link: https://chat.whatsapp.com/IkgG5NpvsODDXSncJhJchk

Online exercise sessions:

Exercise sessions take place on Tuesdays, from 5pm to 7pm, using the same zoom link. We will solve one problem together at the beginning of the exercise session and in the remaining time we will answer your questions in smaller groups. The exercises sessions are not recorded. 

Graded homework

The graded homework are collected via this Moodle page. You can either write them by hand and scan or you can use latex: 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. 

Final exam

The final exam is a 3 hour open-book on-campus exam (lecture notes, exercices, course material, but no electronic devices), held during the regular exam period. This exam will contribute 90% to the grade.

The exam is scheduled to take place on Thursday 24 June 2021 at 8:15-11:15, room INM200

Should circumstances not allow us to do this, we will replace these 90% with the following. You will be assigned a research paper and will be asked to read it and to write a 4 page latex-typed critical summary. You will be graded on this summary. You will be given a period of three weeks to complete this task. We expect that you spend one week on the assignment. You are allowed to discuss the paper with your colleagues. But the write-up must be yours. We will check for similarities.

Final exam 2019 with solutions 

Final exam 2020 with solutions

Problems 3 and 5.3 from 2019 exam and 5.1 from 2020 exam cover the material which was not given this year and would not appear in the exam.

Final exam 2021 with solutions

Q&A sessions prior to final exam

Q&A session will take place on Tuesday, 22 June at 14:00 on Zoom.


Detailed Schedule

Date Lectures Homework Solutions
22/2 Chapter 3 (in UML) video notes Exercises 1, 3, 7, 8 of Chapter 3. Exercises 1 and 2 of Chapter 4.  Solutions1
1/3 Chapters 4 and 5 (in UML) video notes Exercises 1 and 2 of Chapter 4. Detailed proof of Hoeffding inequality  Solutions2
8/3 Chapter 6  (in UML) video notes

Exercise 1 of Chapter 5. 

Graded homework 1 (submit via moodle before March 23, 23:59)

15/3 Chapter 6 (cont.)  (in UML) video notes  Graded homework 1 (cont.)  
22/3 Chapter 7 (in UML) video notes Exercise 3 of chapter 6. Exercise 3 of chapter 7.  Solutions4
29/3 Chapter 14 (in UML) video notes Homework5 Solutions5
5/4 Easter break    
12/4 Chapter 14 (cont.) (in UML) video notes Graded homework 2 (submit via moodle before April 27, 23:59) Solutions6(GH2)

Lecture notes on two-layer neural networks” by A. Montanari notes notes2

video1 video2

This year we don’t have time to review Neural Tangent Kernels, but if you are interested, you can check the material at the bottom of the page and the last year’s notes. This material will not be part of the exam.

Graded homework 2 (cont.)  


Lectures are based on reviews given above + hand written notes are found below (will be typed if time and health permit).

Tens-chap-1.pdf Motivations and examples, multi-dimensional arrays, tensor product, tensor rank. video notes 
Homework 7 Solutions7
3/5 Tens-chap-1.pdf Continued. Tensor decompositions and rank, Jennrich’s thm video

Graded homework 3 (submit via moodle before May 18th, 23:59)

Not graded: Moore-Penrose pseudoinverse

10/5 Tens-chap-2.pdf Matricizations and Alternating Least Squares algorithm video Homework 9 Solutions9
17/5 Tens-chap-2.pdf Multilinear rank Tucker higher order singular value decomposition video Graded homework 4 (submit via moodle before June 1st 4th, 23:59) Solutions10(GH4)
24/5 Pentecote    
31/5 Tens-chap-3.pdf Power method Applications: Gaussian Mixture Models, Topic models of documents video Homework11 Solutions11

Textbooks and notes:

  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