Learning theory
Weekly outline
-
This master class on learning theory covers the classical PAC framework for learning, stochastic gradient descent, tensor methods. We also touch upon topics from the recent literature on mean field methods for NN and the double descent phenomenon.
Teacher: Nicolas Macris: nicolas.macris@epfl.ch
Teaching Assitant: Perrine Vantalon - perrine.vantalon@epfl.ch
Courses: Mondays 8h15-10h Room INM202; Exercises: Tuesdays 17h15-19h Room INR219.
We will use this moodle page to distribute homeworks, solutions, and lecture material each week. As well as use the discussion and questions forum. Dont hesitate to actively use this forum.
MIDTERM: there will be a midterm on monday March 30 at 8h15 - 10h in room INM202. This will count 30% towards the final grade. Its open book (you can bring your notes, printed material, the UML book, or download material on your laptop before hand and have wifi switched off).
EXAM: the final exam during official exam session will count for 70% of the final grade. Its open book (you can bring your notes, printed material, the UML book, or download material on your laptop before hand and have wifi switched off).
Textbooks and notes:
- Understanding Machine Learning (UML) by Shalev-Shwartz and Ben David
- A paper on double descent phenomenon
- Introduction to Tensor Decompositions and their Applications in Machine Learning (Ranbaser, Shchur, Gunneman)
- One lecture on two-layer neural networks
-
If you have a question or want to start a discussion on a topic, post here
- Understanding Machine Learning (UML) by Shalev-Shwartz and Ben David
-
Week of 23rd-24th we will have class on monday (during regular time) and also on tuesday (during exercise session time)
-
1. Monday 23: PAC learning framework. Finite classes. Uniform convergence.
See chapters 3 and 4 in UML
Homework 1: exercises 1, 3, 7, 8 of Chapter 3 (discussed in exercise session next week)
2. Tuesday 24: No free lunch theorem.
See chapter 5 in UML
Homework 2: exercises 1 and 2 of chapter 4 + extra on proof of Hoeffding's inequality (discussed in exercise session next week)
-
Learning infinite classes
Chapter 6 in UML
Homework 1: exercises 1, 3, 7, 8 of Chapter 3
Homework 2: exercises 1 and 2 of chapter 4 + extra on proof of Hoeffding's inequality
-
Bias variance tradeoff and the double descent phenomenon
We will study the double descent of generalization error based on the paper "Two models of double descent for weak features" by Belkin, Hsu, Xu
-
Double descent continued
-
Gradient descent (convexity, Lipshitzness, Approach to optimal solution)
Stochastic gradient descent, application to learning
Chapter 14 in UML
-
MIDTERM monday 30 march 8h15 - 10h room INM 202
-
-
Mean field approach for two layer neural networks
based on the paper "One lecture on two layer neural networks" by A. Montanari
-
We finish discussing the main idea of the mean field analysis of two layer neural networks (notably part II of notes).
Homework: we have extra homework 7 on convexity, GD, SGD below. -
Tensors 1. Motivations and examples, multi-dimensional arrays, tensor product, tensor rank.
Tensors 2. Tensor rank and decompositions, Jennrich's theorem (proof of thm next time)
-
Tensors 2bis. Jennrich's algorithm (proofs)
-
Tensors 3. Alternating least square algorithm
-
Tensors 4. Multilinear rank Tucker higher order singular value decomposition
-
Tensors 5. Power method and Applications: Gaussian Mixture Models, Topic models of documents
-
Here we will post old exams with solutions which will allow you to train yourself. Note that some problems (but not all) are included in the current year's material.
-
